斐波那契数列递归 space 复杂度

Question

public int fib(int n) {
if (n == 0) return 0; 
if (n == 1) return 1; 
return fib(n-1) + fib(n-2);
}

我很困惑为什么上面代码的 space 复杂度是 O(n)。现在，我知道递归的深度是n，也就是树的高度。

没有创建临时变量或最终结果变量。 space 这里的复杂度是从函数调用堆栈计算出来的吗？

Answer 1

是的，这种情况下的 space 复杂度取决于调用堆栈中使用的 space，这取决于活动函数调用的数量（已调用但未完成执行的函数）。

如果您观察到最后一条语句

return fib(n-1) + fib(n-2)

计算fib(n-1)时使用O(n)space。一旦 fib(n-1) 完成执行堆栈 space 可以被 fib(n-2) 重用。

因此，在这种情况下，任何时候调用 fib(n) 的活动堆栈帧数为 O(n)，因此 space 复杂度为 O(n) .

值得注意的是，时间复杂度是指数级的。

Fibonacci sequence recursion space complexity