斐波那契数列的计算复杂度

Question

我理解大O符号，但不知道如何计算许多函数的复杂度。特别是，我一直在尝试弄清楚斐波那契数列的朴素版本的计算复杂度：

int Fibonacci(int n)
{
    if (n <= 1)
        return n;
    else
        return Fibonacci(n - 1) + Fibonacci(n - 2);
}

斐波那契数列的计算复杂度是多少，如何计算？

- Princess

---

这里有一些不错的答案。 - Greg

请查看这里的矩阵形式部分：http://en.wikipedia.org/wiki/Fibonacci_number。通过以巧妙的方式计算矩阵 ^ n，您可以在O(lg n)的时间内计算斐波那契数列中的第n项Fib(n)。诀窍在于进行幂函数计算。有一个非常好的iTunesU讲座专门介绍如何在O(lg n)的时间内解决这个问题。该课程是MIT的算法入门第三讲（完全免费，如果您感兴趣，请查看）。 - Aly

以上两条评论都没有回答问题，问题是关于朴素版本（在发布的代码中）的计算复杂度，而不是像矩阵形式或非递归计算这样更聪明的版本。 - Josh Milthorpe

这里有一个非常好的视频（链接：https://youtu.be/pqivnzmSbq4），讲解了递归实现的下限复杂度（2^n/2）和上限复杂度（2^n）。 - RBT

一个旁注的问题：斐波那契数列的__naive__实现应该是__iterative__还是__recursive__？ - RBT

Answer 1

您可以将计算 Fib(n) 的时间函数建模为计算 Fib(n-1) 的时间加上计算 Fib(n-2) 的时间再加上将它们相加的时间 (O(1))。这是基于同一个 Fib(n) 的重复计算所花费的时间相同，即没有使用记忆化的假设。

T(n<=1) = O(1)

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

您需要解决这个递归关系（例如使用生成函数），然后就会得出答案。

另外，您还可以绘制递归树，它的深度为 n，通过直观地看出这个函数渐近地是 O(2n)。然后您可以通过归纳证明此猜想的正确性。

基础情形: n = 1 很显然

假设 T(n-1) = O(2n-1)，因此 T(n) = T(n-1) + T(n-2) + O(1)，它等价于 T(n) = O(2n-1) + O(2n-2) + O(1) = O(2n) 然而，正如评论中所指出的那样，这不是紧密边界。关于这个函数的一个有趣事实是 T(n) 渐近地与 Fib(n) 的值相同，因为两者都被定义为 f(n) = f(n-1) + f(n-2)。

递归树的叶子将始终返回 1。Fib(n) 的值是递归树中所有叶子返回值的总和，即等于叶子的数量。由于每个叶子要花费 O(1) 来计算，因此 T(n) 等于 Fib(n) x O(1)。因此，该函数的紧密边界是斐波那契数列本身（~θ(1.6n)）。您可以使用我上面提到的生成函数来找到这个紧密边界。

- Mehrdad Afshari

---

我不把你的StackOverflowException当做笑话。指数时间随着n的增加，即使是很小的值，也很容易被察觉到。 - David Rodríguez - dribeas

@MehrdadAfshari，你能解释一下为什么你认为T(n-1) = O(2^n-1)吗？实际上，T(n-1)应该是(n^2)，因为斐波那契数列有调用T(n-1)+T(n-2)，所以在将所有成本相加后，结果应该是2^n。 - Devendra

数学归纳法真的正确吗？似乎你同样可以假设T(n) = O(n)，然后你将有T(n) = O(n-1) + O(n-2) + O(1) = O(n)所以T(n) = O(n)，但显然这是不正确的。如果它是正确的，请有人解释一下。 - Richard Fung

@RichardFung 这里使用的逻辑不够精确，归纳假设过于薄弱，因为它已经包含了大O符号。正确的假设是说T(n) <= c*2^n，其中c是固定的某个常数，然后从归纳证明的结论中，可以推断出T(n) = O(2^n)。 - amnn

“或者，您可以绘制递归树，它将具有深度n，并直观地发现此函数渐近复杂度为O(2^n)。” - 这是完全错误的。该函数的时间复杂度为O(golden_ratio^n)，从未接近O(2^n)。如果您可以无限接近无穷大，它会接近O(golden_ratio^n)。这就是渐近线的含义，两条线之间的距离必须趋近于0。 - bob

Answer 2

只需问自己需要执行多少语句才能完成F(n)。

对于 F(1)，答案是1（条件的第一部分）。

