algorithm - 为什么创建调用二叉树的递归方法的空间复杂度为 O(h)？

Question

给定这个方法:

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

像这样创建堆栈调用/二叉树:

      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 个节点/调用。时间复杂度为 O(2^n)

我的问题是，为什么空间复杂度 = O(h)，h 表示树的高度，在示例情况下为 3？换句话说，如果每个方法调用都有 1 个内存空间用于输入变量 n，那么我们可以说对于每个方法调用，都有 1 个内存空间。如果有 O(2^n) 次方法调用，那么为什么空间不等于 O(2^n)？我的引用资料说“在任何给定时间只存在 O(N)”，这对我来说没有意义。

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

Answer 1

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

如果我们像这样重写算法，它可能会变得更明显:

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)

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

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