time-complexity - 递归运行时 - 空间复杂性(Cracking the Coding Interview 第 44 页)

Question

上页。 Cracking the Coding Interview 的 44，有如下算法:

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

书上说这具有 O(2^n) 的时间复杂度和 O(n) 的空间复杂度。我得到了时间复杂度部分，因为创建了 O(2^n) 个节点。我不明白为什么空间复杂性也不是那样。书上说因为这是因为在任何给定时间只存在 O(n) 个节点。

怎么可能呢？当我们处于 f(1) 的底层时，调用堆栈不会包含所有 2^n 次调用吗？我错过了什么？

如果我可以提供更多详细信息，请告诉我。

谢谢，

Answer 1

没有。第二次调用 f(n-1) 直到第一次调用返回后才会发生，因此它们不会同时占用堆栈空间。当第一个返回时，它的堆栈空间被释放并可以重新用于第二个调用。

这同样适用于递归的每一层。使用的内存与调用树的最大深度成正比，而不是节点总数。