Aritalab:Lecture/Algorithm/Quicksort

クイックソートのアルゴリズムは、ソートのページを参照してください。

平均計算量

ピボットをランダムに選ぶクイックソートの平均計算量は、2 n log_e n = 1.4 n log₂ n といわれます。 その値を導出しましょう。

長さ n の配列をソートする手間数を C_n と書くと、以下の漸化式を満たします。

C₀ = 0

C_n = (n-1) + (2/n) ∑^n-1_k=0 C_k

両辺を n 倍して、その式で n を (n-1) と置き換えたものを引き算すると

n C_n - (n-1) C_n-1 = 2 (n-1) + 2 C_n-2 (n > 1)

この式は n = 1 のとき　C₁　= 0 となるので、n > 0 で成立します。 つまり、漸化式は

C₀ = 0

n C_n = (n + 1) C_n-1 + 2 (n-1)

と書き直せます。 和の因子として s_n = 2 / n(n+1) を導入すると、漸化式の一般解を用いて解くことができ、

C_n = 2(n+1) ∑ⁿ_k=1 1 /(k+1)

となります。

最後に、調和数 (Harmonic number) Η_n = ∑ⁿ_k=1 1 / k を導入します。

∑ⁿ_k=11 /(k+1) = ∑ⁿ⁺¹_k=2 1 / k

= -1 + 1/(n+1) + ∑ⁿ_k=11 / k

= - n / (n+1) + Η_n

調和数は Η_n = log_e n ですから、 C_n ≒ 2n log_e n となります。