对于 F(n)，答案是F(n-1) + F(n-2)。

那么什么函数满足这些规则？试试 aⁿ (a > 1)：

aⁿ == a^(n-1) + a^(n-2)

除以 a^(n-2)：

a² == a + 1

求解 a，您将得到 (1+sqrt(5))/2 = 1.6180339887，也被称为 黄金比率 。

所以它需要指数时间。

- Jason Cohen

---

错误的答案获得了30个赞？ :-) 这是否意味着1=F(1)=(1+sqrt(5))/2？ 那么另一个解 (1-sqrt(5))/2 呢？ - Carsten S

不，1不等于1 + 1。满足这些规则的函数在问题中已经提到。 - molbdnilo

答案并没有错误，它在渐近意义下是正确的。另一个解决方案为负数，因此在物理上不合理。 - Da Teng

有人能解释一下a^n = a^(n-1) + a^(n-2)是如何满足这些规则的吗？请具体说明它是如何满足的。 - frank

记住任何树的时间复杂度是O(分支数^树深)吗？对于任何一个分支fib(N)，假设在底部它不是一棵完美的树，在结束时，高度是N，但"平均分支数量"略小于2。因此，为了获得这个确切数字 x，我们假设对于任何分支fib(n)，O(n)为 x^n。因此 x^n = x^n-1 + x^n-2。 - Lucia

Answer 3

我同意pgaur和rickerbh的观点，递归斐波那契的时间复杂度为O(2^n)。

我通过一种相当简单但我认为仍然有效的推理得出了相同的结论。

首先，关键是要弄清楚在计算第N个斐波那契数时，递归斐波那契函数（从现在开始记为F()）被调用的次数。如果它每个数字都被调用一次，我们就有O(n)；如果它每个数字都被调用n次，那么我们就得到了O(n*n)，或O(n^2)，以此类推。

因此，当F()被调用一个数字n时，0到n-1之间的数字中给定数字调用F()的次数随着我们接近0而增加。

初步印象是，如果我们把它以视觉方式呈现出来，对于给定数字调用F()的每个时间单位，我们会得到一种金字塔形状（也就是说，如果我们在水平方向上居中单位）。大致像这样：

n              *
n-1            **
n-2           ****  
...
2           ***********
1       ******************
0    ***************************

现在的问题是，当n增长时，这个金字塔底部加粗的速度有多快？

让我们拿一个真实的例子来说，比如F（6）。

F(6)                 *  <-- only once
F(5)                 *  <-- only once too
F(4)                 ** 
F(3)                ****
F(2)              ********
F(1)          ****************           <-- 16
F(0)  ********************************    <-- 32

我们可以看到 F(0) 被调用了 32 次，这相当于 2^5，在这个示例中是 2^(n-1)。

现在，我们想知道 F(x) 总共被调用的次数，而我们可以看到 F(0) 被调用的次数只是其中的一部分。

如果我们将 F(6) 到 F(2) 行中的所有 * 移动到 F(1) 行中，我们会发现 F(1) 和 F(0) 的行长度现在相等。这意味着，当 n=6 时，F() 被调用的总次数为 2x32=64=2^6。

现在，就复杂度而言：

O( F(6) ) = O(2^6)
O( F(n) ) = O(2^n)

- J.P.

---

F(3) 只会被调用 3 次而不是 4 次。第二个金字塔是错误的。 - Avik

F(3) = 3，F(2) = 5，F(1) = 8，F(0) = 5。我希望修正它，但我认为我无法通过编辑来挽救这个答案。 - Bernhard Barker

Answer 4

在MIT的这篇文章中，对于这个特定问题进行了非常好的讨论。第5页指出，如果假设一个加法需要一个计算单元，则计算Fib(N)所需的时间与Fib(N)的结果非常密切相关。

因此，您可以直接跳转到斐波那契数列的非常接近的近似值：

Fib(N) = (1/sqrt(5)) * 1.618^(N+1) (approximately)

因此可以说，朴素算法的最坏情况性能为

O((1/sqrt(5)) * 1.618^(N+1)) = O(1.618^(N+1))

PS: 如果您想了解更多信息，可以在维基百科上查看 第N个斐波那契数的闭合形式表达式 的讨论。

- Bob Cross

Answer 5

您可以展开它并进行可视化呈现。

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

     = 2*T(n-1)   
     = 2*2*T(n-2)
     = 2*2*2*T(n-3)
     ....
     = 2^i*T(n-i)
     ...
     ==> O(2^n)

