アルゴリズム (全101問中76問目)
No.76
n個のデータを整列するとき，比較回数が最悪の場合でO(n2)，最良の場合でO(n)となるものはどれか。
出典：平成19年春期 問11
- クイックソート
- 単純選択法
- 単純挿入法
- ヒープソート
分類
テクノロジ系 » アルゴリズムとプログラミング » アルゴリズム
正解
ウ
解説
オーダー記法は、アルゴリズムの計算量が実行時に処理するデータ量によってどのように増加するかやアルゴリズムの実行時間の長さを示します。時間計算量を表すオーダー記法によってアルゴリズムの複雑さがわかり、アルゴリズムの理論的比較することができます。
それぞれの整列法の比較回数は次のようになっています。
したがって最悪の場合で O(n2)、最良で O(n)となるアルゴリズムは「単純挿入法」が適切です。
それぞれの整列法の比較回数は次のようになっています。