为什么下面的代码只有 O(N) 的空间复杂度？

Question

这直接取自 Gayle Lakmaan McDowell 的 Cracking the coding interview。

她列出了以下代码：

 int f(int n) {
 if(n<=1){
   return 1;
  }
 return f(n-1) + f(n-1);
}

她清楚地解释了为什么时间复杂度是 O(2^n)，但为什么这里的空间复杂度只有 O(N)？

Answer 1

空间复杂度考虑了调用堆栈的使用。该函数O(N)在返回之前会调用自身多次，因此调用堆栈会O(N)很深。

更新（感谢@MatthewWetmore）：

澄清一下，f(n-1) + f(n-1);表达式中的两个递归调用不是并行执行的。第一次调用完成，消耗线性堆栈使用量，然后第二次调用，消耗相同的堆栈大小。因此不会发生空间加倍，这与运行时消耗（显然每次调用都会累积）不同。