递归的复杂度：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为底) 时，K代表log（n）的值。

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

但是，我无法想出类似的方法来解决我的问题。如果我的方法有误，请纠正我。

- Gopal

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)

同样地，你可以将递归函数推广为斐波那契数列。

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

接下来，你可以使用直接公式而非递归方式。

使用一种名为Binet's Formula的复杂方法。

- Khaled.K

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) 为第 n 个斐波那契数，有公式 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

这里有一些快速代码以进行演示:

def fib_gen(n):
    """generates fib numbers to avoid rounding errors"""
    fibs=[1,1]
    for i in xrange(n-2):
        fibs.append(fibs[i]+fibs[i+1])
    return fibs

F = fib_gen(50) #just an example.
c=1

def T(n):
    """the recursive definiton"""
    if n == 1:
        return c
    if n == 2:
        return 2*c
    return T(n-1) + T(n-2) + c

def our_T(n): 
    n=n-2 #just because your intials were T(1) and T(2), sorry this is ugly!
    """our found relation"""
    return F[n]*2*c + F[n-1]*c + (F[n+1]-1)*c

并且

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

- seth

Answer 3

您可以使用此处描述的一般方法。点击此处查看。如有更多问题，请提出。

- Aravind

---

@Aravind，你提供的链接非常有帮助！ - Gopal

Answer 4

“比指数更糟糕”对于你的目的是否足够准确？特殊情况C=0定义了斐波那契数列，根据文章可知它是指数级别的。假设C为正数，则你的数列增长速度将比这个更快。事实上，你的数列将介于斐波那契数列和一种变体之间，该变体中黄金比例被略微大一些的东西所替代。

- mcdowella

Answer 5

这种类型的递推关系被称为非齐次递推关系，你需要先解决齐次递推（末尾没有常数项）才能开始解决它。如果您感兴趣，请阅读其背后的数学知识。

我将向您展示一种简单的方法。只需在wolfram-alpha中键入您的方程，您就会得到：

因此，复杂度的增长方式与卢卡斯数或斐波那契数（其中较大的数）相同。

但是它们两个具有相同的增长率：

因此，您的增长率是黄金比的指数：O(phi^n)。

- Salvador Dali