中央値の中央値

中央値の中央値

クラス	選択アルゴリズム
データ構造	配列
最悪計算時間	$\mathrm {O} (n)$
最良計算時間	$\mathrm {O} (n)$
最悪空間計算量	$\mathrm {O} (1)$

中央値の中央値（ちゅうおうちのちゅうおうち、英: median of medians）とは、クイックセレクトに基づく選択アルゴリズムのことである。k番目に大きい要素を選択するための最悪計算時間が線形になることが特徴である。

このアルゴリズムでは、最初におおよその中央値を線形時間で探索し、その値をクイックセレクトでのピボット値とする。つまり、（漸近的な）おおよその中央値選択アルゴリズムを使って、（漸近的な）一般値選択アルゴリズムを構築したものである。

このアルゴリズムは、マヌエル・ブラムらによって開発されたもので、著者の名字の頭文字を取ってBFPRTとも呼ばれる。この原著では中央値の中央値アルゴリズムをPICKと呼び、クイックセレクトをFINDと呼んでいた。

概要

クイックセレクトは分割統治法であり、計算の各段階で、残っている探索対象の要素が$n$個の場合に$\mathrm {O} (n)$の計算時間を必要とする。そのためクイックセレクト全体の計算量は、

• もし探索対象の要素数を（一定の割合で）指数関数的に減少させられるなら、等比級数と1段の計算量($\mathrm {O} (n)$)の積、つまり線形時間$\mathrm {O} (n)$となる。
• しかし、要素数の減少がとても遅い（例えば、減少する要素数が一定、最悪の場合1つずつしか減らないような線形減少の）場合、各段の計算量の線形和となり、2次時間$\mathrm {O} (n^{2})$となる（三角数は2次となる）。

最悪時間となる場合は、例えば、各段階でピボット値として最小値を選んでしまう時である。これは、既に降順に並び替え済みの配列に対して、最初の要素をピボット値として選択してしまうと実際に起こりうる。

つまり、もし各段階で一貫して「良いピボット値」を選択し続けられるなら、このような最悪の場合を回避することができ、最悪の場合でも線形時間の性能となる。この「良いピボット値」では、全ての要素を一定の割合でより大きい値と小さい値に分割することができ、つまり探索対象の要素数を一定の割合で減らすことができ、ゆえに要素数が指数関数的に減少して、全体的な計算時間は線形のままとなる。

中央値は、そのような「良いピボット値」であり、各段階で探索対象を半分ずつに減らすことができる。ゆえに、もし中央値を線形時間で計算できるなら、各段階では線形時間しか増えないので、全体の計算量は線形時間のままとなる。

中央値の中央値アルゴリズムでは、正確な中央値ではなく、代わりに、30から70パーセンタイルの間（第4十分位数の中間）点であることが保証されたおおよその中央値を使用する。そのため、探索対象の要素数は各段階で一定の割合（最小で30%）で減少する（つまり最大で70%が残る）。 一方、ピボット値計算の増加量は各段階では線形となる（元の探索対象の要素数の20%の要素に対する再帰と、線形時間の和）。よって、各段階で問題の要素数は元の要素数の90%(20%+70%)という一定の割合で削減されるので、全体としての計算量は、要素数$n$に対して線形$\mathrm {O} (n)$である（線形性の厳密な証明は後述）。

計算手法

前述のように、中央値の中央値はクイックセレクトのピボット値選択で用いられる。クイックセレクトを擬似コードで書くと以下のようになる。

// 配列arrayのk番目に大きい要素を計算する
// ただし、探索範囲はstart番目からend番目まで
Value Select(Array<Value> array, Index k, Index start, Index end)
{
	Index pivotIndex;
	do
	{
		// ピボット値を計算する
		Value pivot = Pivot(array, start, end);

		// 領域を分割して、ピボット値の位置を計算する
		pivotIndex = Partition(array, start, end, pivot);

		// ピボット値がk番目より左にあったら
		// k番目の要素はピボット値の位置より右にあるので
		// 次の探索開始地点はピボット値の右隣から
		if(pivotIndex < k)
		{
			start = pivotIndex + 1;
		}
		// ピボット値がk番目より右にあったら
		// k番目の要素はピボット値の位置より左にあるので
		// 次の探索終了地点はピボット値の左隣まで
		else if(pivotIndex > k)
		{
			end = pivotIndex - 1;
		}
	} while(pivotIndex != k) // 最終的にピボットの位置がk番目になったら完了
	return array[k];
}

先述の通り、このPivotに中央値の中央値を適用すると、計算される値pivotが全体の配列のおおよその中央値となる。 具体的には以下の手順で計算できる。

1. まず、入力の配列array（要素数n=end-start）を、5個以下ずつの小配列に分割し、それぞれの小配列の中での中央値を計算する。
2. 各小配列の中でそれぞれ計算された中央値を集めた配列を作成し（要素数はn/5に減少している）、またその中での中央値を求める。中央値の計算は選択アルゴリズムにほかならないので、つまり、再帰的にクイックセレクトを実行する。

