中央値の中央値
「5」は、中央値の中央値アルゴリズムが動くもののなかで最小値であるため。もし7個ずつ以上、 2 m + 1 ( m = 3 , 4 , 5... ) {\displaystyle 2m+1(m=3,4,5...)} 個ずつの小配列に分割した場合、まず、小配列の中央値を抽出した配列の要素数は 1 2 m + 1 n {\displaystyle {\frac {1}{2m+1}}n} 個になる。また、各小配列の中に存在するピボット値以下・以上の値はそれぞれ m + 1 {\displaystyle m+1} 個ずつとなるので、次の探索対象の配列は要素数が 1 2 m + 1 n × 1 2 × ( m + 1 ) = m + 1 4 m + 2 n {\displaystyle {\frac {1}{2m+1}}n\times {\frac {1}{2}}\times (m+1)={\frac {m+1}{4m+2}}n} 個減少するので、残るのは ( 1 − m + 1 4 m + 2 ) n = 3 m + 1 4 m + 2 n {\displaystyle \left(1-{\frac {m+1}{4m+2}}\right)n={\frac {3m+1}{4m+2}}n} 個になる。ゆえに、結局、前者と後者を合わせて 3 m + 3 4 m + 2 n {\displaystyle {\frac {3m+3}{4m+2}}n} 個の要素に対して選択アルゴリズムを必要とする。
前述のように、中央値の中央値はクイックセレクトのピボット値選択で用いられる。クイックセレクトを擬似コードで書くと以下のようになる。
先述の通り、このPivotに中央値の中央値を適用すると、計算される値pivotが全体の配列のおおよその中央値となる。 具体的には以下の手順で計算できる。
まず、入力の配列array(要素数n=end-start)を、5個以下ずつの小配列に分割し、それぞれの小配列の中での中央値を計算する。
各小配列の中でそれぞれ計算された中央値を集めた配列を作成し(要素数はn/5に減少している)、またその中での中央値を求める。中央値の計算は選択アルゴリズムにほかならないので、つまり、再帰的にクイックセレクトを実行する。
ここでMedian5では、小配列(5要素以下)の中央値を計算する(例えば挿入ソートなどを使う)。
このように、PivotはSelectを呼び出しており相互再帰となっている。
中央値の計算は再帰呼び出しとなっているが、最悪の場合でも線形である。なぜなら、 T ( n ) {\displaystyle T(n)} をn個の配列に中央値の中央値を適用したクイックセレクトを適用した時の処理時間とすると、
T ( n ) ≤ T ( 2 10 n ) + C n + T ( 7 10 n ) {\displaystyle T(n)\leq T\left({\frac {2}{10}}n\right)+Cn+T\left({\frac {7}{10}}n\right)}
だからである。ここで
T ( 2 10 n ) {\displaystyle T\left({\frac {2}{10}}n\right)} の項は、各小配列から中央値のみを抽出した配列(要素数が必ず元の配列のの要素数の2割)から真の中央値、つまりピボット値を計算するための処理時間(中央値の計算は選択アルゴリズムの特別な場合であり、クイックセレクトの再帰呼び出しで計算可能であるので):計算手法で示したコード上では、初回の反復におけるPivotの処理時間
中央値の中央値(ちゅうおうちのちゅうおうち、英: median of medians)とは、クイックセレクトに基づく選択アルゴリズムのことである。k番目に大きい要素を選択するための最悪計算時間が線形になることが特徴である。
このアルゴリズムでは、最初におおよその中央値を線形時間で探索し、その値をクイックセレクトでのピボット値とする。つまり、(漸近的な)おおよその中央値選択アルゴリズムを使って、(漸近的な)一般値選択アルゴリズムを構築したものである。
このアルゴリズムは、マヌエル・ブラムらによって開発されたもので、著者の名字の頭文字を取ってBFPRTとも呼ばれる。この原著では中央値の中央値アルゴリズムをPICKと呼び、クイックセレクトをFINDと呼んでいた。