61

QuickSort n log n の理由について、「平易な英語」の直感的でありながら正式な説明を提供できる人はいますか? 私の理解では、n個のアイテムをパスする必要があり、これをn回ログに記録します...このログをn回実行する理由を言葉で表現する方法がわかりません。

4

6 に答える 6

162

複雑

クイックソートは、入力を 2 つのチャンクに分割することから始めます。「ピボット」値を選択し、入力をピボット値より小さいものとピボット値より大きいものに分割します (もちろん、ピボット値に等しいものはすべてもちろん、どちらか一方に入りますが、基本的な説明では、それらがどちらに終わるかはあまり重要ではありません)。

入力は (定義により) ソートされていないため、そのように分割するには、入力内のすべての項目を調べる必要があるため、これは O(N) 操作です。初めて入力を分割した後、それらの「チャンク」のそれぞれを再帰的にソートします。これらの再帰呼び出しのそれぞれは、その入力のすべてを調べるため、2 つの呼び出しの間に、すべての入力値を (再度) 参照することになります。したがって、パーティショニングの最初の「レベル」では、すべての入力項目を調べる 1 つの呼び出しがあります。2 番目のレベルでは、2 つの分割ステップがありますが、2 つの間で、(再び) すべての入力項目が調べられます。連続する各レベルには、より多くの個別の分割ステップがありますが、全体として、各レベルでの呼び出しはすべての入力項目を調べます。

パーティションのサイズの下限に達するまで、入力をどんどん小さな断片に分割し続けます。可能性のある最小のものは、各パーティション内の単一のアイテムです。

理想的なケース

理想的なケースでは、各分割ステップが入力を半分に分割することを願っています。「半分」はおそらく正確には同じではありませんが、ピボットを適切に選択すれば、かなり近くなるはずです。計算を簡単にするために、完全な分割を仮定して、毎回正確な半分を取得します。

この場合、半分に分割できる回数は、入力数の 2 を底とする対数になります。たとえば、128 個の入力がある場合、64、32、16、8、4、2、および 1 のパーティション サイズが得られます。これは、7 レベルのパーティショニングです (そして、log 2 (128) = 7)。

そのため、log(N) のパーティショニング「レベル」があり、各レベルは N 個の入力すべてにアクセスする必要があります。したがって、log(N) レベルにレベルごとの N 操作を掛けると、O(N log N) 全体の複雑さが得られます。

最悪の場合

ここで、各パーティショニング レベルが入力を正確に半分に「分割」するという仮定をもう一度考えてみましょう。パーティショニング エレメントの選択の良し悪しによっては、完全に等しい半分が得られない場合があります。それで、起こりうる最悪の事態は何ですか？最悪のケースは、実際には入力内の最小または最大の要素であるピボットです。この場合、O(N) パーティショニング レベルを実行しますが、同じサイズの 2 つの半分を取得する代わりに、1 つの要素の 1 つのパーティションと N-1 要素の 1 つのパーティションになってしまいました。それがすべてのレベルのパーティショニングで発生した場合、パーティションが 1 つの要素になる前に、明らかに O(N) 個のパーティショニング レベルを実行することになります。

これにより、Quicksort の技術的に正しい big-O の複雑さが得られます (big-O は正式には複雑さの上限を指します)。O(N) レベルのパーティショニングがあり、各レベルには O(N) ステップが必要なので、O(N * N) (つまり、O(N 2 )) の複雑さになります。

実際の実装

実際問題として、実際の実装では通常、実際に 1 つの要素のパーティションに到達する前にパーティショニングを停止します。通常、パーティションに含まれる要素が 10 個以下の場合、パーティショニングを停止し、挿入ソートのようなものを使用します (通常、少数の要素の場合は高速になるため)。

変更されたアルゴリズム

最近では、O(N 2 ) の最悪のケースを防ぐ Quicksort の他の変更 (Introsort、PDQ Sort など) が発明されました。Introsort は、現在のパーティショニングの「レベル」を追跡することでこれを行います。深くなりすぎると、ヒープ ソートに切り替わります。これは、典型的な入力に対しては Quicksort よりも低速ですが、O(N log N) の複雑さを保証します。任意の入力に対して。

PDQ ソートはそれに別のひねりを加えます: ヒープ ソートは遅いため、可能な場合はヒープ ソートへの切り替えを回避しようとします。そのために、ピボット値が不十分であると思われる場合は、入力の一部をランダムにシャッフルしてから、ピボット。次に、十分に優れたピボット値を生成できない場合 (およびその場合にのみ)、代わりにヒープ ソートの使用に切り替えます。

于 2012-05-03T05:24:55.593 に答える
0

実際には、すべての N 要素 (ピボット) の位置を見つける必要がありますが、比較の最大数は各要素の logN です (最初は N、2 番目のピボットは N/2、3 番目の N/4 です。ピボットが中央値要素)

于 2016-02-21T05:27:43.950 に答える