2^N配列の挿入ソートの時間の複雑さ？

Question

インデックスX（0≦X < 2N）の要素がX xor 3（つまり、Xの2つの最下位ビットが反転されている）の2^Nのサイズを持つ整数の配列を考えてみましょう。この配列の挿入ソートの実行時間はどれくらいですか？

Answer 1

リストがどのように見えるかの構造を調べ、N = 3の場合

{3、2、1、0}

：N = 2の場合

を

{ 3、2、1、0、7、6、5、4}

挿入ソートの場合、1から現在のインデックスまでのリストがソートされているので不変であるため、それぞれステップはcを配置することですそれ以前のソートされた要素の中の正しい場所です。最悪の場合、現在の値を挿入する前に、以前のすべてのインデックスをトラバースする必要があります（リストが逆ソート順である場合を考えてください）。しかし、上記の構造から明らかなように、各値がインデックス^ 3に等しいというプロパティを持つリストの場合、指定されたインデックスから移動しなければならないリストの中で最も遠いものは3です。したがって、あなたはO（n）を挿入段階で一定の要素に作用させなければならない可能性があります。しかし、リストの各要素を調べるためにはまだO（n）の作業をしなければなりません。したがって、この特定のケースでは、挿入ソートの実行時間は入力のサイズに対して線形ですが、最悪の場合は2次です。