応用情報技術者 2012年 秋期 午前2 問06

オーダ記法の分類【午前2解説】

正解の理由

解法ステップ

1. 設問文のキーワードを把握：「計算時間を比較するときに使用するオーダ記法の説明」。選択肢は「上限」「下限」「主要項の除去」「変数領域」のような語句を含む。
2. 各語句を既知の記法に対応付ける：
   • 「上限」→ ビッグO（$O$）
   • 「下限」→ ビッグΩ（$\Omega$）
   • 「上限かつ下限（厳密な漸近境界）」→ ビッグΘ（$\Theta$）
3. 選択肢を検証して最も一致するものを選ぶ：上限の説明に一致するのはイ。

選択肢別の誤答解説

• ア: 「計算量の下限値を表す」——これはビッグΩ（$\Omega$）の説明です。アルゴリズムが最低でもこれだけはかかる、という下界を示します。
• イ: 「これより遅くならないという計算量の上限値を表す」——ビッグOの定義に合致します。実際には「これより大きくならない（上から抑える）」という意味の漸近上界です。
• ウ: 「主要項の部分を除いて比較する」——説明があいまいで誤りです。オーダ記法では定数倍や低次の項を無視して漸近挙動（主要項）に着目しますが、「主要項を除く」という表現は逆であり誤解を生みます。正しくは「定数や低次の項は無視して主要（高次）項で比較する」です。
• エ: 「変数領域の大きさを表す」——これは空間計算量（メモリ使用量）に関する記述で、オーダ記法自体は時間にも空間にも使えますが、設問は処理時間の比較を問うているため不適切です。

よくある誤解

1. ビッグΘ＝「平均時間」ではない：Θは上界と下界の両方を満たす厳密な漸近境界（tight bound）を意味します。平均ケースを表す記法ではなく、平均・最悪・最良のどのケースを扱うかは明示が必要です。
2. オーダ記法が実行時間の定量的な予測になると考える誤り：定数係数や低次の項を省くため、小さい入力サイズや定数因子の影響が重要な場合には実行時間の大小が逆転することがあります。
3. 「上限」と「最悪ケース」を混同する誤り：ビッグOは上界を示しますが、解析対象を最悪ケースにするのか平均ケースにするのかは別途指定する必要があります。

補足コラム

• 代表的な定義（形式）
  • $f(n)=O(g(n))$：上界（存在する定数 $c,n_0$ に対し $f(n)\le cg(n)$）
  • $f(n)=\Omega (g(n))$：下界（存在する定数 $c,n_0$ に対し $f(n)\ge cg(n)$）
  • $f(n)=\Theta (g(n))$：上界かつ下界（$f(n)=O(g(n))$ かつ $f(n)=\Omega (g(n))$）
• 実例：挿入ソート
  • 最良ケース（既に整列済み）: $O(n)$
  • 平均ケース: $O(n^2)$（平均計算時間は別途導出する必要あり）
  • 最悪ケース: $O(n^2)$
    ここで記号 $O$ は「漸近的にこれを上回らない」という意味で使用しています。
• オーダ記法は時間計算量だけでなく空間計算量の評価にも用いられます（ただし問題文の文脈を確認）。

FAQ