6
1

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 1 year has passed since last update.

クイックソート (QuickSort) の平均計算量の簡単な証明

Last updated at Posted at 2021-11-30

この記事は paiza Advent Calendar 2021 の1日目の記事です。

QuickSort(クイックソート)が、ちょっと話題になっているようですね。
平均計算量がO(n log n)というのは知識として知っている人もいると思いますが、なぜそうなるのかは証明を見る機会は少ないと思い、調べてみました。

Wikipediaには3つの証明が書かれていますが、ここでは一番簡単そうな方法、4分割法とでもいうでしょうか、を紹介します。

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)) $

となります。

他の方法

漸化式を用いる方法、2分探索木と対応させる方法があるようです。

参考

Wikipedia QuickSort - Using percentile

Analysis of quicksort

6
1
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
6
1

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?