平成24年度秋期 応用情報技術者試験 午前 問6
アルゴリズムの処理時間や問題の計算時間を比較するときに使用するオーダ記法の説明として，適切なものはどれか。
- ア アルゴリズムが解に到達するまでの計算量の下限値を表す。
- イ アルゴリズムがこれより遅くならないという計算量の上限値を表す。
- ウ アルゴリズムの解析では，主要項の部分を除いて比較する。
- エ アルゴリズムを実現した場合の変数領域の大きさを表す。
解答・解説を見る
正解：イ
AI解説
オーダ記法(O記法)は、入力サイズnが大きくなったときの計算量の増え方の上限を表す。O(f(n))は「計算時間がf(n)の定数倍を超えない」すなわちこれより遅くならないという上限値を示すものであり、イが適切である。 ア: 計算量の下限を表すのはΩ(オメガ)記法であり、O記法ではない。 イ: 正解。O記法は漸近的な上限(これより悪くならない保証)を表す。 ウ: 誤り。オーダの解析では主要項以外(低次の項や定数係数)を除き、主要項だけで比較する。「主要項を除く」は逆である。 エ: 変数領域の大きさは空間計算量の話であり、O記法自体の説明として不適切である。 💡 O=上限(Upper)、Ω=下限、Θ=上下限一致と整理する。選択肢ウのように「主要項を除く/主要項だけ残す」を逆にしたひっかけが定番なので語尾まで読むこと。
出典：平成24年度 秋期 応用情報技術者試験 午前 問6 ／ 独立行政法人情報処理推進機構（IPA）
※Web掲載用に表記を一部変更しています。著作権はIPAに帰属します。
※Web掲載用に表記を一部変更しています。著作権はIPAに帰属します。