k個の最小・最大要素の選択

ウィキペディア小見出し辞書

k個の最小・最大要素の選択

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/03/21 14:22 UTC 版)

「選択アルゴリズム」の記事における「k個の最小・最大要素の選択」の解説

別の基本的な選択問題として、k 個の最大要素（または最小要素）を選択する問題がある。例えば、売り上げトップ100社のようなリストを得たい場合に相当する。単純だが効率的でない手法はいくつか存在する。上述の選択アルゴリズムで1個ずつ要素を選択していけば O(kn) の時間で k 個の要素を選択できる。これは、k 番目までの選択ソートを実施するのと同じである。もし log n が k よりずっと小さいなら、リスト全体をソートしてしまう方が効率的である。 別の単純な方法は、ヒープや平衡2分探索木のような順序を維持できるデータ構造にデータを格納することである。データ構造に k 個以上の要素があるなら、いらない要素を削除する（小さい方の要素群が必要なら最大の要素を削除する）。これには O(log k) の時間がかかる。要素の挿入にも同じ時間がかかり、全体として O(nlog k) の時間を要する。 これらよりも効率的な手法として、マージソートやクイックソートに基づいた部分ソートアルゴリズムがある。クイックソート方式の方が簡単で、選択したい k 個の要素群（の一部）を含まないパーティションをソートしない。ピボット値が k 番目かそれ以降なら、左側のパーティションだけに再帰を施せばよい。 function quicksortFirstK(a, left, right, k) if right > left select a pivot value a[pivotIndex] pivotNewIndex := partition(a, left, right, pivotIndex) quicksortFirstK(a, left, pivotNewIndex-1, k) if pivotNewIndex < k quicksortFirstK(a, pivotNewIndex+1, right, k) このアルゴリズムにかかる時間は O(n + klogk) であり、実際非常に効率が良い。特に、n に比較して k が十分小さいなら、選択ソートを使うようにすれば効率が向上する。 選択する k 個の要素がソートされている必要がないなら、もっと効率化することができる。その場合、k 番目の要素を含むパーティションだけに再帰を施せばよく、その前後はソートする必要がない。 function findFirstK(a, left, right, k) if right> left select a pivot value a[pivotIndex] pivotNewIndex := partition(a, left, right, pivotIndex) if pivotNewIndex > k // new condition findFirstK(a, left, pivotNewIndex-1, k) if pivotNewIndex < k findFirstK(a, pivotNewIndex+1, right, k) このアルゴリズムに掛かる時間は O(n) であり、アルゴリズムとしては最善の部類になる。 別の方法はトーナメントアルゴリズムである。まず、隣接するペアで試合（比較）を行い、勝者を次の試合に進めていき、最終的に優勝を決定する。このときトーナメント木を生成する。この時点で 2位の要素は優勝者に直接負けた要素であるはずなので、木構造を辿っていけば O(log n) の時間で探すことができる。このとき新たなトーナメント木を生成する。3位の要素は 2位の要素に直接負けた要素のはずなので、2つのトーナメント木からそれを探し出す。このようにして k 個の要素を探し出すまで処理を行う。このアルゴリズムは O(n + k log n) の時間がかかる。 k = 2 の場合、O(n + log n) の時間で選択ができる。