这个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)

Answer 1

它是Θ(2 ^ n)(假设f是我们算法的运行时间):

f(n) = f(n-1) + f(n-2) + ... + 1
f(n-1) = f(n-2) + f(n-3) + ...
==> f(n) = 2*f(n-1), f(0) = 1
==> f(n) is in O(2^n)

实际上,如果我们忽略常量操作,那么确切的运行时间是2 ⁿ.

同样在你写这个是考试的情况下,O(n!)和O(n ^ n)都是真的,并且它们中最接近Θ(2 ^ n)的答案是O(n!),但如果我是学生,我会标记他们两个:)

关于O(n!)的说明:

for all n >= 1: n! = n(n-1)...*2*1 >= 2*2*2*...*2 = 2^(n-1) ==>
2 * n! >= 2^n ==> 2^n is in O(n!),
Also n! <= n^n for all n >= 1 so n! is in O(n^n)

So O(n!) in your question is nearest acceptable bound to Theta(2^n)