逐次ソートアルゴリズム

Question

私は、次の要素が来る前にベクトルをソートする必要がある、つまり、n個の合計がある場合、要素。マージソートはより良いはずです。しかし、マージソートには複雑さn log nがあるとよく言われています。一度にn個の要素をソートしようとするなら、それは当てはまります。それらが1つずつ来て、一時ベクトルをソートする必要がある場合、複雑さは\ sum_ {i = 2}^n i log（i）まで上がります。これはまだn^2未満であると推測しますが、確かにn log n以上です。

これは間違いありませんか？

おかげ

Answer 1

EDIT 2：

\sum_{i=1}^N i log i > \sum_{i=1}^N i = O(N²) 

EDITは：どうやら、あなたはポイントを逃したので、私は明確にしようとするでしょう。

まず、N個の要素を配列に挿入し、挿入が完了するたびに配列がソートされるようにしながら、複雑さO（N²）で実行できます。要素が挿入される位置を見つけるためにバイナリ検索を使用して、配列をソートされているので

• ：あなたは要素を挿入するために、次のアルゴリズムを使用することができます。 O（log i）時間をとります。ここで、iは配列の現在のサイズです。
• すべての要素を1つ右の位置に移動して要素を挿入します。これは、i要素まで移動することを伴うので、O（i）です。

このアルゴリズムをN個の挿入に対して繰り返すと、\ sum_i（i + log i）= O（N²）が得られます。

非常に明確にするには：これは挿入ソートではありません。挿入ソートでは、すべての要素を再挿入することによって配列全体をソートする必要がありますが、このアルゴリズムは1つの要素を挿入するだけです。

第2に、この操作をO（N²）より速く行うことはできません。ソートされた配列を維持しながらサイズiの配列に1つの要素を挿入すると、O（i）よりも複雑ですi要素。 この基本的事実回避するための回避策だけではありません：あなたは[2,3,..,i]に1を挿入した場合、結果は、要素2を意味し、[1,2,3,..,i]である3が..私を移動するを持っていました。

したがって、合計は\ sum_i i = O（N²）より大きくなります。