为什么这个 O(n) 的时间复杂度？

Question

我正在看这个问题：

Let T(n) be the maximum stack depth of the following function, in terms of n.
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;
    }
}
Find T(n) = O(?)

提供的答案是O(n)，但我计算是O(n!)。我不确定如何为此设计解决方案。

Answer 1

堆栈深度可以表示为在某个点从单个递归向下递归调用的最大次数。 foo(n) 调用 foo(0)、foo(1)、foo(2)、...、foo(n - 1)。如果您跟踪来自 foo(n-1) 的递归调用，您会看到它调用了 foo(n - 2)。一直这样直到 f(0) 被调用。因此最大堆栈深度为 O(n)。不是 O(n!)。

时间复杂度如何？

T(n) = T(n-1) + T(n-2) + ... + T(1) + T(0)
T(1) calls T(0) 1 times.  (2^0)
T(2) calls T(0) 2 times.  (2^1)
T(3) calls T(0) 4 times. (from T(2) + T(1) + T(0))
T(4) calls T(0) 8 times.
T(5) calls T(0) 16 times. (2^4)
         ...
T(n-1) calls T(0) 2^(n-2) times.

In total T(0) is called [1 + 2 + 4 + 8 + ... + 2^(n-2)] + 1 times.

等于2^(n-2) + 2^(n-2)，可以表示为2^n / 2。因此它具有指数时间复杂度，即O(2^n).

为什么这个 O(n) 的时间复杂度？

Why is the time complexity for this O(n)?

algorithm

time-complexity