アルゴリズム (全82問中57問目)

No.57

n個のデータを整列するとき,比較回数が最悪の場合でO(n2),最良の場合でO(n)となるものはどれか。
  • クイックソート
  • 単純選択法
  • 単純挿入法
  • ヒープソート

分類

テクノロジ系 » アルゴリズムとプログラミング » アルゴリズム

正解

解説

オーダ記法は、アルゴリズムの計算量が実行時に処理するデータ量によってどのように増加するかやアルゴリズムの実行時間の長さを示します。時間計算量を表すオーダ記法によってアルゴリズムの複雑さがわかり、アルゴリズムの理論的比較することができます。

それぞれの整列法の比較回数は次のようになっています。
11.gif/image-size:447×141
したがって最悪の場合で O(n2)、最良で O(n)となるアルゴリズムは「単純挿入法」が適切です。
© 2010-2018 応用情報技術者試験ドットコム All Rights Reserved.

Pagetop