// 配列arrayのstart番目からend番目までの中でピボット値を計算する
Value Pivot(Array<Value> array, Index start, Index end)
{
	Array<Value> medians;

	// 先頭から5個ずつの小配列に分割する
	for(Index i = start; i < end; i += 5)
	{
		// 小配列の開始地点と終了地点
		Index subStart = i;
		Index subEnd = max(i+4, end);

		// 小配列（5要素）の中央値を計算する
		Value median = Median5(array, subStart, subEnd);

		// 結果を格納する
		Index j = (i - start)/5;
		medians[j] = median;
	}

	// 各小配列の中央値を集めた配列の中で、さらに中央値を計算する（中央値の中央値）
	Index n = ceil((end - start)/5);
	start = 0;
	end = n - 1;
	Index k = n/2;
	return Select(medians, k, start, end);
}

ここでMedian5では、小配列（5要素以下）の中央値を計算する（例えば挿入ソートなどを使う）。

このように、PivotはSelectを呼び出しており相互再帰となっている。

ピボット値の特性

中央値の中央値をピボット値として採用すると、ピボット値は以下の様な特性を持つ。

${\frac {n}{5}}$個の小配列に分割した時、その小配列のうち半数（${\frac {n}{5}}\times {\frac {1}{2}}={\frac {n}{10}}$個）の小配列では、各小配列の中央値がピボット値（中央値の中央値）以下である。また、各小配列の中には、必ず各中央値以下である要素が3個存在する。よって、その${\frac {n}{10}}$個の各小配列には、ピボット値以下の要素が少なくとも3個以上存在するはずなので、全体としては、${\frac {3n}{10}}$個の要素がピボット値以下である。 同様に、もう半数の小配列には、ピボット値以上の要素が少なくとも3個以上存在するはずなので、全体としては、${\frac {3n}{10}}$個の要素がピボット値以上である。

よって、そのピボット値を使用して配列を2分割をした時、その分割点は少なくとも上位30%から70%の間に存在することになるので、次の探索対象となる配列の要素数は、必ず元の配列の要素数の一定の割合（最悪でも3割、最善だと7割）に減少させることができる。

例として、0から99までの100個の乱数列での中央値の中央値を考えると以下のようになる。

0から99までの100個の乱数列での中央値の中央値

	12		15		11		2		9		5		0		7		3		21		44		40		1		18		20		32		19		35		37		39
	13		16		14		8		10		26		6		33		4		27		49		46		52		25		51		34		43		56		72		79
中央値	17		23		24		28		29		30		31		36		42		47		50		55		58		60		63		65		66		67		81		83
	22		45		38		53		61		41		62		82		54		48		59		57		71		78		64		80		70		76		85		87
	96		95		94		86		89		69		68		97		73		92		74		88		99		84		75		90		77		93		98		91

ここで、背景が

• 赤色：ピボット値（中央値の中央値）
• 灰色：ピボット値（中央値の中央値）以下の要素
• 白色：ピボット値（中央値の中央値）以上の要素

である。

また、（5要素ずつの）各小配列の中では昇順で並び替えて可視化してあるので、3行目が各小配列の中央値のみを抽出した配列になっている（実際には並び替える必要はなく、可視化の都合である。実際には各小配列の中での中央値さえ計算できればよい）。 加えて、小配列自体はその中央値同士を比較して昇順で並び替えて可視化してあるので、最終的に、赤色のピボット値より左上にある（30個＝元の配列の要素数の3割の）値は、必ずピボット値以下である。また同様に、右下にある値は必ずピボット値以上であることが分かる。

処理時間が線形であることの証明

中央値の計算は再帰呼び出しとなっているが、最悪の場合でも線形である。なぜなら、$T(n)$をn個の配列に中央値の中央値を適用したクイックセレクトを適用した時の処理時間とすると、

$T(n)\leq T\left({\frac {2}{10}}n\right)+Cn+T\left({\frac {7}{10}}n\right)$

だからである。ここで

• $T\left({\frac {2}{10}}n\right)$の項は、各小配列から中央値のみを抽出した配列（要素数が必ず元の配列のの要素数の2割）から真の中央値、つまりピボット値を計算するための処理時間（中央値の計算は選択アルゴリズムの特別な場合であり、クイックセレクトの再帰呼び出しで計算可能であるので）：計算手法で示したコード上では、初回の反復におけるPivotの処理時間
• $Cn$の項は、ピボット値を使って配列を2分割して次の探索対象の配列を作成するための処理時間（ピボット値と各小配列から中央値のみを抽出した配列の各要素との比較処理であり、比較処理は定数時間$\mathrm {O} (1)$で計算可能であるので）：計算手法で示したコード上では、初回の反復におけるPartitionの処理時間
• $T\left({\frac {7}{10}}n\right)$の項は、分割した後の次の探索対象の配列（要素数は最悪でも元の配列の要素数の7割）でk番目に大きい要素を計算する最大の処理時間（クイックセレクトを再帰的に適用することと等価なので）：計算手法で示したコード上では、次の反復以降にかかる処理時間。

