0

特定の文字列の順列を出力する次のコードがあります。[簡単にするために、そして私がしようとしていることへの焦点を失わないようにするために、文字列に重複する文字がないと仮定しましょう]

public static int count = 0;

public static void permute(String soFar, String strLeft) {

    if(strLeft.length() == 1) {
        soFar += strLeft;
        System.out.println(++count + " :: " + soFar);
    }

    for(int i=0; i<strLeft.length(); i++) {
        permute(soFar + strLeft.charAt(i), strLeft.substring(0,i) + strLeft.substring(i+1));
    }
}

/**
 * @param args
 */
public static void main(String[] args) {
    String input = "abcd";
    permute("",input);
}

このコードの実行時間を把握しようとしています。

これまでの私の思考回路： 繰り返しを書いてみると、

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

あります！順列ですが、再帰呼び出しの数は n! を超えています。実際、入力文字列が "abcd" 、つまり 4 文字の例では、permute 関数の呼び出し回数は 65 回です。

このコードの実行時間を見つける方法についての指針はありますか?

4

1 に答える 1

2

まず第一に、冗長な呼び出しを行います。キャラクターが 1 人しか残っていない場合は、ソリューションを放出します。ただしpermute、空の文字列で呼び出すと、呼び出し回数が台無しになります。

私の最初の改善点はelse、if節に an を追加することです。

public static void permute(String soFar, String strLeft) {

    if(strLeft.length() == 1) {
        soFar += strLeft;
        System.out.println(++count + " :: " + soFar);
    }
    else {
        for(int i=0; i<strLeft.length(); i++) {
            permute(soFar + strLeft.charAt(i), strLeft.substring(0,i) + strLeft.substring(i+1));
        }
    }
}

これにより、呼び出しの量が 41 に削減されます。呼び出しの数をカウントするには、呼び出しツリーを構築し、ノードをカウントします。各呼び出しは文字列から 1 文字を削除することで行われるため
、長さ 4 の呼び出しが 1 回、
長さ 3 の呼び出しが4 回、
長さ 2 の呼び出しが 12 回
、長さ 1 の呼び出しが 24回あります。

合計すると 41 になります。

于 2013-03-05T07:43:09.740 に答える