3

フィボナッチ数を計算するアルゴリズムに取り組んでおり、その疑似コードを取得しましたが、実行にかかる時間がわかりません。O(n) で実行されると思いますが、よくわかりません。コードは次のとおりです。

Algorithm Fast-Fibonacci(n)
Let fib[0] and fib[1] be 1.
for each i from 2 to n, do:
    Let fib[i] be fib[i - 2] + fib[i - 1].
end of loop
return fib[n].

助けてくれてありがとう。

4

3 に答える 3

5

配列を埋めるために 2 から n まで順番にカウントしているだけなので、これには O(n) が必要です。i-1 番号と i-2 番号のそれぞれに対して何らかのルックアップを行っていた場合、複雑さが増す可能性がありますが、記述した方法では、これらの値のそれぞれに対して直接アドレスを呼び出しています。

于 2012-07-13T17:50:06.923 に答える
2

うん。大きな利点は、ループあたりの操作数が一定であり、ループのサイズが n のサイズに対して線形であることです。

ただし、最後の 2 つの数値以外は特に気にしないため、よりスペース効率の高いソリューションが存在します。次はそれを試してください！

于 2012-07-13T17:50:20.667 に答える