[解決済み] 再帰の複雑さ T(n) = T(n-1) + T(n-2) + C

質問

以下の漸化式の複雑さの算出方法を理解したい。

T(n) = T(n-1) + T(n-2) + C 与えられた T(1) = C と T(2) = 2C;

一般に、以下のような方程式では T(n) = 2T(n/2) + C (T(1)=Cとした場合）、私は次のような方法をとっています。

T(n) = 2T(n/2) + C
=> T(n) = 4T(n/4) + 3C
=> T(n) = 8T(n/8) + 7C
=> ...
=> T(n) = 2^k T (n/2^k) + (2^k - 1) c

では、次に n/2^k = 1 => K = log (n) (2の底に)

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

しかし、私が抱えている問題に対して、同様のアプローチを思いつくことができません。もし、私のやり方が間違っていたら、訂正してください。

どのように解決するのですか？

複雑さは入力サイズに関係し、各呼び出しは呼び出しの二分木を生成します。

ここで T(n) 作る 2 n の呼び出しが合計で.

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

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

O(2 n )

同じように、再帰的関数をフィボナッチ数として一般化することができます。

T(n) = F(n) + ( C * 2 n )

次に、再帰的な方法ではなく、直接的な式を使用することができます。

という複雑な方法を用いて ビネーの公式