アルゴリズム(全97問中72問目)

n個のデータを整列するとき,比較回数が最悪の場合でO(n2),最良の場合でO(n)となるものはどれか。

出典:平成19年春期 問11

  • クイックソート
  • 単純選択法
  • 単純挿入法
  • ヒープソート
正解 問題へ
分野:テクノロジ系
中分類:アルゴリズムとプログラミング
小分類:アルゴリズム
解説
オーダー記法は、アルゴリズムの計算量が実行時に処理するデータ量によってどのように増加するかやアルゴリズムの実行時間の長さを示します。時間計算量を表すオーダー記法によってアルゴリズムの複雑さがわかり、アルゴリズムの理論的比較することができます。

それぞれの整列法の比較回数は次のようになっています。
11.gif
したがって最悪の場合で O(n2)、最良で O(n)となるアルゴリズムは「単純挿入法」が適切です。

Pagetop