中央値の中央値

中央値の中央値
	中央値の中央値
クラス	選択アルゴリズム
データ構造	配列
最悪のパフォーマンス	O ( n ) {\displaystyle O(n)}
最高のパフォーマンス	O ( n ) {\displaystyle O(n)}
最悪の場合の空間複雑度	O ( log ⁡ n ) {\displaystyle O(\log n)} 補助
最適	はい

Fast approximate median algorithm

コンピュータサイエンスにおいて、中央値の中央値は近似中央値選択アルゴリズムであり、正確な選択アルゴリズム（最も一般的にはクイック選択）に適したピボットを提供するために頻繁に使用されます。中央値の中央値は線形時間で近似中央値を見つけます。この近似中央値を改良したピボットとして使用すると、クイック選択の最悪ケースの複雑度は2 次から線形に減少します。これは、あらゆる選択アルゴリズムの最悪ケースの複雑度が漸近的に最適であることにもなります。つまり、中央値の中央値は近似中央値選択アルゴリズムであり、適切なピボット要素を生成することで、漸近的に最適で正確な一般選択アルゴリズム（特に最悪ケースの複雑度の意味で）の構築に役立ちます。

中央値の中央値はクイックソートのピボット戦略としても使用でき、最悪ケースの複雑度で最適なアルゴリズムを生成します。^[^{引用が必要}^] 中央値の中央値アルゴリズムは、各ステップで少なくとも 30% の要素を破棄して適切なピボット要素を再帰的に選択することにより、最悪ケースの実行時間が O(n) になることを保証します。^[1]このアプローチは漸近的な最悪ケースの複雑度をかなり最適化しますが、実際には通常、ピボットを計算するオーバーヘッドなしで、選択の平均複雑度とソートの平均複雑度に対してランダムなピボットを選択することで、この方法よりも優れたパフォーマンスを発揮します。 $O(n\log n)$ $O(n)$ $O(n\log n)$

同様に、ハイブリッド・イントロセレクト・アルゴリズムでは、k番目に小さい値が見つかるまで、各反復処理においてピボット選択のフォールバックとして、中央値の中央値が用いられます。これにより、平均ケースの線形パフォーマンスに加えて、最悪ケースの線形パフォーマンスも保証されます。イントロセレクトは、良好な平均パフォーマンスを得るためにクイックセレクト（デフォルトのランダムピボットを使用）から開始し、その後、進行が遅すぎる場合は、中央値の中央値から得られたピボットを使用した修正クイックセレクトにフォールバックします。漸近的には類似しているものの、このようなハイブリッド・アルゴリズムは、任意の有限長において、定数倍（平均ケースと最悪ケースの両方）まで、単純なイントロセレクトよりも複雑性が低くなります。

このアルゴリズムはBlumら（1973）で発表されたため、著者（Blum 、Floyd、Pratt、Rivest、Tarjan）の姓にちなんでBFPRTと呼ばれることもあります。 [ 2 ]元の論文では、このアルゴリズム^はPICKと呼ばれ、クイック選択はFINDと呼ばれていました。

モチベーション

クイック選択は平均すると線形時間ですが、ピボットの選択が適切でない場合は二次の時間が必要になることがあります。これは、クイック選択が分割統治アルゴリズムであるためです。各ステップでは、残りの検索セットのサイズに応じて時間がかかります。検索セットのサイズが指数関数的に急速に減少する場合 (固定の割合で)、等比級数に単一ステップの係数を掛けたものになり、全体の時間は線形になります。ただし、検索セットのサイズが線形などゆっくりと減少する場合 (固定数の要素ずつ、最悪の場合でも毎回 1 要素ずつしか減らない場合)、線形ステップの線形和によって全体の時間は二次の時間になります (正式には、三角数は二次で増加します)。たとえば、すでにソートされたデータに最大要素のクイック選択を適用し、毎回最初の要素をピボットとして使用するなど、各ステップで最小の要素をピボットする場合に最悪のケースが発生します。 $O(n)$ $O(n)$

代わりに「良い」ピボットを一貫して選択すれば、このような事態は回避され、最悪の場合でも常に線形パフォーマンスが得られます。「良い」ピボットとは、一定の割合の要素がその上下に存在し、その場合、探索セットは各ステップで少なくとも一定の割合で減少し、したがって指数関数的に速く減少し、全体の時間は線形のままである、と確立できるピボットです。中央値は良いピボットであり、ソートに最適であり、選択にも全体的に最適な選択肢です。中央値は各ステップで探索セットを半分ずつ減らします。したがって、中央値を線形時間で計算できれば、各ステップにかかる時間は線形時間のみ増加し、アルゴリズム全体の複雑さは線形のままです。

