递归调用的空间复杂度

Question

我正在阅读Cracking the Code Interview 6th Edition并且对第 45 页上的某些内容有疑问。

有一个这样的示例算法：

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

对于算法，它给出了以下注释：

该算法的空间复杂度为 O(N)。尽管我们在树中总共有 O(2^N) 个节点，但在任何给定时间只存在 O(N) 个节点。因此，我们只需要 O(N) 可用内存。

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

Answer 1

它看起来像指数空间复杂度，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)))

正如我们所看到的，递归次数呈指数增长，因此空间复杂度看起来像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)空格 +O(n)作为临时值。

因此，该函数具有O(n)空间复杂度和O(2^n)计算复杂度，即递归。

我想这就是作者的意思。

Answer 2

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

调用树表示在函数的生命周期内进行的所有调用。下面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)。

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

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