計算量とO記法
Big O Notation ・ けいさんりょうとオーきほう
入力が増えたとき処理時間や使用メモリがどう伸びるかを表す記法。性能の共通言語。
✦ 30秒で試す — 航海同じマシン、同じデータで、20秒と12日の差がつく100万件では、どちらが速く終わる？予想してみる概要
計算量とは、アルゴリズムが入力の大きさに応じてどれだけの時間（時間計算量）やメモリ（空間計算量）を必要とするかの尺度です。そしてO記法（ビッグ・オー記法）は、それを「入力 n が増えたときの伸び方」だけに注目して表す記法です。O(n) なら入力に比例して伸びる、O(n²) なら入力の2乗で伸びる、と読みます。
直感的には「入力を10倍にしたらどうなるか」を一言で答えるための言葉です。O(n) の処理は10倍遅くなり、O(n²) の処理は100倍遅くなり、O(log n) の処理はほとんど変わりません。開発中の手元データ1,000件では全部一瞬でも、本番の100万件でこの差は「一瞬」と「何日も」の差になって現れます。マシンや言語が変わっても伸び方の性質は変わらないため、O記法はエンジニアが性能を議論するときの共通言語になっています。
なぜ生まれたか
アルゴリズムの速さを比べたいとき、素朴な方法は実際に動かして秒数を測ることです。しかし実測値はマシンの速度、言語、コンパイラの最適化、たまたま与えたデータに左右され、「このソートは0.3秒だった」という数字からは手順そのものの良し悪しが読み取れません。しかも一番知りたいのは「まだ経験していない大きさの入力でどうなるか」であり、それは測定では原理的に分かりません。
そこで計算機科学者たちは、数学にあった「関数の漸近的な振る舞い」を表す記法を借りてきました。O記法そのものは、19世紀末にドイツの数学者バッハマンが数論の本で使い（1894年）、ランダウが広めたもので（1909年）、もとは「誤差の項がこの程度に収まる」ことを書くための道具でした。これをアルゴリズムの解析に持ち込み、定着させたのが Knuth です。1968年に刊行が始まった『The Art of Computer Programming』で手順の実行回数を系統立てて解析し、1976年の論考では上界の O・下界の Ω・両方からの Θ の使い分けを提案しました。
実行環境に依存する定数倍や、n が大きくなれば効かなくなる下位の項を思い切って捨て、「n を大きくしていったときの支配的な伸び方」だけを残す。この割り切りによって、実装の詳細から独立に手順そのものを比較でき、将来のデータ量に対する予言が可能になりました。以来、計算量はアルゴリズムの「仕様」の一部として語られています。
詳細
代表的なオーダーと成長曲線
よく登場するオーダーは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段違うだけで「待てる」と「待てない」の境界を越えてしまいます。
この差は、作業量を「形」として並べると腑に落ちます。O(n) の仕事は1列、O(n log n) は log n 段の帯、O(n²) は n × n の正方形です。n を増やすと、1列は横に伸びるだけなのに、正方形は縦にも横にも広がります。下の部品で n を動かし、同じ1マスの大きさのまま形がどう育つかを確かめてください。
O(n) の列の右端のつまみを右へドラッグして、n を増やしてみてください。1マスが1回の操作です。いまは n = 4。
定数倍を無視するのはなぜか
O記法では「3n + 50」も「n」もまとめて O(n) と書きます。乱暴に見えますが、これは意図的な設計です。定数の3や50は、マシンの速さや実装の丁寧さで何倍も変わる「環境の事情」であり、手順そのものの性質ではありません。一方で n と n² の差は、どんな環境でも n を大きくすれば必ず逆転不能になる「手順の性質」です。O記法は後者だけを抽出するレンズなのです。
時間だけでなくメモリにも同じ記法を使い、「時間を買うために空間を払う」（インデックスやキャッシュの維持）というトレードオフも計算量の言葉で表現できます。
O・Ω・Θ と、最悪・平均・償却
正確には、O(f(n)) は「どれだけ悪くても f(n) の定数倍以下に収まる」という上界です。だから線形探索を O(n²) と書いても嘘ではありません（上界としては緩いだけ）。これに対し Ω(f(n)) は「少なくとも f(n) の定数倍はかかる」という下界、Θ(f(n)) は上界と下界が一致した「ちょうどこの伸び方」を表します。比較に基づくソートはどう工夫しても Ω(n log n) 回の比較が必要、という有名な結果は下界の主張です。実務の会話で「O(n)」と言うときは、たいてい Θ の意味（ぴったりこの伸び方）で使われています。
もう1つの区別は、どの入力を基準にするかです。通常は「最悪の場合」を基準に語ります。平均は速いが特定の入力で破綻する手順（素朴なクイックソートは、すでに並んだ入力で O(n²) になる）もあるため、保証として最悪計算量を押さえておくのが実務的です。
ただし、最悪だけを見ると実態を見誤る操作もあります。代表が動的配列（JavaScript の配列や Python の list）への末尾追加です。容量が尽きると、一回り大きい領域（実装によって1.5〜2倍程度）を確保して全要素をコピーするので、その1回だけは O(n) かかります。しかし倍々で広げる場合、コピーが起きるのは容量が 1, 2, 4, 8… に達したときだけで、n 回追加したときのコピーの合計は 1 + 2 + 4 + … < 2n にしかなりません。n 回で合計 O(n) なので、1回あたりに均すと O(1) です。これを償却計算量と呼びます。
実務で効く場面 — N+1問題とネストループ
O記法がもっとも役立つのは、コードレビューで性能問題を「起こる前に」見抜くときです。典型例のひとつが ORM で起きやすい N+1問題です。一覧を1クエリで取り、各行についてループ内で関連データを1クエリずつ取ると、SQL の発行回数が n に比例して増えます。1件あたりの通信往復という大きな定数が掛かった O(n) は、データ100件の開発環境では気づかず、本番の1万件で突然火を噴きます。
もうひとつの定番が無自覚なネストループです。「配列Aの各要素について、配列Bに含まれるか線形探索する」コードは O(n²) で、Bをデータ構造のハッシュ表（集合）に変えるだけで O(n) に落ちます。ループの中で呼んでいる関数が、見えないところでもう1つのループ（includes、indexOf、リストの in）を回していないかを疑うのが、レビューでのコツです。データベースのインデックスが効くのも同じ理屈で、全行走査 O(n) を B木の探索 O(log n) に置き換えています。
落とし穴 — 小さい n では定数倍が支配する
一方で、O記法を万能の物差しと思い込むのも危険です。捨てたはずの定数倍は、n が小さいうちはむしろ支配的だからです。要素数十数個なら、O(n²) の挿入ソートのほうがオーバーヘッドの大きい O(n log n) のソートより速いことは珍しくなく、実際に多くの標準ライブラリは小さな区間で挿入ソートに切り替えるハイブリッド実装になっています。また、配列の連続アクセスは CPUキャッシュに乗って理論値以上に速く、ポインタをたどる連結リストは同じ O(n) でも大幅に遅い、というようにメモリ階層が定数倍を大きく左右します。まずO記法で桁の当たりを付け、疑わしい箇所は実データで計測する — 理論と計測の両輪で使うのが、この語彙の正しい運用です。
試問
データの件数を n としたとき、処理の手間が n に対してどう伸びるかを表すのが O 記法です。O(1) は件数によらず一定、O(log n) は n が倍になるたびに1回増えるだけ、O(n) は件数に比例、O(n²) は件数×件数に比例します。8つの処理が並んでいます。
8つの処理を、手間の伸び方（O(1)・O(log n)・O(n)・O(n²)）の箱へ仕分けよ
項目を選んでから、入れる箱を選びます