中央値の中央値アルゴリズムは、近似中央値、つまり30パーセンタイルと70パーセンタイルの間（中央の4デシル）にあることが保証された点を計算します。これにより、探索セットは少なくとも30%減少します。問題は元のサイズの70%に縮小され、これは一定の割合で小さくなります。同じアルゴリズムを、1つまたは2つの要素だけが残るまで再帰的に適用すると、コストは次のようになります。 ${\frac {n}{1-0.7}}\approx 3.33{n}$

アルゴリズム

前述のように、中央値の中央値はクイック選択アルゴリズムのピボット選択戦略として使用され、疑似コードでは次のようになります。

関数median(リスト)
   長さ(リスト)が奇数の場合
       値 := nthSmallest(リスト, 長さ(リスト) / 2)
   それ以外
       値 := 0.5 * (nthSmallest(リスト, 長さ(リスト) / 2 - 1) +
                       nthSmallest(リスト, 長さ(リスト) / 2))
   戻り値

関数nthSmallest(リスト, n)
    インデックス := select(リスト, 1, 長さ(リスト), n)
    リストを返す[インデックス]

left実装する際には、、、rightの扱いに注意してくださいn。以下の擬似コードではleft、、、rightリストが1から始まる番号付けを使用し、がselect最初に1を引数としてleft、リストの長さを引数として呼び出されることを前提としていますright。これは、n番目に小さい数の実際の値ではなく、リストを並べ替えた後のn番目に小さい数のインデックスを返すことに注意してください。

関数select(list, left, right, n)
    ループして
        left = rightの場合は
            leftを返す
        pivotIndex := pivot(リスト, 左, 右)
        pivotIndex := partition(リスト, 左, 右, pivotIndex, n)
        n = pivotIndexの場合は
            n
        を返し、そうでない場合はn < pivotIndexの場合は
            右 := ピボットインデックス - 1
        それ以外
            左 := ピボットインデックス + 1

サブルーチンpivotは、実際の中央値アルゴリズムです。入力（長さ $n$ のリスト）を最大5要素のグループに分割し、各グループの中央値を何らかのサブルーチンを用いて計算します。そして、前のステップで得られた中央値の真の中央値を再帰的に計算します。^[3]pivot はselectを呼び出していることに注意してください。これは相互再帰の例です。 ${\frac {n}{5}}$

function pivot(list, left, right)
     // 要素が 5 以下の場合は中央値のみを取得します。right
     − left < 5の場合は、
         partition5(list, left, right)
    を返します。// それ以外の場合は、5 要素のサブグループの中央値を、
     iについて左から右へ5
        ずつ最初の n/5 の位置に移動します。// i番目の5 要素のサブグループの中央値の位置を取得します。
        サブ右 := i + 4
        subRight > rightの場合
            サブ右 := 右
        median5 := partition5(リスト, i, サブ右)
        list[median5]とlist[left + floor((i − left) / 5)]を交換する

    // n/5 の 5 つの中央値の中央値を計算する
    中央 := 床((右 − 左) / 10) + 左 + 1
    select(リスト、左、左+フロア((右-左)/5)、中央)
を返す

パーティションヘルパー関数

パーティションと呼ばれるサブルーチンは、線形時間でリスト（インデックスから）を3つの部分にグループ化します。つまり、特定の要素より小さい部分、特定の要素と等しい部分、特定の要素より大きい部分です（3分割）。この3つの部分にグループ化することで、多くの要素またはすべての要素が一致する場合でも、中央値の中央値を求めることで線形実行時間を維持できます。以下は、要素に関する分割を実行する擬似コードです。 leftrightlist[pivotIndex]

関数partition(リスト, 左, 右, ピボットインデックス, n)
    ピボット値 := リスト[ピボットインデックス]
    list[pivotIndex]とlist[right]を入れ替える  // ピボットを末尾に移動する
    ストアインデックス := 左
    // ピボットより小さいすべての要素をピボットの左側に移動する
    for i for left from right − 1 do 
        if list[i] < pivotValue then
            list[storeIndex]とlist[i]を入れ替える
            ストアインデックスを増分する
    // すべての要素をピボットと同じ大きさに
    小さい要素の直後に移動します
    ストアインデックスEq := ストアインデックス
    i をstoreIndexから右へ− 1実行し
        、list[i] = pivotValueの場合、
            list[storeIndexEq]とlist[i]を入れ替える
            ストアインデックスを増分する
    list[right] と list[storeIndexEq] を入れ替える  // ピボットを最終的な場所に移動する
    // 目的の位置 n を考慮してピボットの位置を返す
    if n < storeIndex then 
        return storeIndex   // n は小さい要素のグループ内にある
    if n ≤ storeIndexEq then 
        return n   // n はピボットと等しいグループ内にある
    return storeIndexEq // n は大きい要素のグループ内にある