- Tony Tannous

---

我理解第一行。但为什么末尾有一个小于符号<？你是怎么得到T(n-1) + T(n-1)的？ - Quazi Irfan

@QuaziIrfan ：这是一个箭头。-> [(不小于)。对于最后一行的混淆表示抱歉]。至于第一行，嗯... T(n-1)>T(n-2)，所以我可以改变T(n-2)并放置T(n-1)。我只会得到一个仍然适用于T(n-1)+T(n-2)的更高上界。 - Tony

Answer 6

通过绘制递归树，可以更好地估计递归算法的时间复杂度。在这种情况下，绘制递归树的递推关系为T(n)=T(n-1)+T(n-2)+O(1)。请注意，每个步骤都需要O(1)的常数时间，因为它只在if块中进行一次比较来检查n的值。递归树如下所示：

          n
   (n-1)      (n-2)
(n-2)(n-3) (n-3)(n-4) ...so on

假设我们用i来表示上述树的每个级别, 因此,

i
0                        n
1            (n-1)                 (n-2)
2        (n-2)    (n-3)      (n-3)     (n-4)
3   (n-3)(n-4) (n-4)(n-5) (n-4)(n-5) (n-5)(n-6)

假设在特定的i值处，树结束，这种情况发生在n-i=1时，因此i=n-1，这意味着树的高度为n-1。 现在让我们看看每个n层树中需要完成多少工作。请注意，每个步骤都需要O(1)时间，如递归关系所述。

2^0=1                        n
2^1=2            (n-1)                 (n-2)
2^2=4        (n-2)    (n-3)      (n-3)     (n-4)
2^3=8   (n-3)(n-4) (n-4)(n-5) (n-4)(n-5) (n-5)(n-6)    ..so on
2^i for ith level

由于 i=n-1 表示树的高度，因此每个层级的工作量将是：

i work
1 2^1
2 2^2
3 2^3..so on

因此，总工作量将是每个级别完成的工作量的总和，因此它将是2^0+2^1+2^2+2^3...+2^(n-1)，其中i=n-1。通过等比数列求和公式可得，这个总和为2^n。因此，这里的总时间复杂度为O(2^n)。

- nikhil kekan

---

当我看调用树时，我发现每一轮都会翻倍。 1、3、7、15…… 每个下一级（即下一个i）再次翻倍。 它可以翻倍多少次？~N次（直到N“完成”） 因此，您需要将树中每个级别的总调用乘以222*2... N次，即O(2^N)。 - David Constantine

我认为，为了更清晰明了，每个树层的节点应该是O(1)，而不是O(n)，因为T(n) = T(n-1) + T(n-2) + O(1)，而不是T(n-1) + T(n-2) + O(n)。 - sundaycat

Answer 7

证明的答案很好，但我总是要手动进行几次迭代才能真正让自己信服。所以我在白板上画了一个小的调用树，并开始数节点。我把计数分成总节点数、叶子节点数和内部节点数。这是我的结果:

IN | OUT | TOT | LEAF | INT
 1 |   1 |   1 |   1  |   0
 2 |   1 |   1 |   1  |   0
 3 |   2 |   3 |   2  |   1
 4 |   3 |   5 |   3  |   2
 5 |   5 |   9 |   5  |   4
 6 |   8 |  15 |   8  |   7
 7 |  13 |  25 |  13  |  12
 8 |  21 |  41 |  21  |  20
 9 |  34 |  67 |  34  |  33
10 |  55 | 109 |  55  |  54

立即显而易见的是，叶子节点的数量为fib(n)。稍微再迭代几次才会注意到内部节点的数量为fib(n) - 1。因此总节点数为2 * fib(n) - 1。

由于在计算复杂度时舍去系数，最终答案为θ(fib(n))。

- benkc

---

（不，我没有在白板上画出完整的10层调用树。只有5层。）;) - benkc

不错，我一直在想递归斐波那契数列需要多少额外的加法操作。它不仅仅是将1加到单个累加器中Fib(n)次，而且有趣的是它仍然完全符合θ(Fib(n))。 - Peter Cordes

请注意，某些（大多数）递归实现会花费时间添加“0”，因为递归基本情况是“0”和“1”，因为它们执行“Fib(n-1)+Fib(n-2)”。因此，可能来自此链接唯一答案的“3 * Fib(n) - 2”对于节点的总数更准确，而不是“2 * Fib(n) - 1”。 - Peter Cordes

