選択アルゴリズム

ベースラインアルゴリズムとして、${\displaystyle k}$値の集合の中から最小値を求めるには、次の2つの手順を実行します。

• コレクションを並べ替える
• ソートアルゴリズムの出力が配列である場合、その配列を取得します。${\displaystyle k}$番目の要素。そうでない場合は、ソートされたシーケンスをスキャンして、${\displaystyle k}$th要素。

この方法の所要時間はソートステップによって支配され、${\displaystyle \Theta (n\log n)}$比較ソートを使用した場合の時間。^{[ 2 ] [ 3 ]}整数ソートアルゴリズムを使用する場合でも、これらは一般的に、特殊な選択アルゴリズムを使用した場合に達成できる線形時間よりも遅くなります。それでも、このアプローチの単純さは魅力的であり、特にランタイムライブラリの一部として高度に最適化されたソートルーチンが提供されているが、選択アルゴリズムが提供されていない場合に有効です。中程度のサイズの入力の場合、ソートは実行時間の定数係数が小さいため、非ランダム選択アルゴリズムよりも高速になる可能性があります。^{[ 4 ]}この方法は、コレクションのソート済みバージョンも生成し、これは他の後続の計算、特に他の選択肢による選択に役立つ可能性があります。${\displaystyle k}$[ ^{3 ]​}

選択ソートのように一度に1つの項目を生成するソートアルゴリズムの場合、スキャンはソートと同時に実行でき、${\displaystyle k}$番目の要素が見つかりました。シングルエリミネーショントーナメントにおける慰めブラケットの設計例の1つとして、最終的に優勝したチームに敗れたチームが2位を決定するための別のミニトーナメントを行うというものがありますが、これはこの方法の一例と見なすことができます。^{[ 5 ]}この最適化をヒープソートに適用すると、ヒープセレクトアルゴリズムが生成され、${\displaystyle k}$時間における最小値${\displaystyle O(n+k\log n)}$[ ^{6 ]}これは^、${\displaystyle k}$に比べて小さい${\displaystyle n}$しかし、${\displaystyle O(n\log n)}$より大きな値の場合${\displaystyle k}$例えば、選択肢${\displaystyle k=n/2}$中央値を求めるために使用されます。

選択方法の多くは、入力から特別な「ピボット」要素を選択し、この要素との比較を使用して残りの要素を分割することに基づいています。${\displaystyle n-1}$入力値を2つのサブセットに分割します。${\displaystyle L}$ピボットより小さい要素とセット${\displaystyle R}$ピボットより大きい要素。アルゴリズムは、${\displaystyle k}$比較に基づいて、の最小値を見つける。${\displaystyle k}$これらのセットのサイズで。特に、${\displaystyle k\leq |L|}$、​${\displaystyle k}$最小値は${\displaystyle L}$、そして同じ選択アルゴリズムを に適用することで再帰的に見つけることができます。${\displaystyle L}$。もし${\displaystyle k=|L|+1}$すると、${\displaystyle k}$最小の値はピボットであり、すぐに返されます。残りのケースでは、${\displaystyle k}$最小値は${\displaystyle R}$より具体的には、位置にある要素です${\displaystyle k-|L|-1}$の${\displaystyle R}$。これは、選択アルゴリズムを再帰的に適用し、この位置の値を探すことによって見つけることができます。${\displaystyle R}$[ ^{7 ]​}

関連するピボットベースのクイックソートアルゴリズムと同様に、入力の分割は${\displaystyle L}$そして${\displaystyle R}$これらのセット用に新しいコレクションを作成するか、指定されたリストまたは配列データ型をその場で分割する方法によって実行できます。詳細は、入力コレクションの表現方法によって異なります。^{[ 8 ]}ピボットを他のすべての値と比較する時間は${\displaystyle O(n)}$^{[ 7 ]}しかし、ピボット法はピボットの選択方法が異なり、それが各再帰呼び出しにおける部分問題の大きさに影響します。これらの方法の効率は、ピボットの選択に大きく依存します。ピボットの選択が不適切な場合、この方法の実行時間は、${\displaystyle O(n^{2})}$[ ^{4 ]​}

