平成24年秋期試験問題 午前問6

アルゴリズムの処理時間や問題の計算時間を比較するときに使用するオーダー記法の説明として,適切なものはどれか。

  • アルゴリズムが解に到達するまでの計算量の下限値を表す。
  • アルゴリズムがこれより遅くならないという計算量の上限値を表す。
  • アルゴリズムの解析では,主要項の部分を除いて比較する。
  • アルゴリズムを実現した場合の変数領域の大きさを表す。
正解 問題へ
分野:テクノロジ系
中分類:アルゴリズムとプログラミング
小分類:アルゴリズム
解説
オーダー記法は、アルゴリズムの計算量が実行時に処理するデータ量によってどのように増加するかやアルゴリズムの実行時間の長さを示します。時間計算量を表すオーダー記法によってアルゴリズムの複雑さがわかり、アルゴリズムの理論的比較することができます。

ちなみに情報処理技術者試験に出題される整列アルゴリズムのオーダーは、
  • バブルソート,基本選択法,基本挿入法→0(n2)
  • クイックソート,マージソート,ヒープソート→0(nlog2n)
となっています。
  • オーダー記法が表すのは計算量の上限値や処理件数による計算量の増加率です。
  • 正しい。
  • 主要項ではなく係数や定数を除外して比較します。
  • 領域計算量の説明です。

Pagetop