4

考虑以下 C 函数：

double foo (int n) {
    int i;
    double sum;
    if (n==0)
        return 1.0;
    else {
        sum = 0.0;
        for (i=0; i<n; i++)
        sum +=foo(i);
        return sum;
    }
}

上述函数的空间复杂度为：

(a) O(1) (b) O(n) (c) O(n!) (d) O(n^n)

我所做的是计算上述代码的递归关系，但我仍然无法解决该递归。我知道这不是与家庭工作相关的网站。但任何帮助将不胜感激。

这是我的复发。

T(n) = T(n-1) + T(n-2) + T(n-3) + T(n-4) +........+ T(1)+ S

其中 S 是某个常数。

4

4 回答 4

4

这取决于您是在谈论堆栈还是堆空间复杂性。

对于堆，它是O(1)或者O(0)因为你没有使用堆内存。（除了基本的系统/程序开销）

对于堆栈，它是O(n). 这是因为递归提高了N层次。

最深的地方是：

foo(n)
    foo(n - 1)
        foo(n - 2)

        ...

        foo(0)
于 2011-12-23T19:04:35.817 回答
2

空间复杂度描述了您的程序需要多少空间。由于foo不声明数组，因此每个级别都需要O(1)空间。现在您需要做的就是弄清楚在任何给定时间最多可以激活多少个嵌套级别。

编辑：...这么多让你自己找出解决方案:)

于 2011-12-23T19:05:24.200 回答
1

空间复杂度为 O(n)。正如您所提到的，它可能看起来像 O(n*n)，但应该记住，一旦在循环中对 say (i=1) 的调用完成，堆栈中为此使用的空间将被删除。因此，当 i=n-1 时，您将不得不考虑最坏的情况。那么递归函数调用的最大数量将同时在堆栈上

于 2011-12-24T17:38:40.370 回答
1

您没有解释如何得出递归关系。我会这样做：

  1. 如果 n == 0，则foo使用常量空间（没有递归）。
  2. 如果 n > 1，则foo对从 0 到 n-1（包括）的每个 i 递归一次。对于每个递归，它使用常量空间（用于调用本身）加上 T(i) 空间用于递归调用。但是这些电话一个接一个地发生；每次调用使用的空间在下一次调用之前释放。因此，不应添加它们，而应仅添加所取的最大值。那将是 T(n-1)，因为 T 是非递减的。
于 2011-12-23T19:05:45.287 回答