我无法在叶节点上获得相同的结果。从0开始：F(0) -> 1个叶子（它本身）; F(1) -> 1个叶子（它本身）; F(2)-> 2个叶子（F(1)和F(0)）; F(3) -> 3个叶子; F(5) -> 8个叶子; 等等。 - alelom

Answer 8

这个实现在下界上受到2^(n/2)的限制，在上界上受到2^n的限制（正如其他评论中所提到的）。而该递归实现的一个有趣事实是它具有Fib(n)本身的紧密渐进界限。这些事实可以总结如下：

T(n) = Ω(2^(n/2))  (lower bound)
T(n) = O(2^n)   (upper bound)
T(n) = Θ(Fib(n)) (tight bound)

如果您愿意，可以使用其闭式进一步减少紧密约束。

- Dave L.

Answer 9

纯粹递归实现的斐波那契数列由于计算中的重复操作而呈指数级增长：

在根节点处进行计算：

F(n) 依赖 F(n-1) 和 F(n-2)

F(n-1) 再次依赖 F(n-2) 和 F(n-3)

F(n-2) 再次依赖 F(n-3) 和 F(n-4)

每一层都有两个递归调用，浪费了大量计算时间和数据，时间函数如下：

T(n) = T(n-1) + T(n-2) + C，其中C是常数

T(n-1) = T(n-2) + T(n-3) > T(n-2)，因此

T(n) > 2*T(n-2)

...

T(n) > 2^(n/2) * T(1) = O(2^(n/2))

这只是一个下界，对于你的分析目的应该足够了，但真正的时间函数是同样的斐波那契公式的常数倍，而且闭合形式已知是黄金比例的指数级。

此外，你可以使用动态规划找到优化版本的斐波那契数列，如下所示：

static int fib(int n)
{
    /* memory */
    int f[] = new int[n+1];
    int i;

    /* Init */
    f[0] = 0;
    f[1] = 1;

    /* Fill */
    for (i = 2; i <= n; i++)
    {
        f[i] = f[i-1] + f[i-2];
    }

    return f[n];
}

这个算法经过优化，只需n步就能完成，但是时间复杂度仍然是指数级的。

成本函数是从输入大小到解决问题所需步骤的定义。当你看到斐波那契数列的动态版本（需要n步来计算表格）或者判断一个数是否为质数的最简单算法（需要sqrt(n)来分析该数的有效除数），你可能认为这些算法的时间复杂度是O(n)或O(sqrt(n))，但实际上并不是这样，原因如下：

你的算法的输入是一个数字：n，使用二进制表示法，整数n的输入大小为log2(n)，然后进行变量替换。

m = log2(n) // your real input size

让我们找出步数与输入大小的关系函数。

m = log2(n)
2^m = 2^log2(n) = n

如果以输入大小为函数，您的算法成本为：

T(m) = n steps = 2^m steps

这就是为什么成本呈指数增长的原因。

- Miguel

Answer 10

通过绘制函数调用图很容易进行计算。只需将每个n值的函数调用相加，并查看数字增长方式即可。

大O表示法为O(Z ^ n)，其中Z是黄金比例（约为1.62）。随着n的增加，无论是Leonardo数还是Fibonacci数都逐渐接近这个比率。

与其他大O问题不同的是，输入没有变化，而且算法和算法实现都清晰明确。

不需要进行复杂的数学运算。只需绘制下面的函数调用图并将函数拟合到数字上。

或者如果您熟悉黄金比例，您将认识到它是这样的。

这个答案比被接受的答案更正确，后者声称它将趋近于f(n)=2^n。它永远不会这样，它将趋近于f(n)=golden_ratio^n。

2 (2 -> 1, 0)

4 (3 -> 2, 1) (2 -> 1, 0)

8 (4 -> 3, 2) (3 -> 2, 1) (2 -> 1, 0)
            (2 -> 1, 0)


14 (5 -> 4, 3) (4 -> 3, 2) (3 -> 2, 1) (2 -> 1, 0)
            (2 -> 1, 0)

            (3 -> 2, 1) (2 -> 1, 0)

22 (6 -> 5, 4)
            (5 -> 4, 3) (4 -> 3, 2) (3 -> 2, 1) (2 -> 1, 0)
                        (2 -> 1, 0)

                        (3 -> 2, 1) (2 -> 1, 0)

            (4 -> 3, 2) (3 -> 2, 1) (2 -> 1, 0)
                        (2 -> 1, 0)

- bob

---

你能提供任何关于黄金比例的声明来源吗？ - Nico Haase