平成24年度 秋期 応用情報技術者試験 午前 問6

• ア: 計算量の下限値を表す
  誤り。オーダ記法（O記法）は，入力サイズnが大きくなったときの計算量の上限（最悪でもこの程度に収まる増え方）を表すものです。下限値を表すものではありません。

• イ: これより遅くならないという計算量の上限値を表す
  正しい。O(n²) のように表し，入力サイズが大きくなっても計算量がその関数の定数倍を超えない，すなわちこれより遅くならないという上限を示します。

• ウ: 主要項の部分を除いて比較する
  誤り。オーダ記法では，最も増え方の大きい主要項だけを残し，それ以外の項や係数を除いて比較します。主要項を除くのは逆です。

• エ: 変数領域の大きさを表す
  誤り。オーダ記法は空間計算量にも使えますが，ここで問われている処理時間の比較では時間計算量を表します。変数領域の大きさそのものを表す記法ではありません。

答え

イ: アルゴリズムがこれより遅くならないという計算量の上限値を表す。