Skip to content →

選択アルゴリズム:線形

数列 \((a_i)_{1 \leq i \leq n}\) が与えられたとき、昇順で \(k\) 番目の項を \(O(n)\) で見つける選択アルゴリズムを紹介します。

アルゴリズム

数列 \(a\) の昇順 \(k\) 番目を返すアルゴリズムは次のようになります:

アルゴリズム \(\mathrm{order}(a, k)\)

  1. \(a\) を長さ \(5\) の数列 \(n/5\) 個に分けます。十分大きい数を \(a\) に加えても(\(k \leq n\) ならば)結果に変化はありませんから、オーダーを変えずに \(n\) を \(5\) の倍数だと仮定できます。
  2. 長さ \(5\) の数列それぞれの中央値からなる長さ \(n/5\) の数列 \(c\) を作ります。
  3. \(c\) の中央値 \(m=\mathrm{order}(c, \lfloor n/10 \rfloor)\) を見つけます。
  4. \(a\) を \(m\) 未満、\(m\) と等しい、\(m\) 以上の要素からなる数列 \(s_1,s_2,s_3\) に分割します。
  5. 次の3つのいずれかに場合分けします。
    1. \(k \leq |s_1|\) ならば
      return \(\mathrm{order}(s_1, k)\)
    2. \(|s_1| < k \leq |s_1|+|s_2|\) ならば
      return \(m\)
    3. \(|s_1|+|s_2| < k\) ならば
      return \(\mathrm{order}(s_1, k-|s_1|-|s_2|)\)

計算量解析します。\(m\) 以上の数は \(3n/10\) 個以上、\(m\) 以下の数も \(3n/10\) 個以上あります。従って、\(|s_1|, |s_3| \leq 7n/10\) です。このアルゴリズムの計算量を \(T(n)\) と置くと、$$T(n)=T(n/5)+T(7n/10)+O(n)$$ です。\(n/5+7n/10 < n\) より、\(T(n) = O(n)\) を得ます。

なぜ長さ 5 の数列に分割するのか

長さ \(5\) の数列に分解しましたが、ほかの長さだとどうなるでしょうか。長さ \(2d+1\) の数列に分解した場合、計算量は
$$T(n) = T\left(\frac{n}{2d+1}\right) + T\left(\left(1-\frac{d+1}{2(2d+1)}\right)n\right)+O(n)$$となります。解くと、\(d=1\) のとき \(T(n)=O(n\log(n))\), \(d\geq 2\) のとき \(T(n)=O(n)\) です。長さ 5 以上の奇数の数列に分解するのであれば、計算量はいつでも \(O(n)\) になりました。

クイックソート

クイックソートのピボットを、このアルゴリズムで中央値に選ぶと、worst \(\Theta(n\log(n))\) のソートができます。

関連記事

2次元線形計画問題:選択アルゴリズムを途中で用います。

定数個の数列に分割して、計算量改善するのはあまり見たことがなかったので驚き!

Published in データ構造

Comments

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です

CAPTCHA