arrays - 並べ替えと挿入の Big-O 実行時間

Question

したがって、クイックソートを使用して配列をソートする場合は、クイックソートを使用して O(nlogn) で実行できます。一度ソートすると、バイナリ検索風のアルゴリズムを使用して O(logn) の配列に新しい要素を挿入できます。

私の質問は、並べ替えられた配列に O(logn) 時間で挿入できる場合、並べ替えアルゴリズムが少なくとも O(nlogn) である必要があることを証明する方法はありますか?

言い換えれば、2 つのアルゴリズムの実行時間の間に関係はありますか?

Answer 1

さて、順序を維持する挿入が O(log n) であるということは、配列に各要素を順番に挿入するだけで、O(n log n) で並べ替え操作を実行できることを意味します。ただし、これはおそらく、実際に求めていることとは逆です。O(n log n) ソートがあることを証明していますが、より高速なソートの可能性を否定するものではありません。

Answer 2

いいえ: バブルソート (O(n²)) を使用して配列をソートすることは可能です。その後、同じアルゴリズムを使用して O(log(n)) 時間で挿入することも可能です。

Answer 3

まず、特別な条件を必要とする一部の並べ替えアルゴリズムでは、時間の複雑さが低下する可能性があります。たとえば、O(n+k) (k は配列内の最大数) の複雑さを持つカウント ソートや、O(n*k) (k は配列内の最大桁数) の複雑さを持つ基数ソートなどです。要素)。
O(nlogn) の境界は、比較アルゴリズムに適用されます。

第二に、質問に答えるには、いいえ（悲しいことに）。davmac が言ったように、挿入と並べ替えの関係は逆です。

比較の下限がある理由は、正しい順序を見つけるために少なくとも nlogn の比較が必要だからです。詳細については、比較ソート アルゴリズムに関するこの wiki ページを参照してください。教授は挿入とは何の関係もないことに注意してください（教授は実際には挿入を想定していません）。