まず、私は知っています
また、下限は O(nlogn) であることに同意します。
私がよく理解していないのは次のとおりです。
一部の特殊なケースでは、比較の数が実際には下限よりもさらに低くなる場合があります。たとえば、バブル ソートを使用して、既に並べ替えられた配列を並べ替えます。比較回数は O(n) です。
では、下限の考え方を実際に理解するにはどうすればよいでしょうか。
Wikipediaal の古典的な定義: http://en.wikipedia.org/wiki/Upper_and_lower_boundsはあまり役に立ちません。
これについての私の現在の理解は次のとおりです。
比較ベースの並べ替えの下限は、実際には最悪の場合の上限です。
つまり、最悪の場合に最善を尽くすことができます。
これは正しいです？ありがとう。
ソートの問題は次のように見ることができます。
入力: n 個の数字のシーケンス。出力: a'1 <= a'2 ….. <= a'n となるような入力シーケンスの順列 (並べ替え)。
並べ替えアルゴリズムは、比較演算子を使用して 2 つの数値の順序を見つける場合、比較に基づいています。比較ソートは、決定木の観点から抽象的に見ることができます。デシジョン ツリーは、特定のサイズの入力に対して動作する特定の並べ替えアルゴリズムによって実行される要素間の比較を表す完全なバイナリ ツリーです。ソート アルゴリズムの実行は、決定木のルートからリーフまでのパスをたどることに対応します。各内部ノードで、比較 ai aj が行われます。次に、左側のサブツリーは ai aj の後続の比較を指示し、右側のサブツリーは ai > aj の後続の比較を指示します。リーフに到達すると、ソート アルゴリズムによって順序付けが確立されます。したがって、決定木については次のように言えます。
1) それぞれの n! n 個の要素の順列は、並べ替えアルゴリズムが適切に並べ替えるために、決定木の葉の 1 つとして表示される必要があります。
2) x をソート アルゴリズムの最大比較回数とします。デシソン ツリーの最大の高さは x になります。最大の高さ x の木には、最大で 2^x の葉があります。
上記の 2 つの事実を組み合わせると、次の関係が得られます。
n! <= 2^x
両側でログを取ります。\log_2n! <= x
\log_2n 以来! = \Theta(nLogn), x = \Omega(nLog_2n) と言えます。したがって、比較ベースのソート アルゴリズムは、入力配列をソートするために少なくとも \Omega(nLog_2n) 回の比較を行う必要があり、ヒープソートとマージ ソートは漸近的に最適な比較ソートです。 .
並べ替え可能なすべての配列を想像してみてください。それらが長さ「n」の配列であり、1 つの要素を持つ配列のようなものを無視するとしましょう (もちろん、常に既にソートされています。
その配列のすべての可能な値の組み合わせの長いリストを想像してみてください。配列内の値には常に何らかの順序があるため、これを少し単純化できることに注意してください。したがって、最小のものを数値 1 に置き換え、次のものを 1 または 2 (等しいか大きいかによって) などに置き換えると、任意の値を許可した場合と同じ並べ替えの問題が発生します。(これは、長さ n の配列が最大で 1 から n の数値を必要とすることを意味します。いくつかが等しい場合は、それより少ないかもしれません。)
次に、それらの値を含む配列をソートするのにどれだけの作業が必要かを示す数字をそれぞれの横に付けます。複数の数字を入れることができます。たとえば、必要な比較の数を入れることができます。または、必要な要素の移動またはスワップの数を入れることもできます。そこに入力した数字は、必要な操作の数を示します。それらの合計を置くことができます。
あなたがしなければならないことの1つは、特別な情報を無視することです. たとえば、配列内の値の配置が既にソートされていることを前もって知ることはできません。アルゴリズムは、他の配列と同じようにその配列で同じ手順を実行する必要があります。（ただし、最初のステップは、ソートされているかどうかを確認することです。ただし、通常、それはソートには役立ちません。）
そう。比較によって測定される最大数は、値が病理学的に悪い方法で配置されている場合の典型的な比較数です。同様に、最小数は、値が非常に適切に配置されている場合に必要な比較の数です。
バブル ソートの場合、最良のケース (最短または最速) は、値が既に順序付けされている場合です。ただし、これはフラグを使用して、値を交換したかどうかを示す場合のみです。その最良のケースでは、隣接する要素の各ペアを 1 回見て、それらが既に並べ替えられていることを確認し、最後に到達したときに何も交換していないことがわかり、完了です。これは合計 n-1 の比較であり、実行できる比較の最小数を形成します。
最悪の場合を考えるのに時間がかかります。私は何十年もの間、バブルソートを見たことがありません。しかし、それらが逆順になっている場合だと思います。最初の比較を行うと、最初の要素を移動する必要があることがわかります。それぞれを比較して一番上までスライドし、最後に最後の要素と交換します。したがって、そのパスで n-1 の比較を行いました。2 番目のパスは 2 番目の要素から始まり、n-2 回の比較などを行います。したがって、この場合は (n-1)+(n-2)+(n-3)+...+1 回の比較を行います。これは約 (n**2)/2 です。
バブルソートのバリエーションは、私が説明したものよりも優れているかもしれません。どんなに。
バブル ソートの場合、下限は n-1 で、上限は (n**2)/2 です。
他のソート アルゴリズムは、より優れたパフォーマンスを発揮します。
比較以外にもコストがかかる操作があることに注意してください。多くのソートは文字列で行われ、文字列の比較は計算時間にコストがかかるため、比較を使用します。
要素のスワップ (またはスワップと要素のスワップの合計) を使用してカウントすることもできますが、通常は文字列との比較よりも短くなります。数字がある場合、それらは類似しています。
分岐予測の失敗やメモリ キャッシュ ミスなど、より難解なものを使用したり、測定したりすることもできます。
漸近解析を行う場合、すべての入力に対してOorΘまたは またはを導出します。
ただし、入力のプロパティがランタイムに影響するかどうかを分析することもできます。
たとえば、ほとんどソートされたものを入力として受け取るアルゴリズムは、入力の特性とアルゴリズムの構造により、正式な漸近式よりも優れたパフォーマンスを発揮します。例としては、バブルソートとクイックソートがあります。
下限を下回れるわけではありません。特定の入力に対する実装の動作のみです。Ω