考虑以下 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 是某个常数。
最佳答案
这取决于您是在谈论堆栈还是堆空间复杂性。
对于堆，它是 O(1) 或 O(0) 因为您没有使用堆内存。 (除了基本的系统/程序开销)
对于堆栈，它是O(n)。这是因为递归深入 N 层。
最深的一点是:
foo(n)
foo(n - 1)
foo(n - 2)
...
foo(0)
关于algorithm - 计算 C 函数的空间复杂度？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/8619702/