求 space 递归算法复杂度的一般方法是什么？

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;

找到这种算法（如斐波那契）的 space 复杂度的一般方法是什么？我们需要找到调用堆栈的深处？

Answer 1

一个递归算法所需要的space可以用三个元素来近似。 Space 需要存储

在阶乘的例子中。递归公式为T(n) = T(n-1) + c。展开它时你会得到 T(n) = T(n-1) + T(n-2) + ... + n c。所以递归栈需要O(n)space。

函数的输出将是 n!，要存储一个数字 n，您需要 log(n) 位。因此，要存储结果，您需要 log(n!) = O(n log n) space.

在递归的每个步骤中，您需要存储 1 个参数 (n)。您将需要存储它 n 次，并且每个参数占用 log(n) space。所以总共 O(nlogn)

所以你得到了 O(n) + O(nlogn) + O(nlogn) = O(nlogn)。这是计算阶乘递归所需的量 space。

通过这个分析，您可以发现为什么进行 alpa-beta 修剪的国际象棋程序需要大量 ram 才能正确计算位置。

Answer 2

把时间复杂度写成这样的形式后

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

或

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

等等。

你有两个选择：

1) 使用重复替换法，在某些情况下需要一些数学技巧，因为你应该按照步骤直到T(1) 或T(0) 然后计算总和。

或

2) 使用类似于公式的主定理Master Theorem，适用于许多实际情况

What is the general way to find space complexity of recursive algorithms?