対象試験と出題頻度
オーダー記法（O記法・計算量）は、応用情報技術者試験で出題されるテーマです。
整列・探索アルゴリズムの計算量を問う問題の前提知識として必須であり、「O(n)とO(n²)の違い」「二分探索法の計算量」といった形で繰り返し問われます。
H24秋期 応用情報 午前問6ではオーダー記法そのものの定義が直接出題されました。
詳細をクリックして確認
応用情報技術者
★★☆☆☆
ランクC（応用）余裕があれば覚える
用語の定義
情報処理試験を勉強していると、「O(n)とかO(log n)って結局何を表しているの？」と混乱しがちです。
オーダー記法（O記法）とは、一言で言うと
「アルゴリズムの処理時間が、データ量nの増加に対してどの程度の割合で増加するかを表す記法」
のことです。
イメージとしては、「料理にかかる時間を”人数に比例”か”人数の2乗に比例”かでざっくり見積もる」こと。
10人分の弁当を作るとき、おにぎりを握る作業は人数に比例（10人なら10個）ですが、全員が全員と名刺交換する作業は人数の2乗に比例（10人なら90回）です。
オーダー記法は、この「増え方のパターン」だけに注目し、定数や係数は無視してアルゴリズムの効率をざっくり比較する道具です。
📊 オーダー記法の基本情報
| 項目 | 内容 |
|---|---|
| 英語名 | Big-O Notation（ビッグオー記法） |
| 別名 | ランダウの記号、O記法（オーきほう） |
| 表すもの | アルゴリズムの時間計算量の上限（最悪でもこれ以上遅くならない） |
| 読み方 | O(n) →「オーダーn」「オーエヌ」、O(n²) →「オーダーnの2乗」 |
詳細解説
アルゴリズムを評価するとき、「実行時間が何秒か」は実行環境（CPUの速さやメモリ量）に依存するため、絶対的な指標にはなりません。
そこで「データ量が増えたときに処理時間がどう変化するか」という増加の傾向だけを取り出して比較する方法が求められました。これがオーダー記法の存在理由です。
オーダー記法のルール
オーダー記法では、計算量を表す式から「最も支配的な項だけを残し、係数と定数は無視する」というルールで表記します。
たとえば、あるアルゴリズムの実際の計算回数が「3n² + 5n + 10」だった場合、nが十分大きいとき支配的なのは n² の項です。係数3と低次項(5n、10)を除去し、O(n²) と表します。
▶ 代表的な計算量の成長曲線（クリックで展開）
データ量 n を横軸、処理時間を縦軸としたときの増加の様子を示します。下の表は n の値ごとの処理ステップ数を示したもので、増え方の違いを数値で体感できます。
📈 n = 64 のときの処理ステップ数（棒グラフ）
1
6
64
384
4,096
※棒の長さはO(n²)=4,096を100%として比率で表示
📊 データ量 n ごとの処理ステップ数
| n | O(1) | O(log n) | O(n) | O(n log n) | O(n²) |
|---|---|---|---|---|---|
| 8 | 1 | 3 | 8 | 24 | 64 |
| 64 | 1 | 6 | 64 | 384 | 4,096 |
| 1,024 | 1 | 10 | 1,024 | 10,240 | 1,048,576 |
| 1,000,000 | 1 | 20 | 1,000,000 | 20,000,000 | 1兆 |
※log は底2の対数で計算
棒グラフと表から分かるように、O(1)やO(log n)はデータ量が増えても処理時間がほぼ変わりません。一方、O(n²)はデータ量が8倍（8→64）になると処理ステップ数が64倍（64→4,096）に膨れ上がります。この「増え方の差」を一目で把握できるのがオーダー記法の強みです。
試験で問われる代表的な計算量
IPA試験では、整列アルゴリズムと探索アルゴリズムの計算量が定番の出題対象です。以下の表を丸暗記するだけで得点源になります。
📊 整列アルゴリズムの計算量一覧
| アルゴリズム | 最良 | 平均 | 最悪 |
|---|---|---|---|
| バブルソート | O(n) | O(n²) | O(n²) |
| 選択ソート | O(n²) | O(n²) | O(n²) |
| 挿入ソート | O(n) | O(n²) | O(n²) |
| クイックソート | O(n log n) | O(n log n) | O(n²) |
| マージソート | O(n log n) | O(n log n) | O(n log n) |
| ヒープソート | O(n log n) | O(n log n) | O(n log n) |
📊 探索アルゴリズムの計算量一覧
| アルゴリズム | 平均計算量 | 前提条件 |
|---|---|---|
| 線形探索法 | O(n) | 整列不要。先頭から順に比較する |
| 二分探索法 | O(log n) | データが整列済みであること |
| ハッシュ探索法 | O(1) | 衝突がない理想的なケースの場合 |
覚え方のコツは「基本的なソート（バブル・選択・挿入）はO(n²)、高速なソート（クイック・マージ・ヒープ）はO(n log n)」というグループ分けです。ここだけは確実に押さえてください。
では、この用語が試験でどのように出題されるか見ていきましょう。
💡 オーダー記法の核心を3行で
・データ量nに対する処理時間の増加パターンを表す記法で、係数と定数は無視する
・O記法は「これ以上遅くならない」計算量の上限を示す
・基本ソートはO(n²)、高速ソートはO(n log n)、二分探索はO(log n)と丸暗記する
試験ではこう出る！
オーダー記法は、「定義そのものを問う問題」と「具体的なアルゴリズムの計算量を問う問題」の2パターンで出題されています。
📊 過去問での出題実績
| 試験回 | 出題内容 | 問われたポイント |
|---|---|---|
| AP H24秋 午前 問6 |
オーダー記法の説明として適切なものを選ぶ問題。 | ・「計算量の上限値」が正解 ・「下限値」「変数領域の大きさ」「主要項を除外」がひっかけ |
| SW H19春 午前 問11 |
n個のデータを整列するとき、最悪O(n²)・最良O(n)となるアルゴリズムを選ぶ問題。 | ・「単純挿入法」が正解 ・各整列法の最良・最悪計算量を暗記しているかが勝負 |
| FE H27春 午前 問6 |
二分探索法の計算量のオーダーを表す式を選ぶ問題。 | ・O(log n)が正解 ・O(n)やO(n²)との区別が問われる |
📝 IPA試験での出題パターン
パターン1：「オーダー記法の定義を選べ」
O記法が「計算量の上限値」を表すことを知っていれば即答できる。ひっかけは「下限値」（Ω記法の説明）や「変数領域の大きさ」（領域計算量の説明）。
パターン2：「○○法の計算量は？」
具体的なアルゴリズム名と計算量の組合せを問う形式。二分探索法→O(log n)、線形探索法→O(n)、クイックソートの最悪→O(n²) などが頻出。前述の一覧表を暗記していれば得点できる。
試験ではここまででOKです。ランダウの記号の数学的な定義（上極限による形式的な定義）まで問われることはないので、深追いは不要です。
【確認テスト】理解度チェック
ここまでの内容を理解できたか、簡単なクイズで確認してみましょう。
Q. アルゴリズムの処理時間を比較するときに使用するオーダー記法（O記法）の説明として、最も適切なものはどれでしょうか？
- A. アルゴリズムを実現した場合に必要なメモリ領域の大きさを表す。
- B. アルゴリズムがこれより遅くならないという計算量の上限値を表す。
- C. アルゴリズムが解に到達するまでの計算量の下限値を表す。
正解と解説を見る
正解：B
解説：
O記法（ビッグオー記法）は、データ量nに対するアルゴリズムの計算量の上限、つまり「最悪でもこれ以上遅くならない」増加率を表す記法です。係数や低次項は無視し、最も支配的な項のみで表現します。
選択肢Aは「領域計算量（空間計算量）」の説明です。O記法は時間計算量にも領域計算量にも使えますが、この選択肢は「メモリ領域の大きさ」に限定しているため不正確です。選択肢Cは「Ω記法（ビッグオメガ記法）」の説明です。O記法が上限を表すのに対し、Ω記法は下限を表します。
よくある質問（FAQ）
Q. O(n log n)の「log」は何を底とした対数ですか？
情報処理の分野では底を2とする対数（log₂）が一般的です。ただし、オーダー記法では底の違いは定数倍の差にしかならないため、底を省略して単に「log n」と書きます。O(log₂ n)もO(log₁₀ n)もオーダーとしては同じO(log n)です。
Q. 「時間計算量」と「領域計算量」はどう違いますか？
時間計算量はアルゴリズムの「実行時間（演算回数）」の増加率を表し、領域計算量は「使用メモリ量」の増加率を表します。IPA試験で単に「計算量」と言った場合は時間計算量を指すケースがほとんどです。たとえばマージソートは時間計算量O(n log n)ですが、領域計算量はO(n)の追加メモリが必要になります。
Q. O記法以外にΩ記法やΘ記法もありますが、試験で問われますか？
IPA試験の範囲で問われるのはO記法（上限）だけです。Ω記法（下限）やΘ記法（上限と下限が一致）は、H24秋期 応用情報 午前問6のようにひっかけ選択肢として登場することはありますが、それらの定義自体が正解になるパターンは見られません。「O記法＝上限」とだけ覚えておけば十分です。
Q. 実務でオーダー記法はどう役立ちますか？
大量データを扱うシステム開発で、処理方式の選定に直結します。たとえば100万件のレコードを検索するとき、線形探索O(n)では最悪100万回の比較が必要ですが、二分探索O(log n)なら約20回で済みます。データベースのインデックス設計やAPIのレスポンス改善など、「このアルゴリズムでデータ量が増えたとき破綻しないか」を判断する物差しとして日常的に使われています。
