递归算法的空间复杂度通常如何计算？

Question

int factorial(int n)
{
    if(n < 0)  {return -1;}
    if(n == 0) {return  1;}
    return n*factorial(n-1);
}

为了确定时间复杂度，我建立了一个递归关系。

T(n) = T(n-1) + c = T(n-2) + 2c = ... = T(n-k) + kc => O(n)
T(0) = 1;

对于那种算法(比如斐波那契数列)，一般的找到空间复杂度的方法是什么？我们需要找到调用栈的深度吗？

- user6011767

---

你需要递归调用它n次，每次调用都会在堆栈上分配自己的帧和局部变量，因此空间复杂度为O(n)。 - Evk

每次调用factorial函数都会在内存的“堆栈”部分创建一个堆栈帧以供该调用使用。单个堆栈帧将包含在此函数中定义的变量、函数中的参数和返回地址。在这种情况下，对于每个调用，存储这些信息可以在常数时间内完成。由于对该函数的调用数量是线性的，因此总内存将为O(n)。 - Shubham

Answer 1

递归算法所需的空间可以近似为三个元素。所需存储的空间包括：

• 递归栈
• 输入函数的参数
• 函数的输出结果

例如阶乘的递归公式为T(n) = T(n-1) + c，展开后得到T(n) = T(n-1) + T(n-2) + ... + n c。因此递归栈需要O(n)的空间。

函数的输出结果为n!，要存储一个数字n，需要log(n)位。因此存储结果需要log(n!) = O(n log n)的空间。

在每一步递归中，需要存储1个参数（n）。需要存储n次，每个参数占用log(n)的空间。因此总共需要O(nlogn)的空间。

综上所述，所需的空间为O(n) + O(nlogn) + O(nlogn) = O(nlogn)。这就是计算阶乘递归所需的空间。

通过这种分析方法，可以找出为什么进行alpha-beta剪枝的国际象棋程序需要大量内存来正确计算位置。

- Salvador Dali

---

我理解了你的解释，但为什么其他人都说空间复杂度是O(n)呢？ - user6011767

@ivan_petrushenko 问一下他们存储数字 n! 需要多少空间。我们选一个小的数字 n，比如5000。他们会说这是 O(1) 吗？ - Salvador Dali

对于大量的 n 值，空间复杂度将不是线性的，时间复杂度也会如此（我猜），因为在 return n*factorial(n-1) 中，乘以两个非常大的数字不能被视为一个常数时间操作。我写了 O(n)，因为我认为既然 OP 使用的是 int，那么它就无法存储大于 19! 的数字。 - Shubham

Answer 2

在编写时间复杂度的形式时，你可以这样：

T(n) = T(n - 1) + n

或者

T(n) = 2T(n/2) + nlogn

等等。

你有两个选择：

1）使用重复代入法，对于某些情况需要一些数学技巧，因为你需要按照步骤一直追踪到T(1)或T(0)，然后计算一个求和。

或者

2）使用主定理，它类似于一个公式主定理，适用于许多实际情况。

- A. Mashreghi