为什么创建调用 O(h) 的二叉树的递归方法的复杂性 space？

Question

鉴于此方法：

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

创建堆栈 call/binary 树，如下所示：

      n
     /  \
   n-1   n-1
 /   \  /   \
n-2 n-2 n-2 n-2 etc

例如。 n = 3

      3
     /  \
   2     2
  / \    / \
 1   1   1   1
/ \ / \ / \ / \
0 0 0 0 0 0 0 0

2^(n + 1) - 1 => 15 nodes/calls。时间复杂度为 O(2^n)

我的问题是，为什么 space complexity = O(h)，h 表示树的高度，在示例中为 3？换句话说，如果每个方法调用有 1 个内存 space 用于输入变量 n，那么我们可以说对于每个方法调用，有 1 个内存 space。如果有 O(2^n) 次方法调用，那么为什么 space 不等于 O(2^n)？我的参考资料说 "only O(N) exists at any given time"，这对我来说没有意义。

我认为堆栈帧代表一个方法调用、它的参数和变量，以及它的调用者的 return 地址。这可能是我困惑的根源。

Answer 1

重要的是要注意这不是 concurrent/parallel 算法，因此计算函数输出的步骤的最终可视化不是同时发生的。

如果我们像这样重写算法，可能会更明显：

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

  int temp1 = f(n - 1);
  int temp2 = f(n - 1);
  return temp1 + temp2;
}

因此对第一个 f(n - 1) 和第二个 f(n - 1) 的调用不会同时发生。

这意味着在任何给定的时间点，我们都有一个线性调用堆栈，如下所示：

      f(3)
     / 
    f(2)   
   /  
  f(1) 
 /
f(0)

此时，我们有一个大小为 4 的调用堆栈。当计算 f(0) 时，最后一个元素元素从堆栈中弹出，我们将有一个大小为 3 的调用堆栈：

      f(3)
     / 
    f(2)   
   /  
  f(1)

此时，算法计算对f(1)的第二次调用（f(1)的右子树）：

      f(3)
     / 
    f(2)   
   /  
  f(1)
  \
   f(0)

我们再次拥有大小为 4 的调用堆栈。在接下来的几步中，调用堆栈将转换为：

      f(3)
     / 
    f(2)   
   /  
  f(1)

然后：

      f(3)
     / 
    f(2)

然后：

      f(3)
     / 
    f(2)
    \
     f(1)

然后：

      f(3)
     / 
    f(2)
    \
     f(1)
    /
   f(0)

然后：

      f(3)
     / 
    f(2)
    \
     f(1)

然后：

      f(3)
     / 
    f(2)
    \
     f(1)
      \
       f(0)

这个过程一直持续到算法完成。

因此，我们可以得出结论，该算法的 space 复杂度为 O(h).

为什么创建调用 O(h) 的二叉树的递归方法的复杂性 space？

Why is the space complexity of a recursive method that creates a binary tree of calls O(h)?

algorithm

recursion

time-complexity

space-complexity