中央値の中央値

中央値の中央値

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

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

中央値の中央値は、クイックソートのピボット戦略としても使用でき、最悪のケースの複雑度で最適なアルゴリズムを生成します。^[要出典]このアプローチは漸近的な最悪のケースの複雑度をかなり最適化しますが、実際には、ピボットを計算するオーバーヘッドなしで、選択の平均複雑度とソートの平均複雑度に対してランダムなピボットを選択する方が通常、この方法よりも優れています。 ${\displaystyle O(n\log n)}$${\displaystyle O(n)}$${\displaystyle O(n\log n)}$

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

このアルゴリズムは Blum ら (1973) で発表されたため、著者の姓にちなんでBFPRTと呼ばれることもあります。元の論文では、このアルゴリズムはPICKと呼ばれ、クイック選択は "FIND" と呼ばれていました。

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

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

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

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

関数nthSmallest(リスト, n)
    index := select(list, 1, length of list, n) // リストがゼロベースの番号付けの場合は select(list, 0, length of list - 1, n - 1) を使用します
    。return list[index]

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

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

サブルーチンpivot は、実際の中央値のアルゴリズムです。入力 (長さnのリスト) を最大 5 つの要素のグループに分割し、サブルーチンを使用して各グループの中央値を計算し、前の手順で見つかった中央値の真の中央値を再帰的に計算します。^[1] pivot はselect を呼び出すことに注意してください。これは相互再帰の例です。 ${\displaystyle {\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、subRight)
        リスト[median5]とリスト[left + floor((i − left) / 5)]を交換する

    // n/5 の 5 つの中央値の中央値を計算します
    中央 := 床((右 − 左) / 10) + 左 + 1
    select(リスト、左、左 + floor((右 − 左) / 5)、mid)
を返します。

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

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

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

関数partition5(リスト、左、右)
    i := 左 + 1
    i ≤正しい場合
        j := i
        j > left かつ list[j−1] > list[j]であるとき
            リスト[j−1]とリスト[j]を入れ替える
            j := j − 1
        私 := 私 + 1

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

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

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

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

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

中央値を計算する再帰呼び出しは、中央値のリストのサイズが であるのに対し、他の再帰呼び出しはリストの最大 70% を再帰するため、最悪の場合の線形動作を超えません。 が、サイズ の配列に対して中央値の Quickselect アルゴリズムを実行するのにかかる時間とします。この場合、この時間は次のようになります。 ${\displaystyle {\frac {n}{5}}}$${\displaystyle T(n)}$${\displaystyle n}$

${\displaystyle T(n)\leq T(n/5)+T(n\cdot 7/10)+c\cdot n,}$

どこ

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

誘導により：

${\displaystyle 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 法によって結果の複雑さを に制限できますが、線形性は証明されません。 ${\displaystyle {\frac {n}{3}}}$${\displaystyle {\frac {2}{3}}n}$${\displaystyle n}$${\displaystyle O(n\log n)}$

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

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

• 「1996 年 1 月 30 日の講義ノート: 決定論的選択」、ICS 161: アルゴリズムの設計と分析、 David Eppstein