递归的复杂性: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(2n-2) + O(1)

O(2n)

以相同的方式,您可以将递归函数概括为Fibonacci数

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

接下来,您可以使用直接公式而不是递归方式

使用称为Binet公式的复杂方法

Answer 2

如果您也有兴趣为此找到一个明确的公式T(n)可能会有所帮助。

我们知道T(1) = c和T(2) = 2c。T(n) = T(n-1) + T(n-2) + c

因此，只需编写T(n)并开始扩展即可。

T(n) = T(n-1) + T(n-2) + c
T(n) = 2*T(n-2) + T(n-3) + 2c
T(n) = 3*T(n-3) + 2*T(n-4) + 4c
T(n) = 5*T(n-4) + 3*T(n-5) + 7c
and so on.

您会看到系数本身就是斐波那契数！

调用斐波F(n)那nth契数列。 F(n) = (phi^n + psi^n)/sqrt(5)其中phi = (1+sqrt(5))/2和psi = -1/phi，那么我们有：

T(n) = F(n)*2c + F(n-1)*c + (F(n+1)-1)*c

下面是一些用于演示的快速代码：

T(n) = T(n-1) + T(n-2) + c
T(n) = 2*T(n-2) + T(n-3) + 2c
T(n) = 3*T(n-3) + 2*T(n-4) + 4c
T(n) = 5*T(n-4) + 3*T(n-5) + 7c
and so on.

和

>>> T(24)
121392
>>> our_T(24)
121392