以下代码的空间复杂度是多少？

Question

以下代码的空间复杂度是多少？

def f(n):
    sum = 0
    if n == 0:
        return 1
    else:
        for i in range(n):
            sum = sum + f(i)
    return sum

所以，这是一个递归函数，我认为由于每个函数都调用它下面的所有函数，空间复杂度将是 O(n!)，因为堆栈将维护所有函数调用。但正确答案是 O(n)。有人可以详细解释一下吗？

Answer 1

为了确定这段代码的空间复杂度，我们来分析一下内存使用情况。

代码定义了一个函数

f(n)

，它递归地调用自身

n

次。在每次递归调用中，都会创建一个变量

sum

来存储递归调用结果的总和。

由于递归调用是嵌套的，因此将创建

sum

变量的多个实例。实例的数量取决于递归的深度，而递归的深度由输入决定

n

。

我们来分解一下空间复杂度：

• 无论输入大小

  sum

  如何，

  n

  变量的每个实例所需的空间都是恒定的。
• 递归的最大深度为

  n

  ，这意味着在代码执行期间的任何给定时间最多可以有

  n

  变量的

  sum

  实例。

因此，代码的空间复杂度为 O(n)，因为所需的空间与输入大小成线性比例

n

。