応用情報技術者 2012年 秋期 午前2 問06
問題文
アルゴリズムの処理時間や問題の計算時間を比較するときに使用するオーダ記法の説明として、適切なものはどれか。
選択肢
ア：アルゴリズムが解に到達するまでの計算量の下限値を表す。
イ：アルゴリズムがこれより遅くならないという計算量の上限値を表す。（正解）
ウ：アルゴリズムの解析では、主要項の部分を除いて比較する。
エ：アルゴリズムを実現した場合の変数領域の大きさを表す。
オーダ記法の説明 +【午前2 解説】
要点まとめ
- 結論：オーダ記法はアルゴリズムの計算時間の上限を示し、最悪ケースの性能評価に用います。
- 根拠：計算量の上限値を示すことで、入力サイズが大きくなった場合の処理時間の増加傾向を把握可能です。
- 差がつくポイント：下限値や変数領域の大きさと混同せず、主要項を残して定数や低次の項を無視する点を正確に理解しましょう。
正解の理由
イは「アルゴリズムがこれより遅くならないという計算量の上限値を表す」とあり、これはビッグO記法の定義に合致します。ビッグO記法は最悪の場合の計算時間の上限を示し、アルゴリズムの性能評価で最も一般的に使われます。
よくある誤解
オーダ記法は計算量の下限や平均値を示すものではなく、また変数領域の大きさ（メモリ使用量）を表すものでもありません。主要項を残し定数項を無視する点も誤解されやすいです。
解法ステップ
- オーダ記法の定義を確認する（計算時間の上限を示す）。
- 選択肢の説明が上限値か下限値かを判別する。
- 変数領域や主要項の扱いに関する説明が正しいか検証する。
- 最も正確にビッグO記法の意味を表す選択肢を選ぶ。
選択肢別の誤答解説
- ア：計算量の下限値はΩ記法で表し、オーダ記法（ビッグO）とは異なります。
- イ：正解。計算時間の上限値を示し、最悪ケースの性能評価に用います。
- ウ：主要項を残し定数項を無視するのは正しいが、「主要項の部分を除く」とは逆の意味で誤りです。
- エ：変数領域の大きさは空間計算量で表し、オーダ記法の説明としては不適切です。
補足コラム
オーダ記法には主にビッグO（上限）、ビッグΩ（下限）、ビッグΘ（平均や厳密な漸近挙動）があります。ビッグOは最悪ケースの計算時間を示し、アルゴリズムの効率比較に広く使われています。計算量解析では定数や低次の項を無視し、入力サイズが大きくなったときの挙動に注目します。
FAQ
Q: オーダ記法は平均計算時間も表せますか？
A: ビッグOは主に最悪ケースの上限を示します。平均計算時間はビッグΘや別の解析で評価します。
A: ビッグOは主に最悪ケースの上限を示します。平均計算時間はビッグΘや別の解析で評価します。
Q: 変数領域の大きさはオーダ記法で表せますか？
A: 変数領域は空間計算量で表し、オーダ記法は時間計算量の上限を示すことが多いです。
A: 変数領域は空間計算量で表し、オーダ記法は時間計算量の上限を示すことが多いです。
関連キーワード: オーダ記法、ビッグO記法、計算量解析、アルゴリズム、時間計算量、空間計算量
\ せっかくなら /
応用情報技術者を
クイズ形式で学習しませんか？
クイズ画面へ遷移する→
すぐに利用可能！