線形最大・最小アルゴリズム
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/03/21 14:22 UTC 版)
「選択アルゴリズム」の記事における「線形最大・最小アルゴリズム」の解説
最悪でも線形時間となる最小値・最大値を求めるアルゴリズムは自明である。2つの変数を使い、一方にはそれまでの最大値/最小値のリスト上のインデックスを格納し、もう一方にその値そのものを格納する。リストを順次見ていき、それらしい値を見つけたら変数を更新する。 function minimum(a[1..n]) minIndex := 1 minValue := a[1] for i from 2 to n if a[i] < minValue minIndex := i minValue := a[i] return minValue function maximum(a[1..n]) maxIndex := 1 maxValue := a[1] for i from 2 to n if a[i] > maxValue maxIndex := i maxValue := a[i] return maxValue このアルゴリズムは、全順序集合の有限部分集合 A（例えば、整数、実数、辞書の単語群などの部分集合）について、A に含まれない要素 x があるとき、 max ( A ∪ { x } ) = max ( { max A , x } ) {\displaystyle \operatorname {\max } (A\cup \{x\})=\operatorname {\max } (\{\operatorname {\max } A,x\})} が成り立つという定理に基づいている。このとき最小値や最大値が複数個存在する可能性に注意が必要である。上記擬似コードの比較は厳密であるため、このアルゴリズムでは最小のインデックスの最小値を探し出す。厳密でない比較（≤ および ≥）を用いれば、最大のインデックスの最小値を探し出すことになる。 最大値と最小値を同時に求めたい場合、若干の改善方法としてペア単位の比較が考えられる。つまり、奇数番目と偶数番目の要素を比較し、大きい方を最大値と、小さいほうを最小値と比較するのである。別の手法として分割統治法がある。つまり、リストを半分に分け、前半と後半それぞれの最大値・最小値を求め、それらの値から全体の最大値・最小値を求める。
※この「線形最大・最小アルゴリズム」の解説は、「選択アルゴリズム」の解説の一部です。
「線形最大・最小アルゴリズム」を含む「選択アルゴリズム」の記事については、「選択アルゴリズム」の概要を参照ください。
- 線形最大・最小アルゴリズムのページへのリンク
