0

これは、与えられた文字列のすべての順列を見つける単純なプログラムです:

void perm( char str[], int len )
{
if ( len == 1 )
   cout << str << endl ;
else
    for ( int i=0; i<len; i++ ) {
        swap( str[len-1], str[i] ) ;
        perm( str, len-1 ) ;
        swap( str[len-1], str[i] ) ;
    }
}

この関数の T(n) は? この関数のビッグ オー (またはシータ) を計算する方法は?

4

3 に答える 3

2

for loop は n*T(n-1) に n 再帰を実行し、さらに 2n 回スワップする必要があるため、O(n) を加えます。

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

n = 5 for sake of my keyboard

T(n) = n*T(n-1) + n  
T(n) = n*[(n-1)*T(n-2) + (n-1)] + n  
T(n) = n*[(n-1)*[(n-2)*T(n-3) + (n-2)] + (n+1)] + n  
T(n) = n*[(n-1)*[(n-2)*[(n-3)*T(n-4) + (n-3)] + (n-2)] + (n-1)] + n  
T(n-4) = 1 ----------------------^  
Simplify 
T(n) = n*[(n-1)*[(n-2)*[(n-3) + (n-3)] + (n-2)] + (n-1)] + n  
T(n) = n*[(n-1)*[(n-2)*[2(n-3)] + (n-2)] + (n-1)] + n  
T(n) = n(n-1)(n-2)*(n-3)*2 + (n-1)(n-2) + n(n-1) + n  
T(n) = n! + O(n*n!)    <--  wrong, see comment for right answer
T(n) = O(n*n!)    <--  wrong, see comment for right answer

あなたはパターンを見る

于 2012-08-28T18:54:38.223 に答える
2

初期入力文字列の長さを N とします。

perm(str (size = N), len=i) の呼び出しにかかる時間を T(i) とします。

T(1) = N

と

T(i > 1) = iT(i-1) + i

かかる合計時間は T(N) です。

この繰り返しの閉じた形式を計算するには、次を参照してください。

https://math.stackexchange.com/questions/188119/closed-form-for-t1-k-tx-xtx-1-x

答えは次のとおりです。

T(N) is approximately (N + e - 1)N!

したがって、N が無限大に近づくと、関数のパフォーマンスは次のようになります。

O((N + e - 1)N!) = O(N(N!))
于 2012-08-28T19:30:57.223 に答える
1

N 個のアイテムの可能な順列の数は N! (階乗)、このコードは、出力する順列ごとに O(1) 操作を使用しているようです。したがって、建設コストは O(N!) であり、これは O(N^N) に相当します。

または、順列ごとに N 個の項目がコンソールに出力されるため、O(N!*N) になるかもしれません。

于 2012-08-28T18:35:58.273 に答える