c# - 查找递归算法空间复杂度的一般方法是什么？

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;

为那种算法(如斐波那契)找到空间复杂度的一般方法是什么？我们需要找到调用堆栈的深处？

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)。这是计算阶乘递归所需的空间。

---

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