O(n)とかO(n²)とか、あの記法に身構える人は多いと思います。でも中身は、「入力サイズnが増えたとき、比較回数や処理回数がどう増えるか」を評価する考え方です。この記事では計算量の問題を、正確な処理回数を数える問題、「n²に比例する」と与えられた倍率問題、O記法で増加率を見分ける問題、そして最良・平均・最悪の区別、という4つの観点に分けて整理します。この4つを混ぜずに扱えるようになるのが今日のゴールです。
O記法は「大きなnでの増え方」を見る
O記法は、入力サイズnが十分大きいときに、処理量がどの程度の増加率を超えないかを、定数倍を除いて表す漸近的な上界の記法です。試験教材では、支配的な増加率を表すためにO(n²)などと書くのが一般的で、定数係数と低次項は表示しません。実行秒数そのものを表すわけではありません。
たとえば処理回数が T(n) ＝ 3n² ＋ 5n ＋ 100 なら、大きなnではn²の項が支配的なので、試験で一般的な表し方は O(n²)。数学的に項が消滅するわけではなく、漸近的な増加率を表す際に、定数係数3と低次項5n＋100を省略して書く、という意味です（この式は上下からn²の定数倍で押さえられるので、より厳密にはΘ(n²)とも書けます。試験ではOで十分です）。
大事な注意をひとつ。「O(n²)だから、データ2倍で実行時間はきっかり4倍」とは限りません。きっかり4倍として計算してよいのは、「処理時間はn²に比例する」と問題文に明示されているか、支配項だけで近似する問題のとき。実測時間には定数係数・実装・ハードウェア・キャッシュ・入出力なども効いてきます。問題文の「比例する」の一文が、正確な倍率計算の前提になります。
代表的な増加率を並べる
次の倍率は、処理量が各行の代表式に比例すると仮定した場合の目安です。O記法の分類だけから、実測時間の正確な倍率を断定することはできません。
| 計算量 | 支配項に比例すると仮定したときの倍率の目安 | 代表例 |
|---|---|---|
| O(1) | 1倍 | 配列の添字による1要素アクセス（標準的な計算モデルで） |
| O(log n) | log(kn)÷log(n) | 整列配列の二分探索 |
| O(n) | k倍 | 線形探索 |
| O(n log n) | k×log(kn)÷log(n) | マージソート、ヒープソート |
| O(n²) | k²倍 | 単純なバブルソート、選択ソート |
| O(n³) | k³倍 | 三重ループ |
| O(2^n) | 急激に増加 | 部分集合の単純な全探索 |
| O(n!) | 非常に急激に増加 | 全順列の単純な全探索 |
大小関係はこうです（十分に大きなnでの代表的な増え方です）。
O(1) ＜ O(log n) ＜ O(n) ＜ O(n log n) ＜ O(n²) ＜ O(n³) ＜ O(2^n) ＜ O(n!)
O(log n)は「増えない」のではなく「増え方が緩やか」です。数字で見ると（処理量がlog₂nに比例すると仮定した場合）、n＝1,024でlog₂n＝10、n＝10,240でlog₂n≒13.322。データが10倍になっても対数部分は約1.332倍。O(n)の10倍、O(n²)の100倍と比べて増加が緩やかですが、ゼロではありません。
対数の底について一言。オーダー比較では底の違いは定数倍にしかならないので省略してかまいません（log₂n＝log₁₀n÷log₁₀2）。一方、二分探索の具体的な比較回数を数えるときは、範囲を半分にするのでlog₂を使います。
倍率問題：「比例する」の条件を確認して2乗
例題：処理時間がnの2乗に比例するアルゴリズム。データが1,000件のとき4秒なら、2,000件では？
データの倍率：2,000 ÷ 1,000 ＝ 2倍
時間の倍率：2² ＝ 4倍
4秒 × 4 ＝ 16秒
データ件数の倍率2をそのまま時間の倍率として使うと、8秒という誤った値になります。「何倍になったか」を先に出して、それを2乗する。そして繰り返しますが、この計算が成立するのは「比例する」と与えられているからです。
O(n log n)の倍率：nの部分とlogの部分を別々に
例題：処理時間が支配項 n log₂n に比例すると仮定する。n＝1,024から n＝2,048 になったら処理時間は何倍？
nの部分：2,048 ÷ 1,024 ＝ 2倍
logの部分：log₂1,024＝10、log₂2,048＝11 なので 11÷10 ＝ 1.1倍
合わせて 2 × 1.1 ＝ 2.2倍
同じ条件でn²に比例すると仮定した場合は4倍ですが、n log₂nに比例するモデルでは2.2倍。nが大きいほどこの差は開くので、大量データの整列ではO(n log n)の方式（マージソートなど）が有利になりやすいわけです。なおこの2.2倍も「支配項に比例する」という仮定の下での近似で、O(n log n)という分類だけから断定できる数字ではありません。
二分探索：最大比較回数は「半減の回数＋1」
O(log n)の代表、二分探索。整列済みのデータの真ん中と比べて、半分を捨てる、を繰り返す探し方です。成立には条件があります：データが探索キー順に整列されていること、中央位置に効率よくアクセスできること（配列なら中央要素へ定数時間でアクセスできる標準的なモデルを想定できます。単方向リストだと中央への移動自体にコストがかかるので同じ効率にはなりません）。
例題：整列済みの1,024件の配列に標準的な二分探索を行う。探索キーと配列要素の比較を1回と数えるとき、最大比較回数は？
1,024 ＝ 2^10。範囲を半分にして1件相当まで絞る操作が10回。
ただし、絞った最後の候補と一致するかの比較も1回数えるので、
最大比較回数は 11回
半減の回数だけを数えると10回になりますが、ここでは探索キーと中央要素の照合を1回の比較と数え、最後に残った候補との照合も1回に含める、という数え方をしています。この数え方では、半減の回数（10回）と、キーとの比較回数（最大11回）は別物。代表式は、
最大比較回数 ＝ floor(log₂n) ＋ 1（＝ceil(log₂(n＋1))、n≧1）
で、1,023件なら最大10回、1,024件なら最大11回、100万件でも最大20回。1,024件から約100万件へ、データが約1,000倍になっても、このモデルでの最大比較回数は11回から20回への増加にとどまる——この増え方の緩やかさが二分探索の強みです。ちなみに問題文や擬似コードによって比較の数え方（等値と大小を別に数えるなど）が違うことがあるので、その場合は問題文の定義を優先してください。
線形探索（先頭から順に見て、見つかった時点で終了、各要素との照合を1回と数える）と比べてみます。探索対象が必ず存在し、どの位置にも同じ確率であるなら、平均比較回数は(1＋2＋…＋n)÷n ＝ (n＋1)/2。n＝1,000なら500.5回（「約500回」は近似表現で、この条件が崩れれば平均も変わります）。整理すると：
| 線形探索の条件 | 比較回数 |
|---|---|
| 最初に見つかる | 1回 |
| 存在し、位置が一様（平均） | (n＋1)/2回 |
| 最後にある | n回 |
| 存在しない | n回 |
1,000件で平均500回強（線形探索・成功時一様分布の平均）vs 最大11回（二分探索の最大比較回数）。比べている量の種類は違いますが、条件次第でこれだけの差になります。二分探索は「整列済みデータを半分ずつ絞る」代表例で、データベースの索引では、B木・B+木などで探索範囲を段階的に絞る方法や、ハッシュによって格納位置を求める方法などが使われています（ハッシュは半分ずつ絞る方式ではなく、索引が二分探索そのものというわけでもありません）。
バブルソートの比較回数は実装条件を確認する
例題：8件のデータを、各パスで未整列部分の隣接要素を比較し、全パスを実行するバブルソートで整列。比較回数は？
各パスの比較は n−1、n−2、…、1回と減っていくので、合計は、
(n−1)＋(n−2)＋…＋1 ＝ n(n−1)÷2
8件なら：7＋6＋5＋4＋3＋2＋1 ＝ 28回
2で割らずにn(n−1)とすると、8件では56回という誤った値になります。この式、確率の記事でやったnC2と同じ形ですよね。ただし正確に言うと「元のn個から2個を選ぶ全ペアを1回ずつ比較する」わけではなく（比較相手は交換で入れ替わっていきます）、比較回数の合計が1＋2＋…＋(n−1)になり、結果としてnC2と同じ式になる、という関係です。記憶のフックとしては十分使えます。
もうひとつ、実装による違いも問われます。「交換が一度も起きなければ終了する」早期終了付きの改良版だと、既に整列済みの入力ならn−1回の比較で終わります。
| 実装・条件 | 比較回数・計算量 |
|---|---|
| 全パス型（各パスで比較範囲を1件ずつ縮める） | n(n−1)/2回 |
| 早期終了付き・最良（整列済み入力） | n−1回、O(n) |
| 早期終了付き・平均 | O(n²) |
| 早期終了付き・最悪 | n(n−1)/2回、O(n²) |
「バブルソートは何回？」と聞かれたら、どの実装か・どんな入力かを問題文で確認してから答えてください。
ループの計算量は「深さ」でなく「反復回数」で数える
「二重ループ＝n²」と丸暗記すると足をすくわれます。4つのパターンを見比べてください。
① 各ループが独立にn回 → 内側の処理はn×n＝n²回。O(n²)
“`text for i＝1 to n for j＝1 to n 定数時間の処理 “`
② 内側が1からiまで（三角形型） → 1＋2＋…＋n ＝ n(n＋1)/2回。これもO(n²)（係数と低次項は省略）
“`text for i＝1 to n for j＝1 to i 定数時間の処理 “`
③ 内側の変数が2倍ずつ増える → 内側はlog₂n回で、全体はn×log₂n。O(n log n)
“`text for i＝1 to n j＝1 while j＜n 定数時間の処理 j＝j×2 “`
④ ループが入れ子でなく連続 → n＋n＝2n。O(n)
“`text for i＝1 to n 処理A for j＝1 to n 処理B “`
見るポイントは、ネストの深さではなく、各ループの反復回数・内側の上限が外側に依存するか・変数の更新が＋1か×2か・内側の処理自体の重さ（ループ本体がO(n)なら反復回数だけでは決まりません）。連続する処理は和。入れ子は、各外側の反復に対する内側の反復回数を数え、独立に一定回数ずつなら積、内側の上限が外側に依存するなら各回の反復数の総和、です（②の三角形型がn×nでなく1＋2＋…＋nになるのがその例です）。
同じアルゴリズムでも入力で変わる：最良・平均・最悪
| アルゴリズム | 最良 | 平均 | 最悪 |
|---|---|---|---|
| 線形探索 | O(1) | O(n) | O(n) |
| 二分探索 | O(1) | O(log n) | O(log n) |
| 早期終了付きバブルソート | O(n) | O(n²) | O(n²) |
| クイックソート | O(n log n) | O(n log n) | O(n²) |
代表的なクイックソートでは、分割が大きく偏らない場合はO(n log n)、ピボットの選び方と入力によって分割が極端に偏るとO(n²)になることがあります。最良・平均・最悪の違いを確認する代表例です。問題文がどれを聞いているか、最初に丸をつけてください。
実測値から増加率を推定する
逆に、測った時間から計算量を当てる問題もあります。nを2倍にしたときの時間の倍率が目安です。
| nを2倍にしたら | 推定候補 |
|---|---|
| 約1倍 | O(1) |
| 少し増える | O(log n) |
| 約2倍 | O(n) |
| 2倍より少し大きい | O(n log n) |
| 約4倍 | O(n²) |
| 約8倍 | O(n³) |
ただしこの表は、同じ環境と実装で、支配項の影響が現れる程度にnが大きい場合の目安です。nが小さいと固定処理の影響が大きく、測定誤差・キャッシュ・I/Oでも理論値からズレます。1つの測定倍率だけで計算量を確定せず、複数の測定点から傾向を確認します。
解く前の判定フロー
- 求めるのは正確な回数か、オーダー（増加率）か
- nが何倍になったか。「比例する」と明記されているか
- 最良・平均・最悪のどれか
- ループなら各反復回数とループ本体の重さを数える（入れ子は各外側の反復について内側の回数を数える。×2更新はlog）
4-2. O記法だけから正確な実行時間の倍率を求めようとしていないか確認
- 二分探索なら整列済みか。最終候補との比較を数えるか
- ソートなら実装（全パス型か早期終了付きか）を確認
- O記法なら定数倍と低次項を省略
- 最後に単位（回数・倍・秒）を確認
代表的なミスまとめ
| ミス | 出てくる誤答 | 対策 |
|---|---|---|
| n²を比例で計算 | 倍率そのままの値 | 「何倍か」を出してから2乗 |
| O(n²)を無条件に正確な比例式と扱う | 実測と合わない倍率 | 「比例する」の条件を確認 |
| O(log n)を一定時間と考える | 比較回数が増えない値 | log₂nで緩やかに増える |
| 1,024件の最大比較を10回とする | 最後の候補との照合を含めない値 | 問題文の比較定義を確認（この例では最後の照合込みで11回） |
| 未整列データに二分探索 | 探索自体が不成立 | 整列済みが前提 |
| 線形探索の平均を無条件にn/2 | 条件に合わない値 | 成功時・一様分布で(n＋1)/2 |
| バブルソートを常にn(n−1)/2 | 早期終了の最良時で過大 | 実装と入力を確認 |
| 二重ループを無条件にn² | n log n等の誤判定 | 各反復回数を数え、依存関係があれば総和を求める |
| 連続ループを掛け算する | n²と誤答 | 連続する処理は和で数える |
| 平均と最悪の取り違え | 条件違いの値 | 評価区分に丸をつける |
| 途中で丸める | 倍率が微妙にズレる | 丸めは最後の1回 |
仕上げに演習10問どうぞ
演習では、計算量の倍率、探索・整列の比較回数、ループの反復回数などを確認できます。再帰関数のトレースや二分探索木・完全二分木のような木構造の問題が含まれている場合、それらは計算量とは別の関連論点なので、詰まったら焦らず、まず計算量の問題から固めるのがおすすめです。
今日のまとめ
- O記法は十分大きなnでの漸近的な増加率（上界）。定数係数と低次項は表示せず、実行秒数そのものではない
- 正確な倍率を出せるのは「n²に比例する」などの条件があるとき。倍率を出してから2乗
- O(log n)は「増えない」でなく「増加が緩やか」（データ10倍で対数部分は約1.33倍）
- 二分探索は整列済みが前提で、比較回数は数え方の定義とセット。この記事の数え方では最大floor(log₂n)＋1で、1,024件なら11回
- 線形探索の平均(n＋1)/2は「必ず存在・位置が一様」の条件つき
- バブルソートの比較回数とループの計算量は、実装・入力・各反復回数を確認。独立した入れ子は積、依存する入れ子は総和、連続処理は和
- 最良・平均・最悪のどれを聞かれているか、最初に丸をつける
次回は「損益分岐点」。売上高・利益・目標利益の計算を整理します。
参考資料
- IPA「基本情報技術者試験（レベル2）シラバス Ver.9.2」
本記事の例題は、基本情報技術者試験の出題範囲及び標準的なアルゴリズム解析を参考に、当サイトで独自に作成したものです。
コメント