Fibonacci序列递归空间复杂度

Question

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

我不明白为什么上述代码的空间复杂度是O(n)。现在，我知道递归的深度是n，也就是树的高度。

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

Answer 1

是的，在这种情况下，空间复杂性取决于调用堆栈中使用的空间，这取决于活动函数调用的数量(函数被调用，但未完成执行)。

如果你观察到最后的陈述

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

当计算fib(n-1)时，使用O(n)空间。一旦fib(n-1)完成，fib(n-2)就可以重用堆栈空间了。

因此，在这种情况下，在任何时候调用fib(n)的活动堆栈帧的数目都是O(n)，因此空间复杂性是O(n)。

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