中央値の中央値

中央値の中央値（Median of Medians）とは

中央値の中央値（Median of Medians）は、クイックセレクトという選択アルゴリズムのピボット選択戦略の一つです。このアルゴリズムは、k番目に大きい要素を線形時間で選択できることを保証します。つまり、最悪の場合でも効率的に要素を選択できる強力な手法です。

アルゴリズムの概要

中央値の中央値アルゴリズムは、まず入力配列を5要素ずつの小さなグループに分割します。各グループの中央値を計算し、それらの中央値を集めた配列の中央値を求めます。この中央値の中央値が、クイックセレクトのピボット値として使用されます。

このピボット値を選択することで、クイックセレクトのパフォーマンスを安定させ、最悪の場合でも線形時間で動作することを保証します。このアルゴリズムは、マヌエル・ブラムらによって開発され、その頭文字を取ってBFPRTとも呼ばれています。元論文では、中央値の中央値アルゴリズムをPICK、クイックセレクトをFINDと呼んでいます。

クイックセレクトと中央値

クイックセレクトは、分割統治法に基づくアルゴリズムで、各段階で要素数を指数関数的に減少させることで線形時間の計算量を実現します。しかし、ピボット値の選択によっては要素数の減少が遅くなり、最悪の場合には二乗時間の計算量になる可能性があります。特に、各段階で最小値がピボットとして選択されると、この問題が発生しやすいです。

理想的なピボット値は、要素をほぼ均等に分割できる中央値です。中央値を使えば、各段階で探索対象の要素数を半分に減らすことができ、全体の計算量を線形に保てます。中央値の中央値アルゴリズムでは、正確な中央値ではなく、30%から70%の範囲にあるおおよその中央値を使用します。これにより、探索対象の要素数が各段階で一定割合で減少し、線形時間を達成します。

計算手法の詳細

中央値の中央値アルゴリズムは、以下の手順で動作します。

1. 分割: 入力配列を5要素以下の小配列に分割します。
2. 中央値の計算: 各小配列の中央値を計算します。
3. 中央値の中央値: 各小配列の中央値を集めた配列を作成し、その中から中央値を再帰的に求めます。
4. ピボットの選択: 計算された中央値の中央値をクイックセレクトのピボット値として使用します。
5. クイックセレクト: ピボット値に基づいて配列を分割し、必要な要素を再帰的に選択します。

このアルゴリズムは、ピボット値の計算に再帰的にクイックセレクトを利用します。中央値の計算には、挿入ソートなどの簡単なアルゴリズムが用いられます。

ピボット値の特性

中央値の中央値は、以下の特性を持ちます。

5要素の小配列のうち、約半数の中央値はピボット値以下です。
各小配列には、中央値以下の要素が少なくとも3つ存在します。
結果として、ピボット値以下の要素は全体の約30%以上になります。
同様に、ピボット値以上の要素も全体の約30%以上になります。
これにより、次の探索対象の要素数は元の要素数の最大70%に減少します。

例として、100個の乱数で中央値の中央値を計算する様子を図示すると、ピボット値（赤色）より左上には、ピボット値以下の要素（灰色）が、右下にはピボット値以上の要素（白色）が分布していることがわかります。

線形時間の証明

中央値の中央値アルゴリズムの計算時間は、最悪の場合でも線形時間です。これは、以下の漸化式で表されます。


T(n) ≤ T(n/5) + Cn + T(7n/10)


ここで、T(n)はn個の要素に対する処理時間、Cnはピボット選択と分割にかかる線形時間です。この漸化式を解くと、T(n)がO(n)であることが証明できます。

具体的には、

T(2n/10)の項は、中央値を集めた配列に対する再帰呼び出しの時間（要素数は元の配列の20%）。
Cnの項は、ピボット値を使った配列の分割時間。
T(7n/10)の項は、次の探索対象の配列に対する再帰呼び出しの時間（要素数は最大で元の配列の70%）。

この式は、最終的に T(n) ≤ 10Cn となり、O(n)の線形時間であることが示されます。

小配列への分割方法

なぜ5要素ずつの小配列に分割するのか？主な理由は以下の通りです。

奇数要素: 中央値の選択が容易であること。偶数要素では、中央値が2つになるため平均を計算する必要がある。
最小要素数: 中央値の中央値アルゴリズムが有効に機能するために、5要素以上が必要。
* 効率的な削減: 3要素ずつの場合、探索対象の要素数を減らせず、計算時間が線形にならない。7要素以上の場合、分割処理や中央値計算に時間がかかり、性能向上が見込めなくなる。

一定数の小配列に分割するのではなく、一定要素数ずつの小配列に分割するのは、要素数の減少が確実になるためです。要素数が一定の小配列では、中央値を計算した後に探索対象の要素数が減らない可能性があります。

クイックソートにおける利用

中央値の中央値アルゴリズムは、クイックソートのピボット選択にも使えます。最悪計算時間をO(n log n)に抑えられますが、平均的には乱数によるピボット選択の方が高速です。

イントロセレクトでの利用

中央値の中央値は、イントロセレクトでも利用されます。イントロセレクトは、最初はクイックセレクトで計算し、必要に応じて中央値の中央値に切り替えることで、最悪の場合でも線形時間を保証します。

まとめ

中央値の中央値は、クイックセレクトのピボット選択を安定させ、最悪の場合でも線形時間で動作することを保証する重要なアルゴリズムです。その計算手法と特性を理解することで、効率的な要素選択を実装できます。

もう一度検索