递归调用的空间复杂度

Question

我正在阅读《破解面试官》，关于第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)个节点存在。它们难道不都在调用堆栈中吗？有人能解释一下吗？

- Kou Chibin

---

@TimBiegeleisen 在几种编程语言中，** 表示指数运算，因为 ^ 已经被用于异或运算。所以在你可能更熟悉的表示法中，这就是 O(2^N)。 - btilly

请提供关于 https://dev59.com/6FwX5IYBdhLWcg3wnwnd 的相关或重复问题。 - jdhao

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)，即递归。

我想这就是作者所说的意思。

- Andriy Berestovskyy

---

好的解释！谢谢您！ - Kou Chibin

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 绘制图片，然后按顺序进行计算，您将看到这一点。随着进展，您既在分配内存又在释放内存。因此，您可以重复使用相同的内存，而不必使用大量的内存。

- btilly

---

很好的一点是，在任何给定时间使用的内存量就是树的深度。谢谢！ - Kou Chibin