クラス | 選択アルゴリズム |
---|---|
データ構造 | 配列 |
最悪計算時間 | |
最良計算時間 | |
最悪空間計算量 |
中央値の中央値(ちゅうおうちのちゅうおうち、英: median of medians)とは、クイックセレクトに基づく選択アルゴリズムのことである。k番目に大きい要素を選択するための最悪計算時間が線形になることが特徴である。
このアルゴリズムでは、最初におおよその中央値を線形時間で探索し、その値をクイックセレクトでのピボット値とする。つまり、(漸近的な)おおよその中央値選択アルゴリズムを使って、(漸近的な)一般値選択アルゴリズムを構築したものである。
このアルゴリズムは、マヌエル・ブラムら[1]によって開発されたもので、著者の名字の頭文字を取ってBFPRTとも呼ばれる。この原著では中央値の中央値アルゴリズムをPICKと呼び、クイックセレクトをFINDと呼んでいた。
クイックセレクトは分割統治法であり、計算の各段階で、残っている探索対象の要素が個の場合にの計算時間を必要とする。そのためクイックセレクト全体の計算量は、
最悪時間となる場合は、例えば、各段階でピボット値として最小値を選んでしまう時である。これは、既に降順に並べ替え済みの配列に対して、最初の要素をピボット値として選択してしまうと実際に起こりうる。
つまり、もし各段階で一貫して「良いピボット値」を選択し続けられるなら、このような最悪の場合を回避することができ、最悪の場合でも線形時間の性能となる。この「良いピボット値」では、全ての要素を一定の割合でより大きい値と小さい値に分割することができ、つまり探索対象の要素数を一定の割合で減らすことができ、ゆえに要素数が指数関数的に減少して、全体的な計算時間は線形のままとなる。
中央値は、そのような「良いピボット値」であり、各段階で探索対象を半分ずつに減らすことができる。ゆえに、もし中央値を線形時間で計算できるなら、各段階では線形時間しか増えないので、全体の計算量は線形時間のままとなる。
中央値の中央値アルゴリズムでは、正確な中央値ではなく、代わりに、30から70パーセンタイルの間(第4十分位数の中間)点であることが保証されたおおよその中央値を使用する。そのため、探索対象の要素数は各段階で一定の割合(最小で30%)で減少する(つまり最大で70%が残る)。 一方、ピボット値計算の増加量は各段階では線形となる(元の探索対象の要素数の20%の要素に対する再帰と、線形時間の和)。よって、各段階で問題の要素数は元の要素数の90%(20%+70%)という一定の割合で削減されるので、全体としての計算量は、要素数に対して線形である(線形性の厳密な証明は後述)。
前述のように、中央値の中央値はクイックセレクトのピボット値選択で用いられる。クイックセレクトを擬似コードで書くと以下のようになる。
// 配列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が全体の配列のおおよその中央値となる。 具体的には以下の手順で計算できる[2]。
// 配列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要素以下)の中央値を計算する(例えば挿入ソートなどを使う)[2]。
このように、PivotはSelectを呼び出しており相互再帰となっている。
中央値の中央値をピボット値として採用すると、ピボット値は以下の様な特性を持つ。
個の小配列に分割した時、その小配列のうち半数(個)の小配列では、各小配列の中央値がピボット値(中央値の中央値)以下である。また、各小配列の中には、必ず各中央値以下である要素が3個存在する。よって、その個の各小配列には、ピボット値以下の要素が少なくとも3個以上存在するはずなので、全体としては、個の要素がピボット値以下である。 同様に、もう半数の小配列には、ピボット値以上の要素が少なくとも3個以上存在するはずなので、全体としては、個の要素がピボット値以上である。
よって、そのピボット値を使用して配列を2分割をした時、その分割点は少なくとも上位30%から70%の間に存在することになるので、次の探索対象となる配列の要素数は、必ず元の配列の要素数の一定の割合(最悪でも3割、最善だと7割)に減少させることができる。
例として、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割の)値は、必ずピボット値以下である。また同様に、右下にある値は必ずピボット値以上であることが分かる。
中央値の計算は再帰呼び出しとなっているが、最悪の場合でも線形である。なぜなら、をn個の配列に中央値の中央値を適用したクイックセレクトを適用した時の処理時間とすると、
だからである。ここで
この式は簡単に解けて、最終的には以下のように線形時間であることを示すことができる。
先述の通り、本項で説明した中央値の中央値アルゴリズムでは、配列全体を5要素ずつの小配列に分割した。5要素ずつに分割した理由については以下のように説明できる。
おおよその中央値選択アルゴリズムは、クイックソートのピボット値選択にも使用でき、最悪計算量をにすることもできる。しかし、典型的には、この方法より、乱数によるピボット値選択の方が良い性能を示し(そちらの方が、選択の平均計算量が線形で、並べ替えの平均計算量が対数線形となるので)、ピボット値計算の計算量増加を避けることもできる。
中央値の中央値は、イントロセレクト(英語: introselect)の中でも使用される。イントロセレクトでは、最初はクイックセレクトで計算することで平均計算時間を改善し、もし処理に時間が掛かりそうな場合は中央値の中央値に切り替えることで最悪計算時間も線形に抑えることができる。