• ピボットが入力の中央値に正確に位置していた場合、各再帰呼び出しは前の呼び出しの最大半分の値を持ち、合計回数は等比数列で加算され、${\displaystyle O(n)}$しかし、中央値を求めること自体が、元の入力全体に対する選択問題である。選択アルゴリズムを再帰的に呼び出して中央値を求めようとすると、問題のサイズが呼び出しごとに減少しないため、無限再帰につながる。^{[ 7 ]}
• Quickselect は入力値からピボットを均一にランダムに選択します。これは、プルーニングと検索アルゴリズム^{[ 9 ]} 、クイックソートの変種であり、同じピボット戦略を持ちますが、クイックソートが 2 つのサブコレクションをソートするために 2 つの再帰呼び出しを行うのとは異なります。${\displaystyle L}$そして${\displaystyle R}$quickselect は、この 2 つの呼び出しのうち 1 つだけを実行します。予想される時間は${\displaystyle O(n)}$[ ^{2 ] [ 7 ] [ 9 ]任意の}定数に対して${\displaystyle C}$比較回数が超える確率${\displaystyle Cn}$は、${\displaystyle C}$[ ^{10 ]​}
• クイックセレクトの変種であるフロイド・リベストアルゴリズムは、サブセットをランダムにサンプリングすることによってピボットを選択します。${\displaystyle r}$データ値、サンプルサイズがいくつか${\displaystyle r}$そして、その位置の少し上と下の2つの要素を再帰的に選択します。${\displaystyle rk/n}$サンプルのうち、ピボットとして使用するもの。この選択では、${\displaystyle k}$は 2 つのピボットの間に挟まれているため、ピボット後には、再帰呼び出しのためにピボット間のデータ値のごく少数だけが残ります。この方法では、期待される比較回数が次のようになります。${\displaystyle n+\min(k,nk)+o(n)}$^{[ 11 ]}フロイドとリヴェストは、彼らの最初の研究で、${\displaystyle o(n)}$期間は、${\displaystyle O({\sqrt {n}})}$再帰的サンプリング方式によって、彼らの分析の正当性には疑問が呈されている。^{[ 12 ] [ 13 ]}代わりに、より厳密な分析により、彼らのアルゴリズムのバージョンが${\displaystyle O({\sqrt {n\log n}})}$この項については、次のとおりです。^{[ 14 ]}クイックセレクトとフロイド・リベストアルゴリズムの通常の解析では、真の乱数発生器の使用が前提とされていますが、対数的に多くの真の乱数ビットのみでシードされた擬似乱数発生器を使用するフロイド・リベストアルゴリズムのバージョンは、高い確率で線形時間で実行できることが証明されています。^{[ 15 ]}

• 中央値の中央値法は、入力を5つの要素のセットに分割し、別の非再帰的な方法を使用して、各セットの中央値をセットごとに定数時間で求めます。その後、再帰的に自身を呼び出して、これらの中央値を求めます。${\displaystyle n/5}$中央値。結果として得られた中央値の中央値をピボットとして使用すると、次のパーティションが生成されます。${\displaystyle \max(|L|,|R|)\leq 7n/10}$したがって、問題は${\displaystyle n}$要素は、2 つの再帰問題に還元されます。${\displaystyle n/5}$要素（ピボットを見つけるため）と最大${\displaystyle 7n/10}$要素（ピボット使用後）。これら 2 つの再帰的部分問題の合計サイズは最大で${\displaystyle 9n/10}$合計時間を等比数列として分析し、${\displaystyle O(n)}$クイックセレクトとは異なり、このアルゴリズムはランダム化ではなく決定論的です。^{[ 2 ] [ 4 ] [ 5 ]}これは、知られている最初の線形時間決定論的選択アルゴリズムであり、^{[ 5 ]} 2つの等しい部分問題に分割しない分割統治法の例として、学部生のアルゴリズムの授業でよく教えられています。^{[ 2 ] [ 4 ] [ 9 ] [ 16 ]}しかし、その高い定数係数は${\displaystyle O(n)}$時間制限があるため、実際にはクイックセレクトよりも遅く、^{[ 3 ] [ 9 ]}中程度のサイズの入力に対してはソートよりも遅くなります。^{[ 4 ]}
• introselectのようなハイブリッドアルゴリズムは、quickselectの実用的なパフォーマンスを実現し、最悪ケースを保証する中央値の中央値へのフォールバックを可能にするために使用できます。${\displaystyle O(n)}$時間。^{[ 17 ]}

既知の最小比較回数を持つ決定論的選択アルゴリズム、値${\displaystyle k}$遠く離れた${\displaystyle 1}$または${\displaystyle n}$これらは、 1976年にアーノルド・シェーンハーゲ、マイク・パターソン、ニック・ピペンジャーによって導入されたファクトリーの概念に基づいています。^{[ 18 ]}これらは、入力値の小さなサブセットに対して、比較を使用してより小さな部分順序を組み合わせることにより、特定の指定されたタイプの部分順序を構築する方法です。非常に単純な例として、あるタイプのファクトリーは、単一要素の部分順序のシーケンスを入力として受け取り、これらの順序の要素のペアを比較し、2要素の完全順序セットのシーケンスを出力として生成できます。このファクトリーへの入力として使用される要素は、まだ何も比較されていない入力値、または他のファクトリーによって生成された「無駄な」値のいずれかです。ファクトリーベースのアルゴリズムの目標は、さまざまなファクトリーを組み合わせ、一部のファクトリーの出力を他のファクトリーの入力として使用して、最終的に1つの要素（${\displaystyle k}$（最小）は、いくつかのものよりも大きい${\displaystyle k-1}$他の要素よりも小さく、${\displaystyle nk}$その他。これらの工場を慎重に設計すると、中央値探索に適用した場合、最大で${\displaystyle 2.942n}$比較。その他の値については${\displaystyle k}$比較回数は^少なくなる。[ ^{19 ]}

