計算量とO記法 — Nが増えると何が起きるか

同じ「正しい」プログラムでも、データが増えたときに一瞬で終わるものと宇宙が終わっても終わらないものがある。その差を測る物差しが計算量、書き方がO記法です。数式より先に、まず「増え方」を目で見てしまいましょう。

1. 計算の競走 — 増え方はこんなに違う

入力サイズ N を1つ選ぶと、アルゴリズムの種類ごとに「必要な手数（ステップ数）」が決まります。下は6種類の代表的な増え方（オーダー）の競走です。スタートの合図で全員いっせいに走り出しますが、速く増えるものは一瞬で壁に激突します。

N のスライダーを大きくしてみてください。まず O(2ⁿ) が、続いて O(n²) が壁を突き破って画面外へ吹き飛びます。一方で O(1) や O(log n) はほとんど動きません。

6つのオーダーの競走 — 壁（予算）に先に激突するのは誰か

入力サイズ N

右端の赤い壁＝「512ステップの予算」。バーの長さがそのアルゴリズムの手数です。💥 が出たら予算を突破＝画面外へ吹き飛んだ合図で、実際の手数が赤字で出ます。N を上げると爆発する順番が見えます。

POINT — オーダーは「増え方の性格」大事なのはある瞬間の手数ではなく、N が2倍になったとき手数が何倍になるか。O(n) は2倍、O(n²) は4倍、O(2ⁿ) は2乗（＝もう1回まるごと）。この「性格」だけで、N が大きいときの勝負はほぼ決まってしまう。

2. 成長曲線を並べて見る

競走を横から見ると、手数を N の関数として描いた成長曲線になります。線形の目盛りだと、速く伸びるものは画面の上へすぐ消えてしまう（それが現実です）。「対数目盛」にチェックを入れると、全員を1画面に収めて傾きの違いとして比べられます。

成長曲線 — n のスライダーで各オーダーの正確な手数を読む

注目する n

対数目盛（縦軸）

縦線が「いま注目している n」。右上の表に各オーダーの正確な手数が出ます。線形目盛では n² と 2ⁿ が早々に画面の天井を突き抜けます。対数目盛にすると、指数関数 2ⁿ だけが「直線」になって、多項式（n・n²）とは別格の速さだと分かります。

N=1000 のとき　O(n)=1,000　／　O(n log n)≈10,000　／　O(n²)=1,000,000　／　O(2ⁿ)≈10³⁰¹ 10³⁰¹ は「宇宙の全原子数（約10⁸⁰）」を何度もかけ合わせた桁。指数関数は N が少し増えるだけで現実の外へ出る

3. なぜ定数や小さい項を捨てるのか

O記法は 50n や 3n+7 をぜんぶ「O(n)」と書きます。細かい係数や小さい項を捨てるのです。「乱暴では？」と感じますが、これはN が十分大きいときの勝負だけを見る、という約束。下で確かめましょう。

アルゴリズムA は係数の大きい線形 c×n、アルゴリズムB は係数1の二乗 n²。c を大きくしても、ある地点（交差点 n=c）を超えたら n² は必ず c×n に追い抜かれます。定数は「追い抜かれる地点を遅らせる」だけで、勝敗そのものは変えられません。

交差点 — 定数をいくら大きくしても n² はいつか必ず負ける

Aの係数 c（A = c×n）

青＝A（c×n、線形）、橙＝B（n²、二乗）。走り回る白い点が現在地で、そのときの手数と勝者を表示します。交差点 n=c より左では B が速い（定数のせいでA が損）、右では A が速い。c を上げると交差点は右へ動くだけで、必ず存在します。

注意 — O記法は「大きい N」の話だから、扱う N がいつも小さいと分かっているなら、O が悪くても定数の小さい単純なアルゴリズムのほうが速いことは普通にある。O記法は万能の優劣ではなく、「N が伸びたときにどうなるか」という一面を測る道具。現場では実測とセットで判断する。

4. どれくらい待つのか — 手数を時間に換算する

最後に、手数を実際の待ち時間に変えてみます。今どきのCPUを大まかに「1秒間に10億ステップ（10⁹）」として、各オーダーの所要時間を並べたのが下の図です。時間軸は対数（1目盛りで10倍）なので、桁違いの差が横幅の差として見えます。

実時間の対決 — 同じ N でも「一瞬」と「宇宙の年齢超え」が同居する

入力サイズ N

1秒に10億ステップとした場合の所要時間。灰色の縦線は「1秒」「1年」「宇宙の年齢（約138億年）」の目印。N を上げていくと、O(2ⁿ) のバーが1年、そして宇宙の年齢の線をあっさり越えます。O(n log n) までは現実的、O(n²) は大きなNで苦しく、O(2ⁿ) は小さなNですら絶望的、という肌感覚をつかんでください。

5. まとめ — オーダーで世界を見る

計算量は「N が増えたとき手数がどう増えるか」を測る。定数や小さい項は捨て、増え方の性格だけを O記法で表す。
速い順のだいたいの序列：O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ)。境目の O(n log n)（速いソートなど）までが「実用の壁」。
O(n²) は大きな N でつらく、O(2ⁿ)（総当たり）は小さな N ですら破綻する。だからアルゴリズムを工夫してオーダーそのものを下げることに価値がある。

一歩先へ — O・Ω・Θ と最悪／平均正確には O は「これ以上は増えない」上界、Ω は下界、Θ は上下ぴったりを表す。また同じアルゴリズムでも入力次第で手数は変わるため、最悪計算量（保証）と平均計算量（ふつうの体感）を区別する。クイックソートは平均 O(n log n) だが最悪 O(n²)、といった「顔の使い分け」は次のレッスン以降でくり返し出会うことになる。