 | (1)最短路アルゴリズムの伝播法の計算量を次のように求める．ｎ頂点のグラフの発見途中の木Ｔにおいて，その頂点集合Ｖ(Ｔ)が|Ｖ(Ｔ)|=ｋ(ｋ=1, 2,...,n-1)とすると，Ｖ(Ｔ)に含まれない頂点集合Ｖ(Ｔ)^c=Ｖ-Ｖ(Ｔ)は|Ｖ(Ｔ)^c|=n-kとなる．
伝播法では，計算量最大の場合は2頂点ｘ∈Ｖ(Ｔ),y∈Ｖ(Ｔ)^cを両端とする辺の探索を行う手段である．よって，計算量が次式で計算することを示せ．
1 * (n-1) + 2 * (n-2) + ... + (n-1) * 1 = (n(n+1)(n-1))/ 6
よろしくお願いします．あと可能なら
(2)次のフィボナッチ数列を解け．
f(n) = f(n-1) + f(n-2) (n≧3), f(1) = 1 = f(2)
(3)方程式f(x) = x^3 - 3 = 0 に対してニュートン法を用い，再帰式を導け．
(初期式X_0 > 0とすればよい)
もお願いします！
|