ソートを伴う選択
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/03/21 14:22 UTC 版)
「選択アルゴリズム」の記事における「ソートを伴う選択」の解説
単純でよく使われるアルゴリズムは、数列にソートを施してから k 番目の要素を抜き出す方法である。これはある問題から別の問題への還元の例である。これはひとつの数列からいくつもの選択を行いたい場合に便利であり、最初の1回だけソートをすれば、ソート済みの数列からの選択は非常に簡単になる。選択を1回しかしない場合や選択のたびに数列の内容が大幅に変更される場合、この方法は高くつき、一般に最低でも O(n log n) の時間を要する。ここで n はリストの長さである。
※この「ソートを伴う選択」の解説は、「選択アルゴリズム」の解説の一部です。
「ソートを伴う選択」を含む「選択アルゴリズム」の記事については、「選択アルゴリズム」の概要を参照ください。
ウィキペディア小見出し辞書の「ソートを伴う選択」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。
お問い合わせ。
- ソートを伴う選択のページへのリンク
