解説例12 Big O表記の文字列のすべての並べ替え - コーディングの面談の破棄

Question

文字列のすべての順列を生成する次の手順の複雑さを著者がどのようにして得たか理解できません。

void permutation(String str){ 
    permutation(str,""); 
} 
void permutation(String str, String prefix){ 
    if(str.length()==0){ 
    System.out.println(prefix); 
    } else{ 
    for(int i=0;i<str.length();i++){ 
     String rem=str.substring(0,i)+str.substring(i+1); 
     permutation(rem,prefix+str.charAt(i)); 
    } 
    } 
} 

Answer 1

方法の複雑さがあるため、他のパスコストのO(n^2 *n!)です：私たちはへの呼び出しと一緒にそれをn回を計算elseパスにString rem=str.substring(0,i)+str.substring(i+1);への各呼び出しはO(n)であることを

最初の通知、 複雑さがT(n-1)のpermutationです。

この複雑さを計算することは、次のようになります。T(n) = n[n+T(n-1)];この再発を解決(n+T(n-1))

のn回（ループ用）の作品は、私が間違っていないよ場合は、それが解決に煮詰める必要があり、それは容易ではありません。

しかしさんが近似してみましょう。 各置換（基本ケース）は、再帰ツリーのノードを表します。この木はn!の葉を持っています。各リーフは長さnのルートへのパスを持ちます。したがって、ツリー内にノードがn*n!以下であると仮定することは安全です。

これは、permutationへのコール数の上限です。この呼び出しにはそれぞれnのコストがかかるため、複雑さの全体的な上限はO(n^2*n!)

となります。