一个递归斐波那契算法的空间复杂度是多少？

Question

这是来自《破解面试：第5版》的斐波那契数列递归实现

int fibonacci(int i) {
       if(i == 0) return 0;
       if(i == 1) return 1;
       return fibonacci(i-1) + fibonaci(i-2);
}

观看了关于这个算法时间复杂度的视频“斐波那契时间复杂度”后，我现在明白为什么这个算法的运行时间是O(2ⁿ)。然而，我还在分析空间复杂度方面有困难。

我在网上查阅到了这方面的信息，并有一个问题。

在这个Quora主题中，作者表示：“在您的情况下，您有n个堆栈帧f(n), f(n-1), f(n-2),...，f(1)和O(1)。”你不会有2n个堆栈帧吗？比如f(n-2)，一个框架将用于实际调用f(n-2)，但是从f(n-1)中也会有一个调用f(n-2)的调用，对吗？

- committedandroider

---

常数因素在大O复杂度中并不重要——O(n)和O(2n)是相同的。话虽如此，栈帧在第一次调用返回后会被回收和重用于第二次调用。 - Chris Dodd

这是LaTeX数学符号，意思是2的n次方吗？你是不是指2乘以n？ - chrisinmtown

@chrislott，你能修改一下MathJax吗？我的意思是2的n次方。 - committedandroider

@ChrisDodd 所以在计算机中，f(n-2)有一个堆栈帧，并且由于有两个调用，它会被使用两次吗？ - committedandroider

@committedandroider：与MathJax相比，HTML显得非常糟糕。但这是我们唯一拥有的东西。我自由地使用<sup>和<sub>标签，用_包围变量名使它们成为斜体，并记忆一些实体，例如α和→。如果你需要更多，有些服务可以将MathJax渲染为png格式，你可以上传图片。 - rici

Answer 1

这里有一个提示。请按照以下示例，在您的代码中添加打印语句：

int fibonacci(int i, int stack) {
    printf("Fib: %d, %d\n", i, stack);
    if (i == 0) return 0;
    if (i == 1) return 1;
    return fibonacci(i - 1, stack + 1) + fibonacci(i - 2, stack + 1);
}

现在在主函数中执行此行：

Fibonacci(6,1);

打印出的“stack”的最高值是多少。你会发现它是“6”。尝试其他“i”值，你会发现打印的“stack”值从未超过传入的原始“i”值。

由于在计算Fib（i-1）之前完全评估了Fib（i-2），因此递归层数永远不会超过i个。

因此，时间复杂度为O（N）。

- selbie

---

@committedandroider 我通常称其为 depth 而不是 stack。它跟踪递归的层数，以便 printf 可以显示它。(你也可以用它来限制递归深度，但这里不需要。) - user3386109

空间复杂度更依赖于递归层数还是栈帧数量？ - committedandroider

每个递归层级都会有一个栈帧，所以所使用的空间等于“最深层次的递归”乘以“每个层级的栈帧大小”。由于每个层级的栈帧大小是一个固定的乘数，因此在复杂度分析中被忽略，因此空间复杂度只取决于“最深层次的递归”。 - user3386109

所以，如果我们看一个更简单的例子，比如f(4,1)，我注意到两个f调用，f(3,2)和f(2,2)处于同一递归层次。这是否意味着它们使用相同的堆栈帧？ - committedandroider

@committedandroider 是和不是。f(3,2) 实例会设置一个栈帧。当 f(3,2) 返回时，该栈内存将被回收。对 f(2,2) 的调用将在同一内存位置上设置另一个栈帧。因此，它们是否使用相同的栈帧取决于您如何定义“相同的栈帧”。 - user3386109

Answer 2

递归实现的时间复杂度约为2^n，这意味着为了得到第六个斐波那契数，该算法将需要大约经过64次计算步骤。这是巨大的且不是最优的，要得到一个小数字30的斐波那契数，程序将需要大约1073741824个计算步骤，这是不能接受的。实际上，迭代方法明显更好和更优化。

了解了这种实现的时间复杂度后，人们可能会认为其空间复杂度可能相同，但事实并非如此。该实现的空间复杂度等于O(n)，并且从不超过它。那么，让我们揭开“为什么”的神秘面纱。

这是因为被递归执行的函数调用可能似乎在并发执行，但实际上它们是顺序执行的。

顺序执行保证堆栈大小永远不会超过上述调用树的深度。程序通过在转向右侧之前执行所有最左侧的调用来开始运行，当F0或F1调用返回时，它们对应的堆栈帧被弹出。

在下图中，每个矩形代表一个函数调用，箭头表示程序到达递归结尾的路径：

我们可以注意到，当程序到达调用 F4F3F2F1 并返回 1 时，它会返回到其父调用 F4F3F2 来执行右递归子调用 F4F3F2F0，在 F4F3F2F0 和 F4F3F2F1 调用都返回后，程序返回到 F4F3。因此，栈大小永远不会超过最长路径 F4F3F2F1 的大小。

程序将按照相同的执行模式进行，从父节点到子节点，执行左右调用后返回到父节点，直到到达所有 F4 的最后根父节点，带着斐波那契数列的计算和 3。

- isqo

---

我认为这个答案应该被接受。 - Hang Chen

Answer 3

依据我的理解，该过程一次只能下降一个递归。 第一个递归（f(i-1)）将创建N个堆栈框架，另一个递归（f(i-2)）将创建N/2个。 因此最大值为N。其他递归分支不会使用更多的空间。

因此，我认为空间复杂度为N。

事实上，只有一个递归被评估一次，这使得f(i-2)可以被忽略，因为它比f(i-1)的空间小。

- Richard

---

哦，是因为另一个 f(i-2) 会等待第一个 f(i-1) 完成吗？ - committedandroider

@committedandroider。是的，在每个级别上，所有f(i-1)在f(i-2)开始之前都会被执行。请注意，较低级别的f(i-2)将作为下一个更高级别的f(i-1)的一部分进行评估。 - Richard

Answer 4

如果你跟随每个递归到达它的终点，它总是在斐波那契树上最多只有一条路径。堆栈会像这样发展（红色边缘表示一个值被存储在内存中）：

等等……

对于一棵完全二叉树，每条路径的长度为log_2(X)，其中X是节点数。现在输入的总数为n，则X=2^n。这意味着每条路径的长度为log_2(2^n)= n。

- Adam

Answer 5

递归斐波那契算法的空间复杂度将是树的高度，即O(n)。

技巧：只有相互链接的调用才会同时存在于堆栈中，因为前一个调用将等待下一个调用执行，并且这些调用应该在同一时间相互链接。

- Nitin Sharma