非線形選択アルゴリズム
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/03/21 14:22 UTC 版)
「選択アルゴリズム」の記事における「非線形選択アルゴリズム」の解説
最大値/最小値アルゴリズムをそのまま使って、k 番目に小さい値（または k番目に大きい値）を求めるアルゴリズムは簡単に作成できるが、効率は不十分である。必要な時間は O(kn) で、k が小さければ小さいほど効率が良い。このアルゴリズムでは、単に最もそれらしい値を見つけてそれをリストの先頭に移動させ、必要な k番目に達するまでそれを繰り返す。それはちょうど不完全な選択ソートと同じである。以下に小さい値を探すアルゴリズムを示す。 function select(a[1..n], k) for i from 1 to k minIndex = i minValue = a[i] for j from i+1 to n if a[j] < minValue minIndex = j minValue = a[j] swap a[i] and a[minIndex] return a[k] この方式には以下の利点がある。 j 番目に小さい値がわかっている状態では、k 番目に小さい値を求めるのにかかる時間は O(j + (k-j)2) であり、k ≤ j なら O(k) となる。 線形リストデータ構造を使うことができる。一方、後述するパーティションベースの手法ではランダムアクセスを必要とする。
※この「非線形選択アルゴリズム」の解説は、「選択アルゴリズム」の解説の一部です。
「非線形選択アルゴリズム」を含む「選択アルゴリズム」の記事については、「選択アルゴリズム」の概要を参照ください。
ウィキペディア小見出し辞書の「非線形選択アルゴリズム」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。
お問い合わせ。
- 非線形選択アルゴリズムのページへのリンク
