|
中央値の中央値（ちゅうおうちのちゅうおうち、）とは、に基づく選択アルゴリズムのことである。k番目に大きい要素を選択するための最悪計算時間が線形になることが特徴である。 このアルゴリズムでは、最初におおよその中央値を線形時間で探索し、その値をクイックセレクトでのピボット値とする。つまり、（漸近的な）おおよその中央値選択アルゴリズムを使って、（漸近的な）一般値選択アルゴリズムを構築したものである。 このアルゴリズムは、マヌエル・ブラムらによって開発されたもので、著者の名字の頭文字を取ってBFPRTとも呼ばれる。この原著では中央値の中央値アルゴリズムをPICKと呼び、クイックセレクトをFINDと呼んでいた。 == 概要 == クイックセレクトは分割統治法であり、計算の各段階で、残っている探索対象の要素が個の場合にの計算時間を必要とする。そのためクイックセレクト全体の計算量は、 * もし探索対象の要素数を（一定の割合で）指数関数的に減少させられるなら、等比級数と1段の計算量()の積、つまり線形時間となる。 * しかし、要素数の減少がとても遅い（例えば、減少する要素数が一定、最悪の場合1つずつしか減らないような線形減少の）場合、各段の計算量の線形和となり、2次時間となる（三角数は2次となる）。 最悪時間となる場合は、例えば、各段階でピボット値として最小値を選んでしまう時である。これは、既に降順に並び替え済みの配列に対して、最初の要素をピボット値として選択してしまうと実際に起こりうる。 つまり、もし各段階で一貫して「良いピボット値」を選択し続けられるなら、このような最悪の場合を回避することができ、最悪の場合でも線形時間の性能となる。この「良いピボット値」では、全ての要素を一定の割合でより大きい値と小さい値に分割することができ、つまり探索対象の要素数を一定の割合で減らすことができ、ゆえに要素数が指数関数的に減少して、全体的な計算時間は線形のままとなる。 中央値は、そのような「良いピボット値」であり、各段階で探索対象を半分ずつに減らすことができる。ゆえに、もし中央値を線形時間で計算できるなら、各段階では線形時間しか増えないので、全体の計算量は線形時間のままとなる。 中央値の中央値アルゴリズムでは、正確な中央値ではなく、代わりに、30から70パーセンタイルの間（第4十分位数の中間）点であることが保証されたおおよその中央値を使用する。そのため、探索対象の要素数は各段階で一定の割合（最小で30%）で減少する（つまり最大で70%が残る）。 一方、ピボット値計算の増加量は各段階では線形となる（元の探索対象の要素数の20%の要素に対する再帰と、線形時間の和）。よって、各段階で問題の要素数は元の要素数の90%(20%+70%)という一定の割合で削減されるので、全体としての計算量は、要素数に対して線形である（線形性の厳密な証明は後述）。 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「中央値の中央値」の詳細全文を読む スポンサード リンク
|