Space CTCI 书中递归算法的复杂性

Question

我正在阅读 CTCI 的书，但无法理解其中的一个示例。他们开始于：

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

并说明这是 O(n) 时间和 O(n) space 因为每个调用都被添加到调用堆栈并占用实际内存。

下一个例子是：

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

并指出时间复杂度为 O(2^n)，space 为 O(n)。虽然我明白为什么时间是 O(2^n)，但我不确定为什么 space 是 O(n)？他们的解释是"only O(n) nodes exists at any given time"。为什么我们不计算每个调用堆栈占用的 space，就像第一个示例中那样？

P.S。在阅读了类似的问题之后，我是否应该假设一旦我们开始向后（或向上）递归，堆栈框架的 space 就会被回收？

Answer 1

与时间复杂度不同，时间复杂度只是运行程序所需的总时间，space 复杂度描述了执行程序所需的 space。所以程序的执行树中有2ⁿ个节点其实并不重要。调用堆栈自动折叠并释放使用的额外内存。重要的是调用树的最大深度，对于这个程序来说是 O(n)。不过，应该注意的是，递归是一种特殊情况，它会在堆栈折叠时自然释放所有已用内存。如果内存在运行时间内显式分配，则也应显式释放。

关于第一个例子，调用树只是一个深度为 n 的列表，导致类似的复杂度为 O(n)。

Space CTCI 书中递归算法的复杂性

Space complexity of a recursive algorithm from the CTCI book

time-complexity

big-o

space-complexity