1

このプログラムは、指定された文字列の可能なすべての組み合わせを再帰的に出力します。再帰的に自分自身を呼び出す for ループ内のステートメントに混乱しています。それは暗黙的な n*n で、n は文字列の長さです

   public static void getStringCombination(String prefix, String str) {
     System.out.println(prefix);
     for (int i = 0; i < str.length(); i++)
     getStringCombination(prefix + str.charAt(i), str.substring(i + 1));
    }
4

2 に答える 2

2

私は個人的に常にそのようなことを判断するのに苦労していますが、これは階乗的であると言わざるを得ません. 最初のヒントはall the possible combination、高校の数学を正しく覚えていれば、多かれ少なかれ階乗であると出力しているということです。2番目のヒントは、再帰呼び出しを行う文字列全体に対してforループを実行しているため、最初の呼び出しでN回の再帰呼び出しを実行し、次の再帰呼び出しではN-1再帰を実行することです通話など

これを言った後、私は自分自身と、実際に可能なすべての組み合わせを実際に印刷するかどうかを疑っていると言わなければなりません...後者の文字が最初の文字の前にある組み合わせを印刷しないことは非常に確信しています文字。これは、階乗が正しくないという私の声明を作成する可能性がありますが、これについて確信があるとは言えません。

編集

@Ben S.の回答とテストを読んだ後、あなたの例はO(2^n)であり、Ben S.の「修正」はO(n!)であると私の考えはかなり確信していますが、私は違います、実際はもっと高いです。あなたの例が 2^n である理由を説明できないと思いますが、まだ自分で考えています。

于 2013-10-09T05:50:24.143 に答える
0

これは O(n2) に近いはずですが、再帰の場合であるため、これが正確であるとは言えません。

于 2013-10-09T05:46:38.250 に答える