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

Question

这是Cracking the Coding Interview(第5版)中Fibonacci序列的递归实现

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)？

Answer 1

递归实现的时间复杂度近似为 2 square n (2^n)，这意味着该算法必须经过大约 64 个计算步骤才能获得第 6 个斐波那契数。这是巨大的并且不是最优的，大约需要程序1073741824个计算步骤才能得到斐波那契数30，一个很小的数，这是不可接受的。实际上，迭代方法绝对是更好和优化的方法。

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

这是因为，乍一看，递归执行的函数调用似乎是并发执行的，但实际上，它们是顺序执行的。

顺序执行保证堆栈大小永远不会超过上面所示的调用树的深度。程序首先执行所有最左边的调用，然后向右转，当 F0 或 F1 调用返回时，它们相应的堆栈帧将被弹出。

下图中，每个矩形代表一个函数调用，箭头代表程序到达递归终点所采取的路径：

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

程序将遵循相同的执行模式，从父级到子级，并在执行 left 和 right 调用后返回父级，直到到达所有 F4 的最后一个根父级，将计算出的斐波那契数和为 3。

Answer 2

这是一个提示.使用print语句修改代码,如下例所示:

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);
}

现在在main中执行以下行:

Fibonacci(6,1);

打印出来的"堆栈"的最高值是多少.你会看到它是"6".尝试"i"的其他值,您将看到打印的"堆栈"值永远不会超过传入的原始"i"值.

由于Fib(i-1)在Fib(i-2)之前被完全评估,因此永远不会有多于i递归的级别.

因此,O(N).

Answer 3

如果其他人仍然感到困惑,请务必查看此Youtube视频,该视频讨论了生成Fibonacci序列的空间复杂性.斐波纳契空间复杂性

演示者非常清楚为什么空间复杂度为O(n),递归树的高度为n.

Answer 4

正如我所看到的，该过程一次只会下降一个递归。第一个 (f(i-1)) 将创建 N 个堆栈帧，另一个 (f(i-2)) 将创建 N/2。所以最大的是N。另一个递归分支不会使用更多的空间。

所以我想说空间复杂度是N。

事实上，一次仅计算一次递归，这使得 f(i-2) 可以被忽略，因为它小于 f(i-1) 空间。