Space 递归调用的复杂性

Question

我正在阅读 Cracking the Code Interview 第 6 版，我对第 45 页的内容有疑问。

有一个这样的示例算法：

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

对于算法，它给出了以下评论：

The space complexity of this algorithm will be O(N). Although we have O(2^N) nodes in the tree total, only O(N) exist at any given time. Therefore, we would only need to have O(N) memory available.

我真的不明白为什么在任何给定时间只存在 O(N)。他们不应该都在调用堆栈中吗？有人可以解释一下吗？

Answer 1

理解这一点的更好方法可能是绘制调用树，而不是调用堆栈。

调用树表示在函数的生命周期内进行的所有调用。 f(n) 下面会有两个分支。每一个都有你进行的函数调用

在 f(n) 的调用下面有两个计算 f(n-1) 的调用。在每个下面还有 2 个 f(n-2)。等等。

如果在单独调用内部你需要固定数量的内存和固定数量的工作（在子调用中花费更多的时间和工作），那么这棵树的大小代表你必须做的工作总量运行程序。那将是 1 + 2 + 4 + ... + 2**n = (1 - 2**(n+1))/(1-2) = O(2**n).

然而，您在任何给定时间可能需要的最大内存量是树的深度。因为一旦你 return 从一个电话中，你就完成了它并丢弃了所需的内存。树的最大深度为 n，每次调用计算时都会达到 f(1)。所以你可以分配、存储、计算一些东西，然后把它扔掉，然后当你需要再次分配它时它就可用了。一遍又一遍。

尝试为 n=3 画图，然后完成计算，您就会明白这一点。随着您的进步，您正在分配和释放内存。因此，您可以一遍又一遍地重复使用相同的内存，而不必使用大量内存。

Answer 2

它看起来像指数 space 复杂度 O(2^n) 因为为了完成 f() 我们需要两次递归：

#4: f(4)
#3: (f(3) + f(3))
#2: (f(2) + f(2)) + (f(2) + f(2))
#1: ((f(1) + f(1)) + (f(1) + f(1))) + ((f(1) + f(1)) + (f(1) + f(1)))

正如我们所见，递归次数呈指数增长，因此 space 复杂度看起来像 O(2^n).

另一方面，我们不会同时调用这两个函数。其实我们会完成第一次递归调用，拿到值然后完成第二次递归调用：

#4: f(4)
#3: f(3)
#2: f(2)
#1: f(1)

#4: f(4)
#3: f(3)
#2: f(2)
#1: (1 + f(1))

#4: f(4)
#3: f(3)
#2: f(2)
#1: (1 + 1) = 2

#4: f(4)
#3: f(3)
#2: (2 + f(2))
...

所以在任何给定时间，我们只需要 O(n) space + O(n) 作为临时值。

因此，此函数具有 O(n) space 复杂性和 O(2^n) 计算复杂性，即递归。

我想这就是作者的意思。

Space 递归调用的复杂性

Space complexity for recursive calls

algorithm

space-complexity