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;

通常对于像 (Given T(1) = C) 这样的方程T(n) = 2T(n/2) + 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)

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

score 7 · Accepted Answer

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

总共在哪里T(n)打电话2ⁿ..

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

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

O(2ⁿ)

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

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

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

使用称为比内公式的复杂方法

score 4 · Accepted Answer

4

您可以使用此处描述的这种通用方法。如果您有更多问题，请询问。

于 2013-07-18T05:09:25.353 回答

score 4 · Accepted Answer

对于您的目的，“比指数差”是否足够准确？特例 C=0 定义了 http://en.wikipedia.org/wiki/Fibonacci_number，你可以从文章中看到它是指数级的。假设 C 为正，您的系列将比这增长得更快。事实上，您的系列将介于斐波那契数列和斐波那契数列的变体之间，其中黄金比例被稍大一些的东西所取代。

score 4 · Accepted Answer

如果您也有兴趣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

这里有一些快速代码来演示：

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

score 2 · Accepted Answer

这种类型的递归称为：非齐次递归关系，您必须在一开始就解决齐次递归（最后没有常数的递归）。如果您有兴趣，请阅读其背后的数学。

我会告诉你一个简单的方法。只需在wolfram-alpha中输入您的方程，您将得到：

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

但是两者的增长率是一样的：

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

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

5 回答 5

Related

Reference