algorithm - 递归的复杂度 : T(n) = T(n-1) + T(n-2) + C

Question

我想了解如何得出以下递推关系的复杂性。

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)

但是，对于我遇到的问题，我无法想出类似的方法。如果我的方法不正确，请纠正我。

Answer 1

复杂度与输入大小有关，其中每个调用都会产生调用的二叉树

其中 T(n) 总共调用了 2n ..

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

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

O(2n)

以同样的方式，您可以将递归函数概括为斐波那契数

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

接下来可以用直接公式代替递归的方式

使用称为 Binet's Formula 的复杂方法