algorithm - 调用堆栈中的空间复杂度

Question

我正在阅读 Cracking the Coding Interview，在这本书的大 O 部分，我们看到了这段代码:

int pairSumSequence(int n){

    int sum = 0;
    for(int i = 0; i < n; i++){
        sum += pairSum(i, i + 1);
    }
    return sum;
}

int pairSum(int a, int b) {
    return a + b;
}

现在，我明白时间复杂度是 O(n)，因为很明显执行时间随着 int n 大小的增加而增加。但书中继续指出:

"...However, those calls [referring to calls of pairSum] do not exist simultaneously on the call stack, so you only need O(1) space."

这是我不明白的部分。为什么这个算法的空间复杂度是O(1)？作者的意思到底是什么？在我最初的分析中，我假设因为 pairSum() 被调用 N 次，所以这些调用将被连续添加到调用堆栈中，因此会占用调用堆栈中的 N 个空间。非常感谢。

Answer 1

这意味着该算法使用的空间量相对于输入大小是恒定的。

是的，pairSum 被调用了 N 次。然而，它占用 O(1) 空间，因为正如书中所说，没有两个调用是同时完成的。

粗略地说，在循环的每次迭代中:

1. pairSum 被调用。它使用恒定数量的堆栈空间。

2. 它返回。之后它不占用任何堆栈空间。

因此，该算法在任何时候都只使用固定数量的空间(它不依赖于n)。