c - 下面的程序如何花费 O(n!) 时间？

Question

以下程序的复杂度为 O(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;
    }
}

但我无法确定其复杂度为 O(n!)。谁能解释一下它是如何变成 O(n!) 的？

是 θ(n!) 也是 O(n!) 还是只有 O(n!)？

如果不是 θ(n!) 。我可以获取 θ(n!) 代码的示例吗？

Answer 1

假设计算 foo(n) 的时间为 T(n)。在 n>0 的情况下，我们可以得出迭代所需的时间为:T(n)=(Σi=0n−1T(i))+n+c另外，T(1)=c首先，有一点理由。括号中的总和是循环中所有对 foo 调用的运行时间。 n 负责循环，常量 c 负责初始化、比较等内容。

现在，在中间，让我们计算下一步是什么，看看我们是否可以推断出运行时间的增长。

T(n+1)=(Σi=0nT(i))+(n+1)+c现在，如果我们从当前总和中提取 T(n)，我们得到:

T(n+1)=(Σi=0n−1T(i))+T(n)+(n+1)+c现在，如果我们按以下方式重新排列结果，我们就有机会减少总和:

T(n+1)=[(Σi=0n−1T(i))+n+c]+T(n)+1您会看到括号中的内容正是我们定义的 T(n)(第一个方程)。在这种情况下，我们得到:

T(n+1)=T(n)+T(n)+1=2T(n)+1由此也可知T(n)=2T(n−1)+1。如果我们用这个函数计算出的值替换 T(n−1) 会发生什么？好吧，让我们迭代一下:

T(n)=2T(n−1)+1=2[2T(n−2)+1]+1=2[2[2T(n−3)+1]+1]+1⋮ =2kT(n−k)+k差不多了。最后，让我们用我们已知的基本情况 T(0) 来编写它。首先，我们必须有 T(n−k)=T(0)，因此 k=n。最终我们得到:

T(n)=2nT(0)+n=2nc+n考虑到这一点，我们可以得出结论 T(n)=θ(2n)