0

以下は単純な再帰関数です。私はこのような再帰方程式を作りました

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

int i に + 1 を使用しました。私はこのように解決しました

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; 
 }

この短い問題を解決する方法を教えてください

4

1 に答える 1

0

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) の複雑さに依存します。

于 2013-08-05T02:04:52.763 に答える