計算量とオーダー記法｜コンピュータ基礎

🎓 レベル：基礎　|　重要度：A（必須）

📎 前提：なし（この章の出発点）　|　関連：基本データ構造・性能の評価とアムダールの法則

要点（BLUF）

計算量は「入力サイズ n が増えると、処理ステップ数がどう増えるか」を表す。実時間は機械やデータで変わるが、増え方の型は本質的でぶれない。
O記法は、定数倍と低次の項を無視し、**最高次の項（支配項）**だけで増え方を表す。3n^2 + 100n + 5 は O(n^2)。
n が大きくなると、オーダーの差は爆発的になる。O(log n) と O(n^2) と O(2^n) の差は、実用と非実用を分ける。

概念 ── なぜ「増え方」で測るのか

同じ処理でも、速いPCと遅いPCでは実時間が違います。データの中身でも変わります。では何がアルゴリズム固有の性質か。それは「入力が大きくなったとき、どんなペースで遅くなるか」です。

例えば、要素数 n の配列から目的の値を線形に探すと、最悪 n 回比較します。n が2倍なら手間も約2倍。これは O(n)。一方ソート済み配列を二分探索すれば、n が2倍でも手間は1回増えるだけ（O(log n)）。この増え方の型が、アルゴリズムの良し悪しを決めます。

仕組み ── O記法の約束（定数倍と低次を捨てる）

O記法は、関数の増え方の上界を表します。正式には「ある定数 c と十分大きい n に対し f(n) <= c·g(n)」なら f(n) = O(g(n))。実用上のルールは2つ。

定数倍を無視：5n も 100n も O(n)。機械やコンパイラ最適化で変わる定数は本質でない。
最高次の項だけ残す：3n^2 + 100n + 5 は O(n^2)。n が大きいと n^2 が他を圧倒する。

flowchart LR
    f["3n^2 + 100n + 5"] -->|"低次・定数を捨てる"| g["O(n^2)（支配項だけ）"]

なぜこんな大胆な省略が許されるのか。n が大きい領域では支配項が全てを決めるからです。n=10^6 なら n^2 = 10^12 に対し 100n = 10^8 は1万分の1で誤差。だから「型」だけ見れば十分なのです。

ついでに最良・平均・最悪の区別も重要。線形探索は運が良ければ1回（最良 O(1)）、平均 n/2、最悪 n（O(n)）。普通は最悪計算量で語ります（保証が要るから）。

仕組み ── 増え方の比較（数値で実感）

代表的なオーダーが n とともにどう増えるか（[[#対応ラボ]] の 06-01_growth_rates.py）。

import math
for n in (8, 64, 1024, 1_000_000):
    print(n, math.log2(n), n, n*math.log2(n), n*n)  # log n / n / n log n / n^2

実行結果（実機・抜粋）:

       n |    log n |          n |      n log n |            n^2 |          2^n
       8 |      3.0 |          8 |           24 |             64 |          256
      64 |      6.0 |         64 |          384 |          4,096 |     1.84e+19
 1000000 |     19.9 |  1,000,000 |   19,931,568 |       1.00e+12 |        (超巨大)

同じ問題サイズ n = 1,000,000 で比べると差は歴然：

O(log n) ≒ 20 回         <- 二分探索
O(n)      = 1,000,000 回   <- 線形探索
O(n log n)= 19,931,568 回   <- 良い整列
O(n^2)    = 1,000,000,000,000 回   <- 素朴な整列（1兆回＝非現実的）

O(log n) はわずか20回、O(n^2) は1兆回。同じ問題でもアルゴリズム次第で「一瞬」と「事実上不可能」に分かれる。さらに O(2^n) は n=64 で既に宇宙の原子数級になり、総当たりが破綻する理由を示します（基本アルゴリズム）。

仕組み ── 時間計算量と空間計算量

計算量には2つの軸があります。

時間計算量：ステップ数（速さ）。
空間計算量：使うメモリ量。

両者はトレードオフすることが多い。例えばハッシュ表（基本データ構造）はメモリを多めに使って検索を O(1) にする。メモ化（計算結果の保存）は空間を使って時間を買う。「どちらが希少資源か」で選びます。これは計算機の制約（メモリ階層とキャッシュ）と直結します。

仕組みの直観 ── なぜこの設計か（なぜO記法が有用か）

定数倍を捨てる理由：定数は機械・言語・実装で変わる「環境依存」。アルゴリズムの本質的な優劣を語るには、環境に左右されない「増え方の型」に集中するのが正しい。
最悪計算量を使う理由：システムは最悪ケースでも動く保証が要る（リアルタイム性・SLA）。平均が良くても最悪が爆発するなら使えない場面がある。
オーダーが実務を支配する理由：データは増え続ける。今は小さくても、n が10倍100倍になったとき、定数倍の差は誤差、オーダーの差は致命傷。だから設計時にオーダーを見る。

⚠️ よくある誤解・落とし穴

「O(n) は常に O(n^2) より速い」→ n が小さいと定数倍で逆転しうる。オーダーは大きな n での漸近の話。
「O記法があれば実時間が分かる」→ 分かるのは増え方だけ。実時間は定数倍と局所性（メモリ階層とキャッシュ）次第。両方見る。
「計算量が同じなら同じ速さ」→ キャッシュ効率（配列 vs 連結リスト）で実速度は数倍変わる（基本データ構造）。
「O(2^n) でも速いPCなら大丈夫」→ 指数は無理。n を少し増やすだけで宇宙年齢を超える。アルゴリズムを変えるしかない。

対応ラボ

cs-foundations-study/labs/06-01_growth_rates.py（実行して各オーダーの増え方を確認済み）。

確認できること：log n / n / n log n / n^2 / 2^n の爆発的な差