平成24年度 秋期 応用情報技術者試験 午前 問6
テクノロジ／アルゴリズムアルゴリズムの処理時間や問題の計算時間を比較するときに使用するオーダ記法の説明として，適切なものはどれか。
出典：平成24年度 秋期 応用情報技術者試験 午前 問6
- アアルゴリズムが解に到達するまでの計算量の下限値を表す。
- イアルゴリズムがこれより遅くならないという計算量の上限値を表す。
- ウアルゴリズムの解析では，主要項の部分を除いて比較する。
- エアルゴリズムを実現した場合の変数領域の大きさを表す。
正解：イ
解説
オーダ記法（O記法）は，データ量が十分大きくなったときにアルゴリズムの計算量がどのように増加するかを表す記法で，「これより計算量が悪くならない」という上限の目安を与えます。解析の際には，計算量への影響が小さい項を無視し，最も影響の大きい主要項に着目して比較します。
選択肢ごとの解説
- ア誤り。オーダ記法は下限値ではなく，計算量が増加していく上限の目安を表します。
- イ正しい。オーダ記法は，アルゴリズムの計算量がこれより遅くならないという上限の目安を表します。
- ウ誤り。オーダ記法の解析では，主要項の部分を除くのではなく，主要項以外の影響が小さい項を無視して主要項に着目します。
- エ誤り。これは空間計算量（メモリ使用量）に関する説明であり，処理時間の比較に使うオーダ記法自体の説明とは異なります。