373

Big-O 表記法は理解できますが、多くの関数で計算する方法がわかりません。特に、単純なバージョンのフィボナッチ数列の計算上の複雑さを理解しようとしています。

int Fibonacci(int n)
{
    if (n <= 1)
        return n;
    else
        return Fibonacci(n - 1) + Fibonacci(n - 2);
}

フィボナッチ数列の計算上の複雑さとはどのように計算されますか?

4

12 に答える 12

408

計算する時間関数を、計算する時間、計算する時間、およびそれらFib(n)を合計する時間の合計としてモデル化します( )。これは、同じものを繰り返し評価するのに同じ時間がかかることを前提としています。つまり、メモ化は使用されません。Fib(n-1)Fib(n-2)O(1)Fib(n)

T(n<=1) = O(1)

T(n) = T(n-1) + T(n-2) + O(1)

この再帰関係を (たとえば生成関数を使用して) 解くと、最終的に答えが得られます。

または、深さのある再帰ツリーを描画nして、この関数が漸近的に であることを直感的に理解することもできます。その後、帰納法によって予想を証明できます。O(2n)

ベース：n = 1明白です

したがって、_T(n-1) = O(2n-1)

T(n) = T(n-1) + T(n-2) + O(1) に等しい

T(n) = O(2n-1) + O(2n-2) + O(1) = O(2n)

ただし、コメントに記載されているように、これは厳密な境界ではありません。この関数に関する興味深い事実は、T(n) がの値と漸近的に同じFib(n)であることです。これは、両方が次のように定義されているためです。

f(n) = f(n-1) + f(n-2).

再帰ツリーの葉は常に 1 を返します。 の値はFib(n)、再帰ツリーの葉によって返されるすべての値の合計であり、葉の数に等しくなります。各リーフの計算には O(1) かかるため、T(n)は に等しくなりFib(n) x O(1)ます。したがって、この関数の厳密な境界は、フィボナッチ数列そのもの (~ ) です。上で述べたように、生成関数を使用して、このタイトな境界を見つけることができます。θ(1.6n)

于 2008-12-11T20:29:12.750 に答える
155

F(n)完了するために実行する必要があるステートメントの数を自問してください。

の場合F(1)、答えは1(条件の最初の部分) です。

の場合F(n)、答えはF(n-1) + F(n-2)です。

では、これらの規則を満たす関数は何ですか? n (a > 1) を試してください:

n == a ( n-1) + a (n-2)

(n-2)で割る:

2 == + 1

を解くと、黄金比として知られるaが得られます。(1+sqrt(5))/2 = 1.6180339887

したがって、指数関数的な時間がかかります。

于 2008-12-11T20:26:21.553 に答える
37

pgaur と rickerbh に同意します。再帰フィボナッチの複雑さは O(2^n) です。

私はかなり単純化して同じ結論に達しましたが、それでも妥当な推論だと思います。

まず、N 番目のフィボナッチ数を計算するときに、再帰的なフィボナッチ関数 (今後は F() ) が何回呼び出されるかを把握することがすべてです。0 から n までのシーケンスで数値ごとに 1 回呼び出される場合は O(n) になります。数値ごとに n 回呼び出される場合は、O(n*n) または O(n^2) になります。等々。

したがって、数値 n に対して F() が呼び出されると、0 から n-1 の間の特定の数値に対して F() が呼び出される回数は、0 に近づくにつれて増加します。

第一印象として、視覚的に言えば、 F() が特定の数値に対して呼び出される時間ごとに単位を描画すると、一種のピラミッド形状が得られるように思えます (つまり、単位を水平方向に中央に配置すると）。このようなもの：

n              *
n-1            **
n-2           ****  
...
2           ***********
1       ******************
0    ***************************

さて問題は、n が大きくなるにつれて、このピラミッドの底面がどのくらいの速さで拡大するかということです。

F(6) のような実際のケースを考えてみましょう。

F(6)                 *  <-- only once
F(5)                 *  <-- only once too
F(4)                 ** 
F(3)                ****
F(2)              ********
F(1)          ****************           <-- 16
F(0)  ********************************    <-- 32

F(0) が 32 回呼び出されることがわかります。これは 2^5 であり、このサンプル ケースでは 2^(n-1) です。

ここで、F(x) が呼び出される回数を知りたいのですが、F(0) が呼び出される回数はその一部にすぎないことがわかります。

F(6) 行から F(2) 行までのすべての * を精神的に F(1) 行に移動すると、F(1) 行と F(0) 行の長さが等しくなることがわかります。つまり、n=6 の場合に F() が呼び出される合計回数は 2x32=64=2^6 です。

さて、複雑さの観点から：

O( F(6) ) = O(2^6)
O( F(n) ) = O(2^n)
于 2014-04-15T21:38:56.573 に答える
35

MIT で、この特定の問題に関する非常に優れた議論があります。5 ページでは、加算に 1 計算単位がかかると仮定すると、Fib(N) の計算に必要な時間は Fib(N) の結果と非常に密接に関連していることが指摘されています。

その結果、フィボナッチ数列の非常に近い近似に直接スキップできます。

Fib(N) = (1/sqrt(5)) * 1.618^(N+1) (approximately)

したがって、単純なアルゴリズムの最悪の場合のパフォーマンスは

O((1/sqrt(5)) * 1.618^(N+1)) = O(1.618^(N+1))

PS: 詳細情報が必要な場合は、ウィキペディアでN 番目のフィボナッチ数の閉じた形式の表現に関する議論があります。

于 2008-12-11T21:10:03.057 に答える
10

下端は2^(n/2)2^n で、上端は 2^n で区切られています (他のコメントで述べたように)。そして、その再帰的な実装の興味深い事実は、Fib(n) 自体の厳密な漸近境界があることです。これらの事実は次のように要約できます。

T(n) = Ω(2^(n/2))  (lower bound)
T(n) = O(2^n)   (upper bound)
T(n) = Θ(Fib(n)) (tight bound)

タイト バウンドは、必要に応じてクローズド フォームを使用してさらに減らすことができます。

于 2008-12-11T21:03:08.937 に答える
1

まあ、私によればO(2^n)、この関数のように、再帰だけがかなりの時間を要しています（分割統治）。上記の関数は、レベルに到達したときに葉が近づくまでツリー内で継続することがわかりF(n-(n-1))ますF(1)。したがって、ここで、ツリーの各深さで遭遇する時間計算量を書き留めると、合計系列は次のようになります。

1+2+4+.......(n-1)
= 1((2^n)-1)/(2-1)
=2^n -1

それはの順序です2^n [ O(2^n) ]。

于 2012-11-18T00:46:27.003 に答える