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

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），我在哪里想错了吗？

- POOJA GUPTA

---

@devnull: 如果(n==0)，则返回1.0；// 这用于控制递归函数，以便在某个时刻返回控制。所以，是的，它会编译。 - POOJA GUPTA

也许这个问题通过分配的总内存来衡量"空间复杂度"，而不是任何一点上分配的最大内存量。如果是这样，那么它将超过O（n）。 - Kevin

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)的时间内运行而不会发生堆栈溢出。

- Vikram Bhat

---

谢谢。你解决了我的疑惑。我尝试使用输入值5运行它，每个调用执行O(1)时间，所以时间复杂度为O(2^n)，但是使用动态规划，复杂度会降低。 - POOJA GUPTA

如果您使用备忘录技术，那么时间复杂度将降至O(N)。但是从函数中我得知您正在计算2^(N-1)，可以使用位移操作在O(1)时间内完成。 @POOJAGUPTA - Vikram Bhat

Answer 2

这样来考虑：

计算 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!)。

希望这很清楚。

- user2459179

---

这听起来像是关于算法时间复杂度的一个好论点，但它是否也适用于空间复杂度呢？ - Kevin

我猜你的意思是 foo(n) = ... 或者 O(foo(n)) = O(...)，因为你写的方式是不正确的。 - Bernhard Barker

是的，就像其他几篇帖子所说的那样。这只是针对时间复杂度的。我的错...还有，asdukeling说我的符号也不对... - user2459179

@user2459179：感谢您的回答，但您所说的不是时间复杂度吗？我的意思是您能否澄清一下？您的最终答案是什么？因为我认为即使函数有N！个函数调用，这些调用在堆栈中占用的空间也最多只有n。 - POOJA GUPTA

@user2459179 首先，这个问题涉及到空间复杂度，而且时间复杂度也是O(2^N)，而不是O(N!)。证明：T(N) = T(N-1) + T(N-2) + T(N-3).....T(1)，因此T(N-1) = T(N-2) + T(N-3).... 因此T(N) = 2*T(N-1)，解决后得到O(2^N)。 - Vikram Bhat

Answer 3

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

- egur