ソートされた配列のN個の挿入操作の時間の複雑さ

Question

N個の要素を含むソートされた配列があり、N個の挿入操作を実行したい場合は、最善の方法の最悪の場合の時間の複雑さはどれくらいですか？

ソートされた配列の最後にN個の要素を直接挿入できるので、O（N log（2N））でなければならないと思います。すべての挿入の後、我々は2N要素を持ち、2N配列全体に対してO（2N log（2N））〜O（N log（2N））を取る安定したソートアルゴリズムを実行することができる。

しかし、どこでもO（N^2）という名前が付いていますソートされた配列の間に各挿入のためのスペースを作ることによって、各挿入の後にソートされた配列！

私のアプローチは間違っていますか？挿入するたびに並べ替えられた配列をソートしておく必要がありますか？ 「はい」の場合は、「この一連の操作の後にデータ構造を維持するのではなく、各操作後にデータ構造を維持する」ルールがすべてのデータ構造に対して有効ですか？

Answer 1

必要なものによって異なります。

各挿入の後にいくつかの操作を行う必要がある場合は、O(n^2)が標準です（正しい場所はO(lgn)であり、シフト要素はO(n)です）。

あなたは、挿入の間に何もする必要がない場合は、操作全体がO(nlgn)をとるように終わりにしてソートO(nlgn)内のすべての要素を挿入します（最後に挿入を想定したがO(1)時間がかかります）。 *私たちは、各挿入後にソートソートされた配列を維持する必要がありますか？*私は知らないO(nlg(n))