|
===================================== 〔語彙分解〕的な部分一致の検索結果は以下の通りです。 ・ 選 ： [せん] 【名詞】 1. (1) selection 2. choice 3. election 4. (2) compilation 5. editing ・ 選択 ： [せんたく] 1. (n,vs) selection 2. choice
選択アルゴリズム（）とは、数列から ''k'' 番目に小さい（あるいは ''k'' 番目に大きい）数を探すアルゴリズムである。最小値、最大値、中央値を探すアルゴリズムは選択アルゴリズムの特殊なものと言える。これらを「順序統計量」とも呼ぶ。比較的単純な最小値、最大値、''k'' 番目に小さい値を求めるアルゴリズムとしては、平均で線形時間のものが知られている。''k'' 番目に小さい値や一度に複数の順序統計量を最悪でも線形時間で探すことも可能である。選択は最近傍探索問題や最短経路問題のようなもっと複雑な問題の部分問題である。 == ソートを伴う選択 == 単純でよく使われるアルゴリズムは、数列にソートを施してから ''k'' 番目の要素を抜き出す方法である。これはある問題から別の問題への還元の例である。これはひとつの数列からいくつもの選択を行いたい場合に便利であり、最初の1回だけソートをすれば、ソート済みの数列からの選択は非常に簡単になる。選択を1回しかしない場合や選択のたびに数列の内容が大幅に変更される場合、この方法は高くつき、一般に最低でも O(''n'' log ''n'') の時間を要する。ここで ''n'' はリストの長さである。 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「選択アルゴリズム」の詳細全文を読む スポンサード リンク
|