私が持っている電子ブックからこのテキストを貼り付けています。O(n 2 )の場合の複雑さを示し、その説明も提供しますが、その方法がわかりません。
質問: このコードの実行時間は?
public String makeSentence(String[] words) {
StringBuffer sentence = new StringBuffer();
for (String w : words) sentence.append(w);
return sentence.toString();
}
本が与えた答え：
O(n 2 )、ここで n は文の文字数です。理由は次のとおりです。文に文字列を追加するたびに、文のコピーを作成し、文のすべての文字を実行してコピーします。ループ内で毎回最大 n 文字まで反復する必要がある場合、少なくとも n 回ループすると、O(n 2 ) の実行時間が得られます。痛い！
誰かがこの答えをもっと明確に説明できますか?
たまたまその本を読んだばかりなので、これは誤解を招く問題のようです。本のテキストのこの部分はタイプミスです! コンテキストは次のとおりです。
================================================== =================
質問: このコードの実行時間は?
1 public String makeSentence(String[] words) {
2 StringBuffer sentence = new StringBuffer();
3 for (String w : words) sentence.append(w);
4 return sentence.toString();
5 }
答え: O(n 2 )、ここで n は文の文字数です。理由は次のとおりです。文に文字列を追加するたびに、文のコピーを作成し、文のすべての文字を実行してコピーします。ループ内で毎回最大 n 文字まで繰り返す必要があり、少なくとも n 回ループしている場合、O(n 2 ) の実行時間が得られます。痛い！StringBuffer (または StringBuilder) を使用すると、この問題を回避できます。
1 public String makeSentence(String[] words) {
2 StringBuffer sentence = new StringBuffer();
3 for (String w : words) sentence.append(w);
4 return sentence.toString();
5 }
================================================== ===================
著者がそれを台無しにしたことに気づきましたか？彼女が言及した O(n 2 ) ソリューション (最初のもの) は、「最適化された」ソリューション (後者) とまったく同じでした。したがって、私の結論は、O(n 2 ) アルゴリズムの例として、次のすべての文字列を追加するときに常に古い文を新しいバッファーにコピーするなど、作成者が何か他のものをレンダリングしようとしていたということです。著者は「StringBuffer (または StringBuilder) を使用すると、この問題を回避できる」とも述べているため、StringBuffer はそれほどばかげているべきではありません。
実装の詳細を抽象化して高レベルで記述されている場合、このコードの複雑さに関する質問に答えるのは少し難しいです。Javaのドキュメントは、append関数の複雑さに関して何の保証もしていないようです。他の人が指摘したStringBufferように、文字列を追加する複雑さが、に保持されている文字列の現在の長さに依存しないように、クラスを記述することができます (また、記述する必要があります) StringBuffer。
しかし、この質問をする人が単に「あなたの本は間違っている!」と言うのはあまり役に立たないと思います。-代わりに、どのような仮定が行われているかを見て、著者が言おうとしていたことを明確にしましょう.
次の仮定を行うことができます。
new StringBufferは O(1)wを取得するのwordsは O(1) ですsentence.toStringのは最大で O(n) です。問題は実際には の順序でありsentence.append(w)、それは 内でどのように発生するかに依存しますStringBuffer。単純な方法は、画家のシュレミエルのようにすることです。
のコンテンツに C スタイルのヌル終了文字列を使用するとしますStringBuffer。このような文字列の末尾を見つける方法は、ヌル文字が見つかるまで各文字を 1 つずつ読み取ることです。次に、新しい文字列 S を追加するために、S からStringBuffer文字列への文字のコピーを開始できます (別のヌル文字で終了)。キャラクター）。このように書くappendと、O( a + b ) となります。ここで、aは現在の文字数StringBuffer、bです。新しい単語の文字数です。単語の配列をループし、新しい単語を追加する前に追加したすべての文字を読み取る必要があるたびに、ループの複雑さは O(n^2) になります。ここで、n は文字の総数です。すべての単語で（最終文の文字数も）。
一方、 の内容は依然として文字の配列ですが、文字列の長さ (文字数) をStringBuffer示す整数も格納するとします。これで、文字列の末尾を見つけるためにsize、すべての文字を読み取る必要がなくなりました。O( a )ではなく O(1) である配列内のStringBufferインデックスを検索するだけです。次に、関数は追加される文字数 O( b ) のみに依存するようになりました。この場合、ループの複雑さは O(n) です。ここで、n はすべての単語の合計文字数です。sizeappend
最後に、まだカバーされていない実装の側面がもう 1 つあります。これは、教科書の回答によって実際に持ち出されたものです - メモリ割り当てです。より多くの文字を に書き込もうとするたびStringBufferに、文字配列に新しい単語を実際に収めるのに十分なスペースがあるとは限りません。十分なスペースがない場合、コンピューターは最初に にさらにスペースを割り当てる必要があります。メモリのクリーンなセクションを作成し、古いStringBufferアレイ内のすべての情報をコピーすると、以前と同じように続行できます。このようなデータのコピーには、O( a ) 時間かかります ( aはコピーする文字数です)。
最悪の場合、新しい単語を追加するたびにより多くのメモリを割り当てなければなりません。これは基本的に、ループが O(n^2) の複雑さを持ち、本が示唆しているように見える正方形に戻ります。おかしなことは何も起こっていないと仮定する場合 (単語が指数関数的に長くなることはありません!)、割り当てられたメモリを大きくすることで、おそらくメモリ割り当ての数を O(log(n)) のようなものに減らすことができます。指数関数的に。それがメモリ割り当ての数であり、一般的なメモリ割り当てが O( a) の場合、ループ内のメモリ管理だけに起因する複雑さの合計は O(n log(n)) です。追加作業は O(n) であり、メモリ管理の複雑さよりも少ないため、関数の全体的な複雑さは O(n log(n)) です。
繰り返しになりますが、Java のドキュメントは、の容量がどのように増加するかという点では役に立ちませんStringBuffer。「内部バッファーがオーバーフローすると、自動的に大きくなります」とだけ書かれています。それがどのように発生するかに応じて、全体的に O(n^2) または O(n log(n)) になる可能性があります。
読者に任せる演習として: メモリの再割り当ての問題を取り除くことで、全体的な複雑さが O(n) になるように関数を変更する簡単な方法を見つけてください。
このプログラムを使用して確認しようとしました
public class Test {
private static String[] create(int n) {
String[] res = new String[n];
for (int i = 0; i < n; i++) {
res[i] = "abcdefghijklmnopqrst";
}
return res;
}
private static String makeSentence(String[] words) {
StringBuffer sentence = new StringBuffer();
for (String w : words) sentence.append(w);
return sentence.toString();
}
public static void main(String[] args) {
String[] ar = create(Integer.parseInt(args[0]));
long begin = System.currentTimeMillis();
String res = makeSentence(ar);
System.out.println(System.currentTimeMillis() - begin);
}
}
結果は、予想どおり、O(n) でした。
Java テスト 200000 - 128 ミリ秒
Java テスト 500000 - 370 ミリ秒
Java テスト 1000000 - 698 ミリ秒
バージョン 1.6.0.21
この本にはタイプミスがあります。
最初のケース:
public String makeSentence(String[] words) {
String sentence = new String();
for (String w : words) sentence += w;
return sentence;
}
複雑さ : O(n^2) -> (n 単語) x (現在の文を StringBuffer にコピーするために、各反復でコピーされる n 文字)
2番目のケース:
public String makeSentence(String[] words) {
StringBuffer sentence = new StringBuffer();
for (String w : words) sentence.append(w);
return sentence.toString();
}
複雑さ : O(n) -> (n ワード) x O(1) (StringBuffer 連結の複雑さの償却)
それは本当にの実装に依存しStringBufferます。が定数時間であると仮定すると、時間のアルゴリズム.append()があることは明らかです。時間が一定でない場合は、O(n) にメソッドの時間の複雑さを掛ける必要があります。実際に現在の実装で文字列を文字単位でコピーする場合、上記のアルゴリズムは次のようになります。O(n)n = length of the words array.append StringBuffer
Θ(n*m)、またはO(n*m)、ここでnは単語数、mは平均単語長であり、あなたの本は間違っています。厳密な境界を探していると思います。
本の答えが間違っている簡単な例:
String[] words = ['alphabet']本の定義によりn=8、アルゴリズムは 64 ステップに制限されます。これは事実ですか？明らかに厳密ではありません。n 文字で 1 つの割り当て操作と 1 つのコピー操作が表示されるので、約 9 つのステップが得られます。上で説明したように、この種の動作は の境界によって予測されO(n*m)ます。
私は掘り下げましたが、これは明らかに単純なキャラクターのコピーではありません. O(n)メモリが大量にコピーされているようです。これにより、ソリューションの最初の推測である に戻ります。
/* StringBuffer is just a proxy */
public AbstractStringBuilder append(String str)
{
if (str == null) str = "null";
int len = str.length();
ensureCapacityInternal(count + len);
str.getChars(0, len, value, count);
count += len;
return this;
}
/* java.lang.String */
void getChars(char dst[], int dstBegin) {
System.arraycopy(value, offset, dst, dstBegin, count);
}
あなたの本は古いかひどいか、あるいはその両方です。JDK のバージョンを掘り下げて、最適ではない StringBuffer の実装を見つけるほどの確信はありませんが、おそらく存在するでしょう。
本で説明されているように、文字列配列内の単語ごとに新しい文オブジェクトが作成され、その文オブジェクトは最初に前の文をコピーし、次に配列の最後までトラバースしてから新しい単語を追加するため、複雑になります。のn^2。
したがってn*n、 になりますn^2。