パーティション5サブルーチンは最大5つの要素のグループの中央値を選択します。これを実装する簡単な方法は、以下に示すように挿入ソートです。^[3]また、決定木として実装することもできます。

関数partition5(リスト, 左, 右)
    i := 左 + 1
    i ≤正しい間
        j := i
        j > 左かつlist[j−1] > list[j]であるとき
            リスト[j−1]とリスト[j]を交換する
            j := j − 1
        i := i + 1

    左 + (右 - 左) / 2
を返す

ピボットの特性

グループのうち、半数のグループでは中央値がピボットより小さくなります (中央値の中央値)。また、残りの半数のグループでは中央値がピボットより大きくなります。中央値がピボットより小さい各グループには、それぞれの中央値より小さい要素が 2 つあり、それぞれの中央値はピボットより小さくなります。したがって、各グループにはピボットより小さい要素が少なくとも 3 つあります。同様に、中央値がピボットより大きい各グループには、それぞれの中央値より大きい要素が 2 つあり、それぞれの中央値はピボットより大きくなります。したがって、各グループにはピボットより大きい要素が少なくとも 3 つあります。したがって、ピボットは要素より小さく、別の要素より大きくなります。このように、選択された中央値は、順序付けられた要素を 30%/70% と 70%/30% の間のどこかに分割し、アルゴリズムの最悪ケースの線形動作を保証します。図を視覚化します。 ${\frac {n}{5}}$ $\left({\frac {1}{2}}\times {\frac {n}{5}}={\frac {n}{10}}\right)$ $\left({\text{again, }}{\frac {1}{2}}\times {\frac {n}{5}}={\frac {n}{10}}\right)$ ${\frac {n}{10}}$ ${\frac {n}{10}}$ ${\frac {n}{10}}$ ${\frac {n}{10}}$ $3\times {\frac {n}{10}}$ $3\times {\frac {n}{10}}$

0から99までの100個の要素をランダムに抽出した1回の反復
	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

（赤 = 「（2つの可能な値のうちの1つ）中央値の中央値」、灰色 = 「数値 < 赤」、白 = 「数値 > 赤」）

ここでは、分かりやすくするために、5つのタプルを中央値でソートして表示しています。ピボット要素として使用するには中央値のみが必要なので、タプルをソートする必要はありません。

赤の上/左にあるすべての要素 (100 個の要素のうちの 30%) は小さく、赤の下/右にあるすべての要素 (100 個の要素のうちの別の 30%) は大きいことに注意してください。

線形実行時間の証明

中央値を計算する再帰呼び出しは、中央値のリストのサイズがであるのに対し、もう一方の再帰呼び出しはリストの最大70%しか再帰処理しないため、最悪ケースの線形動作を超えません。サイズの配列に対して中央値の中央値クイック選択アルゴリズムを実行するのにかかる時間をとすると、この時間は次のように求められます。 ${\frac {n}{5}}$ $T(n)$ $n$

T(n)\leq T(n/5)+T(n\cdot 7/10)+c\cdot n,

どこ

この部分は、中央値の真の中央値を見つけるためのもので、（独立した）クイック選択を実行して中央値を見つけます（中央値を見つけることは、 k最小の要素を選択する特別なケースにすぎないため） $T\left({\frac {n}{5}}\right)$ ${\frac {n}{5}}$
この用語は、2 つの側面を作成するための分割作業を表します。そのうちの 1 つは、クイック選択によって再帰されます (各要素を一定回数訪問して n/5 のグループに分け、各中央値を時間内に取得します)。 $O(n)$ $c\cdot n$ $O(1)$
この部分は実際のクイック選択再帰用です（最悪の場合、k番目の要素が最大サイズのより大きなパーティション内にある場合） $T\left({\frac {7n}{10}}\right)$ ${\frac {7n}{10}}$

誘導により：

T(n)\leq 10\cdot c\cdot n\in O(n).

分析

