algorithm - 计算 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;
    }
}

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

(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 是某个常数。

Answer 1

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

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

对于堆栈，它是O(n)。这是因为递归深入 N 层。

最深的一点是:

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

        ...

        foo(0)