c - 给定递归程序的空间复杂度

Question

考虑以下 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) 以及我哪里想错了？

Answer 1

如果您需要时间复杂度，那么它肯定不是许多人建议的 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) 时间内运行而不会出现任何堆栈溢出。