選択のための並列アルゴリズムは、1975年にレスリー・ヴァリアントがこれらのアルゴリズムを分析するための並列比較ツリーモデルを導入し、このモデルでは線形数の比較を使用した選択には${\displaystyle \Omega (\log \log n)}$最小値や最大値を選択する場合でも、並列ステップが用いられます。^{[ 20 ]}研究者らは後に、選択のための並列アルゴリズムを発見しました。${\displaystyle O(\log \log n)}$この境界に一致するステップ数。^{[ 21 ] [ 22 ]}ランダム化並列比較ツリーモデルでは、選択を制限されたステップ数と線形回数の比較で実行できます。^{[ 23 ]}排他的読み出し排他的書き込みメモリアクセスを備えた、より現実的な並列RAMコンピューティングモデルでは、選択は時間で実行できます。${\displaystyle O(\log n)}$と${\displaystyle O(n/\log n)}$プロセッサ数で、時間とプロセッサ数の両方で最適です。^{[ 24 ]}同時メモリアクセスにより、一般的にわずかに高速な並列処理が可能になり、^{[ 25 ]}${\displaystyle \log n}$時間制限内の項は、${\displaystyle \log k}$[ ^{26 ]​}

データが既にデータ構造に整理されている場合、値の数に対して非線形な時間で選択を実行できる可能性があります。この簡単な例として、既に配列にソートされているデータの場合、${\displaystyle k}$番目の要素は、定数時間で単一の配列ルックアップによって実行できます。^{[ 27 ]}サイズの2次元配列に整理された値の場合${\displaystyle m\times n}$行と列がソートされている場合、選択は時間内に実行できます。${\displaystyle O{\bigl (}m\log(2n/m){\bigr )}}$または、より速く${\displaystyle k}$配列の次元に比べて小さい。^{[ 27 ] [ 28 ]}コレクションの場合${\displaystyle m}$1次元のソート済み配列で、${\displaystyle k_{i}}$選択したアイテムよりも少ないアイテム${\displaystyle i}$th配列、時間は${\textstyle O{\bigl (}m+\sum _{i=1}^{m}\log(k_{i}+1){\bigr )}}$[ ^{28 ]​}

バイナリヒープ内のデータからの選択には時間がかかります${\displaystyle O(k)}$これはサイズとは無関係です${\displaystyle n}$山積みの、そしてより速い${\displaystyle O(k\log n)}$最良優先探索から得られる時間制限。^{[ 28 ] [ 29 ]}この同じ方法は、ヒープ順序付けされたツリー（各ノードが1つの値を格納し、各非ルートノードの親が子よりも小さい値を持つツリー）として構成されたデータに、より一般的に適用できます。ヒープでの選択を実行するこの方法は、暗黙的に定義されたヒープ順序付けされたツリーの形式で解の状態空間を定義し、この選択アルゴリズムをこのツリーに適用することにより、重み付きグラフでk個の最短経路を見つけるなど、組み合わせ最適化問題の複数の解をリストアップする問題に適用されています。^{[ 30 ]}反対に、線形時間の選択アルゴリズムは、ヒープに関連する優先度キューデータ構造のサブルーチンとして使用され、その抽出時間を改善しています。${\displaystyle k}$アイテムから${\displaystyle O(\log n)}$に${\displaystyle O(\log ^{*}n+\log k)}$;ここ${\displaystyle \log ^{*}n}$は反復対数である。^{[ 31 ]}

動的な挿入と削除が行われるデータ値のコレクションの場合、順序統計ツリーは自己平衡二分探索ツリー構造をツリーノードごとに一定量の追加情報で拡張し、挿入、削除、選択クエリで要求される値を可能にします。${\displaystyle k}$現在のセットの 番目の要素はすべて実行されます${\displaystyle O(\log n)}$演算あたりの時間。^{[ 2 ]}計算の比較モデルを超えて、バイナリ算術演算が可能な小さな整数値の場合、演算あたりの時間が速くなる可能性があります。 ^{[ 32 ]}メモリが両方とも準線形であるストリーミングアルゴリズムでは不可能です。${\displaystyle n}$そして${\displaystyle k}$動的データに対して選択クエリを正確に解決するには、カウント-ミニット スケッチを使用できます。これは、要素の順序付けにおける位置 (要素に追加された場合) が、範囲内にある値を見つけることで、選択クエリを近似的に解決します。${\displaystyle \varepsilon n}$のステップ${\displaystyle k}$サイズが対数係数の範囲内にあるスケッチの場合${\displaystyle 1/\varepsilon }$[ ^{33 ]​}