[解決済み】フィボナッチ数列の計算複雑性

質問

Big-O記法は理解できるが、多くの関数で計算方法がわからない。特に、フィボナッチ数列の素朴版の計算量を知りたいのですが。

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

フィボナッチ数列の計算量とその計算方法を教えてください。

どのように解くのですか？

時間関数をモデル化して計算します。 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(2 n ) . そして、帰納法で自分の推測を証明することができます。

ベースとなります。 n = 1 は当然として

仮定 T(n-1) = O(2 n-1 ) , したがって

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

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

しかし、コメントで指摘されているように、これは厳密な境界ではありません。この関数に関する興味深い事実は、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.6 n ) ). このタイトバウンドは、上で述べたように、生成関数を使うことで知ることができます。