この式は簡単に解けて、最終的には以下のように線形時間$\mathrm {O} (n)$であることを示すことができる。

$T(n)\leq 10Cn\in \mathrm {O} (n)$

小配列への分割方法

先述の通り、本項で説明した中央値の中央値アルゴリズムでは、配列全体を5要素ずつの小配列に分割した。5要素ずつに分割した理由については以下のように説明できる。

• 奇数個の要素から成る小配列に分割するのが高速かつ簡便なため。偶数個の要素から成る小配列に分割することもできるが、その場合、真ん中の要素は2つになってしまい、中央値はその平均をとらなければならないので、唯一の中央値を簡単に選択できる奇数個に比べて遅くなる。
• 中央値の中央値アルゴリズムが動くのは1つの小配列には5要素以上が必要なため。もし3要素ずつしかない場合、小配列の中央値を抽出した配列の要素数は${\frac {1}{3}}n$個になる。また、各小配列の中に存在するピボット値以下・以上の値はそれぞれ2つずつとなるので、次の探索対象の配列は要素数が最悪でも${\frac {1}{3}}n\times {\frac {1}{2}}\times 2={\frac {1}{3}}n$個減少するので、残るのは$\left(1-{\frac {1}{3}}n\right)={\frac {2}{3}}n$個となる。ゆえに、結局、前者と後者を合わせて$n$個の要素に対して選択アルゴリズムを必要としてしまうので、要素数が全く減らないことになる。
• 「5」は、中央値の中央値アルゴリズムが動くもののなかで最小値であるため。もし7個ずつ以上、$2m+1(m=3,4,5...)$個ずつの小配列に分割した場合、まず、小配列の中央値を抽出した配列の要素数は${\frac {1}{2m+1}}n$個になる。また、各小配列の中に存在するピボット値以下・以上の値はそれぞれ$m+1$個ずつとなるので、次の探索対象の配列は要素数が${\frac {1}{2m+1}}n\times {\frac {1}{2}}\times (m+1)={\frac {m+1}{4m+2}}n$個減少するので、残るのは$\left(1-{\frac {m+1}{4m+2}}\right)n={\frac {3m+1}{4m+2}}n$個になる。ゆえに、結局、前者と後者を合わせて${\frac {3m+3}{4m+2}}n$個の要素に対して選択アルゴリズムを必要とする。つまり、ここでmを大きくして小配列の要素数を増やしたとしても、結局、次の探索対象の要素数は${\frac {3}{4}}n$個、つまり元の要素数の75%にしかならない。一方で小配列の中の要素数が増えていくと、分割処理にも小配列の中での中央値を探すのにも時間がかかるようになってしまい、元の配列の要素数が充分に大きくなると全体的な性能向上には寄与しなくなってしまう。
• 別の分割方法として、要素数が一定の小配列ではなく一定数の小配列に分割する、つまり、要素数が5個ずつの小配列ではなく、5個の小配列に分割することを考える。しかしその場合は、明らかに要素数は減少させることはできない。なぜなら、要素数${\frac {1}{5}}n$個ずつの小配列5個の中で、それぞれ中央値を計算せねばならないが、結局、次の探索対象の要素数は${\frac {7}{10}}n$個にしかならないからである。つまり、3要素ずつに分割する時と同様に、個々の中央値を計算する配列の要素数は元の配列より少なくて済むが、結局、全体的な長さは短くならず、むしろ長くなってしまう。要素数が${\sqrt {n}}$個の小配列に分割しても、小配列の数は${\sqrt {n}}$個になり、同様である。

クイックソートにおける中央値の中央値

おおよその中央値選択アルゴリズムは、クイックソートのピボット値選択にも使用でき、最悪計算量を$\mathrm {O} (n\log n)$にすることもできる。しかし、典型的には、この方法より、乱数によるピボット値選択の方が良い性能を示し（そちらの方が、選択の平均計算量が線形で、並び替えの平均計算量が対数線形となるので）、ピボット値計算の計算量増加を避けることもできる。

イントロセレクト

中央値の中央値は、イントロセレクト（英語: introselect）の中でも使用される。イントロセレクトでは、最初はクイックセレクトで計算することで平均計算時間を改善し、もし処理に時間が掛かりそうな場合は中央値の中央値に切り替えることで最悪計算時間も線形に抑えることができる。

外部リンク

• "Lecture notes for January 30, 1996: Deterministic selection", ICS 161: Design and Analysis of Algorithms, David Eppstein