計算量とO記法
けいさんりょうとオーきほう
入力が増えたとき処理時間や使用メモリがどう伸びるかを表す記法。性能の共通言語。
概要
計算量とは、アルゴリズムが入力の大きさに応じてどれだけの時間（時間計算量）やメモリ（空間計算量）を必要とするかの尺度です。そしてO記法（ビッグ・オー記法）は、それを「入力 n が増えたときの伸び方」だけに注目して表す記法です。O(n) なら入力に比例して伸びる、O(n²) なら入力の2乗で伸びる、と読みます。
直感的には「入力を10倍にしたらどうなるか」を一言で答えるための言葉です。O(n) の処理は10倍遅くなり、O(n²) の処理は100倍遅くなり、O(log n) の処理はほとんど変わりません。開発中の手元データ1,000件では全部一瞬でも、本番の100万件でこの差は「一瞬」と「数時間」の差になって現れます。マシンや言語が変わっても伸び方の性質は変わらないため、O記法はエンジニアが性能を議論するときの共通言語になっています。
なぜ生まれたか
アルゴリズムの速さを比べたいとき、素朴な方法は実際に動かして秒数を測ることです。しかし実測値はマシンの速度、言語、コンパイラ、たまたま与えたデータに左右され、「このソートは0.3秒だった」という数字からは手順そのものの良し悪しが読み取れません。しかも一番知りたいのは「まだ経験していない大きさの入力でどうなるか」であり、それは測定では原理的に分かりません。
そこで計算機科学者たちは、もともと数学にあった「関数の漸近的な振る舞い」を表す記法を借りてきました。実行環境に依存する定数倍や、nが大きくなれば効かなくなる下位の項を思い切って捨て、「nを大きくしていったときの支配的な伸び方」だけを残す。この割り切りによって、実装の詳細から独立に手順そのものを比較でき、将来のデータ量に対する予言が可能になったのです。1960年代にKnuthらがアルゴリズム解析の標準としてこの記法を定着させ、以来、計算量はアルゴリズムの「仕様」の一部として語られるようになりました。
詳細
代表的なオーダーと成長曲線
よく登場するオーダーは5つ覚えれば十分です。速い順に、O(1)（定数時間 — 入力が増えても一定。ハッシュ化による辞書引きや配列の番号アクセス）、O(log n)（対数時間 — 候補を半分ずつ捨てる二分探索）、O(n)（線形時間 — 全件を一度なめるループ）、O(n log n)（良いソートの標準。マージソートやクイックソート）、O(n²)（2重ループ — 全要素の総当たり比較）です。この違いは、曲線として並べると一目で分かります。
数字で置き直すとさらに実感が湧きます。1回の操作を1マイクロ秒として n = 100万なら、O(log n) は約20マイクロ秒、O(n) は1秒、O(n log n) は20秒、そして O(n²) は約12日です。同じデータ、同じマシンでも、オーダーが1段違うだけで「待てる」と「待てない」の境界を越えてしまいます。この「入力を10倍にしたら」の感覚は、実際に n を動かして操作回数の桁が変わる瞬間を見ると腑に落ちます。
所要時間は 1億回/秒 のCPUで実行した場合の換算。棒は対数スケール（1目盛り = 1,000倍）。
スライダーで n を動かして、5つのオーダーの操作回数と所要時間を見比べてみてください。棒グラフは対数スケール — 1目盛りで10倍違います。
定数倍を無視するのはなぜか
O記法では「3n + 50」も「n」もまとめて O(n) と書きます。乱暴に見えますが、これは意図的な設計です。定数の3や50は、マシンの速さや実装の丁寧さで何倍も変わる「環境の事情」であり、手順そのものの性質ではありません。一方で n と n² の差は、どんな環境でも n を大きくすれば必ず逆転不能になる「手順の性質」です。O記法は後者だけを抽出するレンズなのです。また通常は「最悪の場合」を基準に語ります。平均は速いが特定の入力で破綻する手順（素朴なクイックソートなど）もあるため、保証として最悪計算量を押さえておくのが実務的です。時間だけでなくメモリにも同じ記法を使い、「時間を買うために空間を払う」（索引やキャッシュの維持）というトレードオフも計算量の言葉で表現できます。
実務で効く場面 — N+1問題とネストループ
O記法がもっとも役立つのは、コードレビューで性能問題を「起こる前に」見抜くときです。典型例のひとつが ORM で悪名高い N+1 問題です。一覧を1クエリで取り、各行についてループ内で関連データを1クエリずつ取ると、SQL の発行回数が n に比例して増えます。1件あたりの通信往復という大きな定数が掛かった O(n) は、データ100件の開発環境では気づかず、本番の1万件で突然火を噴きます。もうひとつの定番が無自覚なネストループです。「配列Aの各要素について、配列Bに含まれるか線形探索する」コードは O(n²) で、どちらかをデータ構造のハッシュテーブルに変えるだけで O(n) に落ちます。データベースのインデックスが効くのも同じ理屈で、全行走査 O(n) を B-tree の探索 O(log n) に置き換えているのです。
落とし穴 — 小さいnでは定数倍が支配する
一方で、O記法を万能の物差しと思い込むのも危険です。捨てたはずの定数倍は、n が小さいうちはむしろ支配的だからです。要素数十数個なら、O(n²) の挿入ソートのほうがオーバーヘッドの大きい O(n log n) のソートより速いことは珍しくなく、実際に多くの標準ライブラリは小さな区間で挿入ソートに切り替えるハイブリッド実装になっています。また、配列の連続アクセスは CPUキャッシュに乗って理論値以上に速く、ポインタをたどる連結リストは同じ O(n) でも大幅に遅い、というようにメモリ階層が定数倍を大きく左右します。まずO記法で桁の当たりを付け、疑わしい箇所は実データで計測する — 理論と計測の両輪で使うのが、この語彙の正しい運用です。