3

考虑以下 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; 
      }
}

上述函数的空间复杂度为 

1)  O(1)
2)  O(n)
3)  O(n!)
4)  O(n^n)

根据我的说法，在上述问题中，答案应该是（2），但答案是（3）选项。虽然它是递归函数，但堆栈永远不会超过 O(n) 堆栈深度。谁能解释我为什么是这个答案（3），我在哪里想错了？

4

3 回答 3

3

如果您需要时间复杂度，那么它肯定不会O(N!)像很多人建议的那样，但要少得多O(2^N)。

证明：-

T(N) = T(N-1) + T(N-2) + T(N-3) + T(N-4)........T(1)

再由上式

T(N-1) = T(N-2) + T(N-3)...... T(1)

因此T(N) = T(N-1) + T(N-1) = 2*T(N-1)

解决上面给出T(N) = O(2^N)

而如果您需要空间复杂度，那么对于递归函数，空间复杂度是由它在某一时刻占用的最大堆栈空间量计算的，在这种情况下不能超过O(N)

但无论如何，答案不是O(N!)因为根本没有完成许多计算，所以堆栈怎么会占用那么多空间。

注意：-尝试运行该函数，n = 20如果它不会导致内存溢出，那么文本中给出的答案将为 20！它比任何内存都大，但我认为它会O(2^20)及时运行而不会出现任何堆栈溢出。

于 2014-01-13T19:09:59.500 回答
1

空间复杂度为 O(N)。在任何给定时间，使用的空间仅限于： N*sizeof_function_call_which_is_a_constant.

于 2014-01-13T15:20:57.427 回答
1

可以这样想：

计算foo(n)。程序必须计算： foo(0)+foo(1)+foo(2) ... foo(n-1)：

同样对于 foo(n-1)。程序必须递归计算：foo(0) + foo(1) + ... foo(n-2)。

基本上你会有 O(foo(n)) = n! + (n-1)！+ (n-2)！+ ... 1！= O(n!)。

希望这很清楚。

于 2014-01-13T15:08:25.483 回答