algorithm - 单循环找不到递归函数的时间复杂度

Question

以下是一个简单的递归函数。我已经像这样制作了它的递归方程

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

我用 + 1 表示 int i; 我已经这样解决了

T(n)=kT(n-1)+1。. . T(n)=k^mT(nm)+m

使 T(1)-> nm=1 -> m=n-1

它变成 ( k^n-1 )(n-1)

现在我的问题是，它好吗？我期待它 n^2 但这似乎不是多项式的。

void permute(int k,int size) 
 {  
   int i; 
   for (i=k-1;i>=0;i--) 
   permute(k-1,size); 
  return; 
 } 

请帮我解决这个短问题

Answer 1

让 n = 大小。然后

T(n,k)=k*T(n,k-1) + O(1)
    =k*[(k-1)*T(n,k-2) + O(1)] + O(1)
    =k*(k-1)*T(n,k-2) + k*O(1) + O(1)
    =k*(k-1)*[(k-2)*T(n,k-3) + O(1)] + k*O(1) + O(1)
    =k*(k-1)*(k-2)*T(n,k-3) + k*(k-1)*O(1) + k*O(1) + O(1)
    =...
    =O(k!)*T(n,0) + O(1) * [P(k,k-1)+P(k,k-2)+...+P(k,1)]
    =O(k!)*T(n,0) + O(1) * e * O(k!)
    =O(k!)*T(n,0)                

所以这取决于 permute(0,size) 的复杂度。