重要なステップは、問題を、元のリストよりも合計長が短い2つのリストを選択し、その削減ステップに線形係数を加えるという形に縮小することです。これにより、全体の実行時間が線形であることが簡単な帰納法で示されます。

5 つの要素のグループを具体的に選択した理由は、次のとおりです。まず、奇数リストの中央値を計算する方が高速で簡単です。偶数リストを使用することもできますが、中央の 2 つの要素の平均を取る必要があり、中央の 1 つの要素を選択するだけの場合よりも遅くなります。次に、中央値の中央値が機能する最小の奇数は 5 です。3 つの要素だけのグループの場合、検索対象となる中央値のリストは長さになり、これは要素の 1/2 × 2/3 = 1/3 より大きく、要素の 1/2 × 2/3 = 1/3 より小さいため、再帰的にリストを長さに削減できます。したがって、これはまだ検索対象となる要素を残しており、問題を十分に削減するものではありません。ただし、個々のリストは短くなり、 Akra–Bazzi 法によって結果の複雑さをに制限できますが、線形性は証明されません。 ${\frac {n}{3}}$ ${\frac {2}{3}}n$ $n$ $O(n\log n)$

逆に、= 7、9、またはそれ以上の要素でグループ化することもできます。これは機能します。これにより、中央値のリストのサイズがに削減され、重複する線のサイズが比例して減少するため、上の表の象限が 25% に近づくにつれて、3 n /4 (75%) で漸近線に再帰するリストのサイズが削減されます。これにより、スケーリング係数が漸近的に 10 から 4 に削減されますが、それに応じて分割作業の項が増加します。大きなグループの中央値を見つけるには時間がかかりますが、これは定数係数 ( のみに依存) であるため、 n が大きくなっても全体的なパフォーマンスは変わりません。実際、最悪の場合の比較数を考えると、定数係数はです。 $g$ ${\frac {n}{g}}$ $c$ $g$ ${\frac {2g(g-1)}{g-3}}$

代わりに他の方法でグループ化する場合、つまり、要素リストを 5 つのリストに分割し、それぞれの中央値を計算し、次にこれらの中央値を計算する場合、つまり定数ではなく定数分数でグループ化する場合、問題はそれほど明確には軽減されません。これは、各要素のリストで 5 つの中央値を計算し、最大で長さのリストを再帰する必要があるためです。 3 でグループ化する場合と同様に、個々のリストは短くなりますが、全体の長さは短くなりません (実際には長くなります)。そのため、超線形境界しか証明できません。長さのリストの平方にグループ化することも同様に複雑です。 $n$ ${\frac {n}{5}}$ ${\frac {7}{10}}n$ ${\sqrt {n}}$ ${\sqrt {n}}$

参考文献

^ Cormen、TH、Leiserson、CE、Rivest、RL、および Stein、C. (2009)。アルゴリズム入門 (第 3 版)。 MITプレス。
^ Blum, M. ; Floyd, RW ; Pratt, VR ; Rivest, RL ; Tarjan, RE (1973年8月). 「選択のための時間境界」(PDF) . Journal of Computer and System Sciences . 7 (4): 448– 461. doi : 10.1016/S0022-0000(73)80033-9 .
^ ab コーメン、トーマス H. ;チャールズ・E・ライザーソン;ロナルド・L・リベスト;スタイン、クリフォード(2009) [1990]。アルゴリズム入門(第 3 版)。 MIT プレスとマグロウヒル。 p. 220.ISBN 0-262-03384-4。

外部リンク

「1996年1月30日の講義ノート：決定論的選択」、ICS 161：アルゴリズムの設計と分析、 David Eppstein
「高速決定論的選択」アンドレイ・アレクサンドルスク

[1] Cormen、TH、Leiserson、CE、Rivest、RL、および Stein、C. (2009)。アルゴリズム入門 (第 3 版)。 MITプレス。

[2] Blum, M. ; Floyd, RW ; Pratt, VR ; Rivest, RL ; Tarjan, RE (1973年8月). 「選択のための時間境界」(PDF) . Journal of Computer and System Sciences . 7 (4): 448– 461. doi : 10.1016/S0022-0000(73)80033-9 .

[clrs-3] コーメン、トーマス H. ;チャールズ・E・ライザーソン;ロナルド・L・リベスト;スタイン、クリフォード(2009) [1990]。アルゴリズム入門(第 3 版)。 MIT プレスとマグロウヒル。 p. 220.ISBN 0-262-03384-4。