0

次のアルゴリズムのBigOhを知りたい

public List<String> getPermutations(String s){
    if(s.length()==1){
        List<String> base = new ArrayList<String>();
        base.add(String.valueOf(s.charAt(0)));
        return base;
    }

    List<String> combos = createPermsForCurrentChar(s.charAt(0),
                                    getPermutations(s.substring(1));

    return combos;
}
 private List<String> createPermsForCurrentChar(char a,List<String> temp){
    List<String> results = new ArrayList<String>();
    for(String tempStr : temp){
        for(int i=0;i<tempStr.length();i++){
            String prefix = tempStr.substring(0, i);


            String suffix = tempStr.substring(i);

            results.add(prefix + a + suffix);
        }


    }
    return results;
}

ここで、getPermutationsはn回と呼ばれます。ここで、nは文字列の長さです。私の理解では、createPermutationsはO（l * m）です。ここで、lはリストtempの長さ、mはtemp内の各文字列の長さです。

ただし、最悪の場合の分析を検討しているため、m<=nおよびl<=n！です。一時リストの長さは、再帰呼び出しごとに増え続け、一時の各文字列の文字数も増え続けます。

これは、このアルゴリズムの時間計算量がO（n * n！* n）であることを意味しますか？それともO（n * n * n）ですか？

4

2 に答える 2

2

さて、コメントの長いリストを作成する代わりに、これを回答として書き留めます。

長さ n の文字列に対する getPerm の実行時間を T(n) として示します。getPerm 内で getPerm(string length n-1) を呼び出すことに注意してください。

T(n)=T(n-1) + [run time of createPerm]

createPerm にはネストされた 2 つのループがあることに注意してください。外側のループは getperm の結果のサイズ (長さ n-1 の文字列) を反復し、内側のループは n-1 (個々の文字列の長さ) を反復します。getPerm(string of length n-1) の結果は、T(n-1) 文字列のリストです。このことから、

[run time of createPerm] = (n-1) T(n-1)

これを前の式に代入すると、

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

終了条件から T(1) = 1。展開して解を見つけることができます (または、代わりに Z 変換を使用します:この再帰の複雑さを把握できません)。これは単純な方程式であるため、展開は高速です。

 T(n) = n T(n-1)
      = n (n-1) T(n-2)
      = n (n-1) (n-2) T(n-3) ....
      = n (n-1) ... 1
      = n!

つまり、T(n) = n!

演習: これを帰納法で証明してください! :p

これは理にかなっていますか？考えてみましょう。n 文字の順列を作成しています: http://en.wikipedia.org/wiki/Permutation。

編集: T(n)=n であることに注意してください! O(ん!)

于 2013-01-30T16:20:34.987 に答える
1

私は組み合わせ論が得意ではありませんが、O(n^3) だと思います。ここで、n は文字列の文字数です。

私の論理は次のとおりです。

getPermutations(String)

が呼び出され、次の呼び出しに関連しています。

createPermsForCurrentChar(s.charAt(0),getPermutations(s.substring(1));

最初の呼び出しで引数 (charAt(0), 長さ s.length-1 の部分文字列) を渡し、次に (charAt(1), 長さ s.length-2 の部分文字列)... を O(n) 呼び出しに渡します。

さらに重要なのは、createPermsForCurrentChar を入力するたびに List temp に含まれる要素の数です。

まず、関数をスタンドアロンのものとして分析してみましょう: に k 個の要素がありList<String> temp、L=1 で始まり L=k で終わる、L=現在の長さで示される単調に増加する長さがあるとします。

外側の for ループは k 回反復しますが、これは簡単です。内側の for ループは L 回繰り返します。複雑さは O(k"L") です。L は毎回変更されるため、引用符で囲まれています。どのように見えるか見てみましょう。最初の外側のループ反復で、内側のループが 1 回実行されます。2 番目の外側のループ反復では、内側のループが 2 回実行され、内側のループが k 回実行されるまで続き、1+2+3+4+...k = O(k^2) が得られます。

そのため、createPermsForCurrentChar は O(k^2) の複雑さです。ここで、k は要素の数List<String> temp(および temp の最長文字列のサイズ) です。私たちが今知りたいのはこれです -List<string> temp各呼び出しにいくつの要素が入るでしょうか?

再帰で最終的に基本ケースに到達すると、文字列の最後から 2 番目の文字と、文字列の最後の文字を createPermsForCurrentChar に渡すので、k=1 になります。長さ O(k) の単一の文字列を作成します。これにより、次の実行でスタックから取り出され、今度は k=2 で createPermsForCurrentChar を再度呼び出すことができます。次に、k=3、k=4、k=5 などです。

createPermsForCurrentChar は再帰関係により O(n) 回呼び出されていることがわかっているため、k は最終的に = n になります。(1 + 2 + 3 + ... + n) = O(n^2)。createPermsForCurrentChar の複雑さを考慮すると、(1^2 + 2^2 + 3^2 + ... n^2) = (1/3)n^3 + (1/2)n^2 + ( 1/6)n ( http://math2.org/math/expansion/power.htmから)。

支配的な値のみを気にするので、アルゴリズムは O(n^3) であると言えます。

于 2013-01-29T17:01:15.363 に答える