c - 关系 T(n)=nT(n-1)+n 的时间复杂度是多少

Question

关系 T(n)=nT(n-1)+n 的时间复杂度是多少在我的程序中是这样的

f(int n)
{
    c++;
    if(n>0)
        for(i=1;i<=n;i++)
            f(n-1);
}

我用一个计数器来计算函数被调用的次数它给出了 n 到 n 之间的答案!谢谢。

Answer 1

您的代码缺少递归的 +n 部分，因此我认为代码是错误的并且递归

T(n) = n*T(n-1) + n

正确。

设f(n)=T(n)/n!，则

f(n) = T(n)/n! = n(T(n-1)+1)/n! 
     = T(n-1)/(n-1)! + 1/(n-1)!
     = f(n-1) +  1/(n-1)!
     = sum(1,n-1, 1/k!)
     ~ e

因此T(n) ~ e*n!。