読者です 読者をやめる 読者になる 読者になる

LifeTimeException@hrk623

This is my breakpoints and stack-trace for my life

クイックセレクト(Quick Select)

アルゴリズム

 今回は選択アルゴリズムの紹介です。
これは、配列からk番目に小さい数を線形時間で
探しだすクイックセレクト(Quick Select)という
クイックソートの派生アルゴリズムです。

問題

 ソートされていないa1からanまでの数字がn個あり、
その中からk番目に小さい数字を探せ。

 例:
サイズが9の配列、[2, 5, 3, 7, 1, 8, 6, 0, 4]において、
3番目に小さい数は2です。

解1:ソートする。

 ソートしてk番目の数字を取る方法です。
ソートにθ(nlogn)と見つけるのにθ(n)なので、T(n) ∈ θ(nlogn)

解2:選択ソート的解

 リストから一番小さい数字を見つけ、取り出します。
これをk回繰り返します。
リストから最小値を見つけるのにO(n)なので
T(n) ∈ O(kn)です。

解3:ヒープソートの利用

 ヒープソートの構成にO(n)、取り出しにO(logn)なので
T(n) ∈ O(n+klogn)です。

解4:クイックセレクト(Quick Select)

 本題です。クイックソートのアルゴリズムを少し変えた解で
平均ケースでT(n) ∈ O(n)を実現します。

 ランダム、または何らかの法則でピボットを選び、
クイックソートと同じように再帰しソート処理を行います。
そして、ピボットより小さい数値のリストのサイズが
k-1であればピボットを返します。

擬似コード:

QuickSelect({a1, ..., an}, k)
 if n = 1 then return a1
 pick pivot x ∈ {a1, ..., an} at random
 L ← {ai : ai < x}
 R ← {ai : ai > x}
 l ← |L|
 if k = l+1 then return x
 else if k ≦ l then return QuickSelect(L, k)
 else return QuickSelect(R, k-l-1)

 左に再帰する際のサイズはl、右にはn-lとなります。
しかも、今回はどちらか一方にしか再帰しないので、
それぞれの再帰処理でT(max {l, n-l})として考えれば
上界が分かります。
最悪ケースは、l = 1 または l = nの時で

T(n) = T(n - 1) + θ(n) ∈ O(n^2)

理想は、毎回l =n/2をとる事で

T(n) = T(n/2) +θ(n) ∈ θ(n)

 つまり、クイック選択で理想値に近づくには
「良いピボットを選ぶ」事が必要不可欠です。

良いピボット

 では、良いピボットとは何か?と言うところから。
もちろん、n/2になるような中央値が最適です。
しかし、k個目に小さい数字を探すアルゴリズムを作るのに
n/2個目に小さい数字を探すアルゴリズムを使うなんて何だか変ですよね。
ここは少し、範囲を広めます。

「n/4 < l < 3n/4なるようなピボットxは良いピボットである」といいます。
なぜでしょうか。

確率Pr(n/4 < l < 3n/4) = 1/2で、
max{l, n-l} ≦ 3n/4ですから、
良いピボットを得るための必要ピボット取得回数の期待値は2となります。
これにより、
T(n) ≦ T(3n/4) +2θ(n)となり
T(n) = T(3n/4) +θ(n) ∈ θ(n)と言えます。

つまり、xが良いピボットであれば、期待ケースが Θ(n)となるのです。

では、そのようなピボットをどうやって見つけるのかです。
これには中央値の中央値(Median of Medians)と言う方法を使います。

中央値の中央値(Median of Medians)

問題:

 クイック選択のアルゴリズムにおいて、
n/4 < l < 3n/4になるようなピボットをO(n)で見つけろ。

 要は正確でなくてもいいから、大体の中央値を見つけるアルゴリズムです。
以下は、中央値の中央値を組み込んだクイックセレクトです。


QuickSelect({a1, ..., an}, k)
 if n = 1 then return a1

 // ここから中央値の中央値
 split {a1, ..., an} into groups G1, ..., Gn/5 each with 5 numbers
 for i ← 1 to n/5 do
  xi ← median of Gi // θ(1) since always 5 numbers or less
 x ← QuickSelect({x1, ..., xn/5}, n/10)
 // ここまで中央値の中央値

 L ← {ai : ai < x}
 R ← {ai : ai > x}
 l ← |L|
 if k = l +1 then return x
 else if k ≦ l then return QuickSelect(L, k)
 else return QuickSelect(R, k-l-1)

 ピボットの取り方だけが変わって、それ以外は同じですね。

では、なぜ中央値の中央値法は正しいのでしょうか。

 まずは一つ例を見てみます。
{7, 5, -3, 2, 1, 0, 4, 15, 25, 99, 3, -10, -1, 8, 9}で試します。
数字は15個あり、中央値の中央値法で選んだピボットが
(15)/4 < l < 3(15)/4の範囲に入るかどうか見てみましょう。

 まず、それぞれが5つの数字を持つようなグループに区切ります。
   G1 = {7, 5, -3, 2, 1}
   G2 = {0, 4, 15, 25, 99}
   G3 = {3, -10, -1, 8, 9}

 つぎに、それぞれの中央値を取ります。
   x1 = 2
   x2 = 15
   x3 = 3

 ここで一旦QuickSelectに再帰され、
中央値の中の中央値を返してきます。
   x = QuickSelect({2, 15, 3}, 1) = 3

 これで中央値の中央値は3となりました。
3をピボットとした場合、l = 6となり、
(15)/4 < 6 < 3(15)/4にちゃんと収まりましたね。

軽く証明:

 中央値の中央値で得られたピボットxを使うと
必ずn/4 < l < 3n/4になる事の証明です。

 まず、ピボットxは各グループG1,..., Gn/10
中央値の集合{x1, ..., xn/5}の中の
中央値をとってるわけですから、
約n/10個のxiはxより小さい事になります。
先程の例で言うと、x > x1です。

 さらに、それらの中央値より小さい数が、
それらのグループ内に2つある事になります。
x1 > 1, x1 > -3, x1 = 2, x1 < x
⇒ x > 1, x > -3, x > x1

 つまり、x ≧ 3n/10個の数となり、
これは l ≧ 3n/10となります。
同様に、x ≦ 3n/10個の数となり、
l < 7n/10です。

 よって、n/4 < 3n/10 <= l ≦ 7n/10 < 3n/4となり、
n/4 < l < 3n/4が証明されます。

クイック選択の解析

 さて、中央値の中央値の解説で
3n/10 <= l <= 7n/10が証明されたので、
max{l, n-l} <= 7n/10と言う事言えるようになりました。
なので、

   T(n) = T(n/5) + T(7n/10) + θ(n)

となります。
中央値を取るのに T(n/5)、
片方の再帰に T(7n/10) 、分割にθ(n)です。

それでは、今度はこの再帰式の解析です。
単純にみて、 T(n/5) + T(7n/10) = T(9n/10)なので、
小さくなっていってると見れます。なので、
とりあえずO(n)だろうと予想し置き換え法で計算します。

   T(n) = T(n/5) + T(7n/10) + an if n > 1
     or
   T(n) = 1 if n = 1

ですから、

T(n) ≦ cn for c > 0であることを証明します。
T(n) = T(n/5) + T(7n/10) + an
  ≦ c5/n + c7n/10 + an
⇒  n(c/5 + 7c/10 +a ) ≦ cnを証明します。
⇒  c/5 + 7c/10 + a ≦ c
⇒  c/10 ≧ a
⇒  c ≧ 10a
なので、c ≧ 10aである限りT(n) ∈ O(n)といえます。

お疲れ様でした。