この記事は paiza Advent Calendar 2021 の1日目の記事です。
QuickSort(クイックソート)が、ちょっと話題になっているようですね。
平均計算量がO(n log n)というのは知識として知っている人もいると思いますが、なぜそうなるのかは証明を見る機会は少ないと思い、調べてみました。
Wikipediaには3つの証明が書かれていますが、ここでは一番簡単そうな方法、4分割法とでもいうでしょうか、を紹介します。
４分割法
クイックソートで配列を分割するとき、なるべく真ん中で分割する方が効率がよくなります。
分割時のピボット要素の順序が比較的真ん中の1/4〜3/4になる確率は50%です。これを幸運な場合と呼びます。
幸運な場合の中で最悪の場合は、配列が25%と75%に分割される場合です。分割のたびに、幸運が続き、この分割を繰り返すといつか分割された配列は一つになります。
つまり、分割回数をdとすると、幸運な場合の中で最悪の場合、以下の様になります。
$ 1 = n * (\frac{3}{4})^d $
変形すると
$ (\frac{4}{3})^d = n $
さらに変形して
$ d = log_{\frac{4}{3}} n $
これが、幸運な場合の最悪分割回数になります。
次に、残りの50%の不運な場合も考えます。不運な場合については、もう一回分割を行なってみます。それでも不運なら、もう一度分割、、、とするといつか幸運な場合が訪れます。平均すると、半分の確率で幸運は訪れるので、ずっと幸運な場合の平均2倍の分割回数になります。
つまり、$ 2 * log_{\frac{4}{3}} n $ となります。
分割回数ごとにn回の比較があるのでn倍になります。
これを、数字を消してO記法にすると、
$ O(n * log(n)) $
となります。
他の方法
漸化式を用いる方法、２分探索木と対応させる方法があるようです。