BUILD YOUR UNDERSTANDING
情報処理技術者試験の用語集
言葉の意味を確かめて、問題への理解を一歩深めましょう。
オーダー記法
入力が増えたときの伸び方
オーダー記法は、入力の大きさに対して処理時間や記憶量がどの程度増えるかを、主要な増え方に着目して表す方法です。Big-Oは漸近的な上界を示します。実際の何秒という値ではなく、データが大きくなったときの傾向を比較するために使います。時間計算量と空間計算量は別々に考えます。
代表的な増え方
| 表記 | 代表的な意味 | 例となる処理 |
|---|---|---|
| O(1) | 入力数によらない程度 | 配列の特定位置を参照 |
| O(log n) | 対数的に増える | 整列配列の二分探索 |
| O(n) | 入力数に比例する | 全要素を一度調べる |
| O(n log n) | 線形より大きい増加 | 比較による効率的な整列 |
| O(n²) | 二乗に比例する | 全ての要素対を調べる |
| 前提となるデータ構造や操作の費用をそろえて比較します。 |
ループの読み方
n回のループの中で、毎回n回の処理をすれば、全体はn²回程度です。一方、二つのn回のループが順に並ぶだけなら、合計は2n回で、主要な増え方はO(n)です。内側の回数が外側の位置によって変わる場合は、各回の合計を求めます。入れ子の深さだけで機械的に判断してはいけません。
定数と最悪時
O(n)の処理が、小さな入力でも必ずO(n log n)より速いとは限りません。定数倍、入出力、実装方法などが影響するからです。また、最良、平均、最悪のどの状況を表すかを確認します。ハッシュ表の平均的な探索と、衝突が多い場合の最悪の探索を同じ保証として扱わないようにします。
試験での要点
3n²+5n+7のような式では、大きなnで支配的な項に着目します。ただし、Big-Oは厳密に同じ増え方を表すΘ記法と定義が異なります。試験の表現に従いながら、実行時間そのものではないことを押さえます。入力を何倍にしたとき処理量がどう変わるかを考えると、式の暗記だけでなく、方式を選ぶ判断へ結び付けられます。
参考資料
内容確認日:2026-11-13