Rui Software100万件から1人を探すのに、20回で足りる：手間の「増え方」を測る計算量の話【第5回】
100万件の名簿から1人を探すとき、先頭から順に照合すれば平均50万回かかります。ところが並べ替えておけば、20回で見つかります。差は2万5,000倍です。この記事を読み終えると、
O(n)やO(log n)が何を約束して何を約束していないのかを説明でき、データ構造を「速いか遅いか」ではなく「手間がどう増えるか」で選べるようになります。ジュニアエンジニア向けコンピュータサイエンス入門シリーズ（全8回）の第5回です。
🎯 テーマの主役：「計算量」——手間の増え方を測る物差し
今回の主役は計算量（computational complexity）、とくにオーダー記法（O記法）です。一言で言えば、データが増えたときに、手間がどう増えるかを表す物差しです。
日常の例えで言うなら、図書館で本を探す方法の違いです。方法は3つあります。第一に、入口の棚から順に全部見ていく。1冊見つけるのに平均で蔵書の半分を確認します。第二に、背表紙の番号で棚を絞る。蔵書が番号順に並んでいれば、真ん中を見て「求める番号は右か左か」を判断し、毎回候補を半分に減らせます。第三に、目録（索引）を見る。著者名や件名から棚の番号が直接分かります。
第一の方法は、蔵書が100冊なら50冊見れば済みます。ところが100万冊なら50万冊です。「蔵書が増えたら、手間はどう増えるか」という問いに答えるのが計算量であり、この3つの方法はそれぞれ違う答えを持っています。
第3回で「メモリの速度の階段」を、第4回で「OSが資源を配る仕組み」を扱いました。性能を語るには、実は2本の軸が要ります。1本目は「1回のアクセスに何サイクルかかるか」（第3回）。2本目が今回の「何回アクセスするか」です。片方だけでは「なぜ遅いのか」を説明しきれません。ようやく両輪が揃います。
この物差しを手に入れると、次の4つができるようになります。第一に、コードを書く前に「この書き方だとデータが10倍になったら何倍遅くなるか」を見積もれること。第二に、O(n) や O(n log n) という表記を、約束と限界の両方まで含めて読めること。第三に、「配列とハッシュテーブルのどちらを使うか」を理由をつけて選べること。第四に、レビューで「この処理は何回ループするか」を聞かれて答えられることです。
3つの方法を、蔵書数ごとの手間の回数で並べてみます。ここが計算量の核心です。同じ「探す」という作業でも、増え方の形がまったく違います。
| 蔵書数 | ① 順に探す（線形探索） | ② 半分に絞る（二分探索） | 差の倍率 |
|---|---|---|---|
| 10冊 | 平均5回 | 4回 | 約1.3倍 |
| 100冊 | 平均50回 | 7回 | 約7倍 |
| 1,000冊 | 平均500回 | 10回 | 約50倍 |
| 1万冊 | 平均5,000回 | 14回 | 約360倍 |
| 100万冊 | 平均50万回 | 20回 | 約2万5,000倍 |
| 10億冊 | 平均5億回 | 30回 | 約1,700万倍 |
表の左端と右端を見比べてください。蔵書が10冊のときは、ほとんど差がありません。差が生まれるのは、データが増えてからです。これが、計算量を学ぶ理由そのものです。
😓 動機：「遅い」と言われて、マシンを速くする話をしてしまう
ジュニアエンジニアが性能の相談を受けたとき、最初に思いつくのは「マシンを強化する」です。インスタンスのスペックを上げる、CPUを増やす。しかし第3回で見たとおり、ハードウェアで得られる改善は数倍の世界です。計算量を変えると、数万倍動きます。
よくある症状を4つ挙げます。ひとつ目は、データが増えるほど遅くなる。テスト環境では一瞬だったのに、本番では数十秒。ふたつ目は、インスタンスを倍にしたのに速くならない。みっつ目は、同じことをしている2つのコードで、片方が100倍遅い。よっつ目は、レビューで「これはO(n²)では？」と言われて、何を指しているか分からない。
これらはすべて、「手間がどう増えるか」を測っていないことから来ます。「今のデータ量で動くか」ではなく「データが10倍になったらどうなるか」を問う習慣が抜けているのです。
そして、この視点はAI時代に重要性が上がっています。AIが生成するコードは、データ量が少ないうちは快適に動きます。AIは「動くコード」を返すのが得意で、「増えても壊れないコード」を保証してはくれません。書かれたコードが二重ループなのか、ハッシュを使っているのかを見抜くのは、人間の仕事として残ります。
🧪 仮説：性能を決めるのは「1回の速さ」だけでなく「回数の増え方」である
仮説を立てます。コードの速度は、1回あたりの処理時間と、処理の回数の積で決まる。そして回数の増え方は、アルゴリズムとデータ構造の選び方で変えられる。
この仮説を支持する観察が3つあります。第一に、100万件の探索は、線形探索で平均50万回、二分探索で20回です。1回あたりの速度が同じでも、2万5,000倍の差が出ます。第二に、インスタンスのスペックを2倍にしても、O(n²)の処理は2倍にしかなりません（しかもCPUを増やしてもループは1本のままなので、実際には伸びないことも多い）。第三に、アルゴリズムを変えずにデータ構造だけ変える（配列をハッシュテーブルにする）だけで、計算量のクラスが変わることがあります。
ここから実務的な指針が出ます。「この処理は何回まわるか」を、データ量の関数として言えるかどうか。言えれば、性能の問題はほぼ見通せます。言えなければ、まだ測る準備ができていないということです。
🔬 検証①：探し方の違いを、実際に数えてみる
まず、先ほどの表の数字がどこから来るのかを確かめます。
線形探索は単純です。先頭から順に照合し、見つかったら止めます。100万件で目的のデータが真ん中にあれば50万回、最後にあれば100万回の照合が必要です。「何回照合するか」は、データの件数に比例して増えます。これを O(n) と書きます。
二分探索はどうでしょうか。並びが番号順になっていることが前提です。真ん中の1件を見て、求める値より大きいか小さいかを判定します。小さいと分かれば、右半分は全部候補から外れます。1回の照合で候補が半分になるので、候補が1件になるまでの回数は「何回2で割れるか」、つまり2の何乗で n を超えるかです。
具体的に数えます。2の10乗は1,024ですから、1,000件なら10回で足ります。2の20乗は1,048,576ですから、100万件でも20回です。件数が倍になっても、必要な回数は1回しか増えません。これを O(log n) と書きます。
ここで大事なのは、二分探索が使える条件があることです。候補が番号順に並んでいる必要があります。並んでいないデータに対しては、この方法は使えません。速さには前提が付いてくる。これが計算量を語るときの基本作法です。
ちなみに、この「半分に絞る」アルゴリズムは単純に見えて、正しく書くのが意外と難しいことで知られています。1962年ごろには正しい実装が共有されていたとされますが、2006年には Java の標準ライブラリの二分探索とマージソートに、中央値の計算で整数がオーバーフローするバグがあることが指摘されました。第2回で扱った「型の範囲」の話が、まさにここに現れています。アルゴリズムと型の知識は別物ではなく、つながっているのです。
🔬 検証②：O記法が約束すること・約束しないこと
ここで、O(n) や O(log n) という表記の意味を正確に押さえます。この記法は、誤解されやすいからです。
O(f(n)) は、「n が十分大きいとき、手間は f(n) の定数倍を超えない」という約束です。ここで大事なのは2点です。第一に、定数倍は切り捨てます。100回のループと3回のループは、どちらも O(n) です。第二に、小さい項も切り捨てます。2n + 500 は、n が十分大きければ O(n) です。
なぜ定数を落とすのか。それは、O記法が「増え方の形」を語る道具だからです。ハードウェアが世代ごとに速くなっても、増え方の形は変わりません。定数倍の差は、機械の性能が上がれば全部同じ比率で縮みます。しかし「n が10倍になったら手間が何倍になるか」という形は、機械が変わってもそのままです。長く効く情報だけを残すと、O記法になるのです。
| 記法 | 意味 | 何を語るか | 使う場面 |
|---|---|---|---|
O(f(n)) | 上界。「これより悪くはならない」 | 最悪の場合の保証 | 実務でいちばんよく使う。安全側の見積もり |
Ω(f(n)) | 下界。「これより良くはならない」 | 原理的な限界 | 「これ以上速くできない」ことの証明 |
Θ(f(n)) | 上下から挟める。「ちょうどこの形」 | 厳密な増え方 | 理論的な議論。実務ではあまり使わない |
O記法が約束しないことは3つあります。第一に、「何秒か」は語りません。O(n) の処理が1秒なのか1時間なのかは、定数次第です。第二に、定数倍の優劣は語りません。O(n) どうしの比較では、定数が10倍違えば10倍の差が出ます。第三に、n が小さいときの振る舞いは語りません。O記法は「n が十分大きいとき」の話です。
この3つ目が、実務で最も効いてきます。要素数が数十件なら、O(n) の線形探索が O(log n) の二分探索より速いことが多いのです。理由は第3回で扱ったメモリ階層にあります。線形探索はデータを前から順に読むので、キャッシュの空間的局所性がよく効きます。一方の二分探索は、毎回候補の真ん中に飛ぶので、アクセスのたびにキャッシュミスを起こしやすい。分岐の予測も外れやすい。計算量のクラスが良くても、定数とキャッシュの事情で負けることがある。これが、O記法を「絶対の答え」として使ってはいけない理由です。
だから実務の順番はこうなります。 まず「データ量の見積もり」を立てる。n が小さいうちは素直な実装でよい。n が大きくなりうる場所だけ、計算量のクラスを意識する。そして必ず計測する。O記法は当たりを付ける道具であって、答えを出す道具ではありません。
🔬 検証③：成長のクラスを並べて見る
よく出会う計算量を、増え方の形で並べます。ここで注目してほしいのは、どのクラスが「使える」で、どのクラスが「破綻する」かです。
| 計算量 | n=10 | n=100 | n=1,000 | n=100万 | どんな処理か |
|---|---|---|---|---|---|
O(1) | 1 | 1 | 1 | 1 | ハッシュテーブルの参照、配列の添字アクセス |
O(log n) | 約3 | 約7 | 10 | 20 | 二分探索、B-treeの検索 |
O(n) | 10 | 100 | 1,000 | 100万 | 全件走査、線形探索 |
O(n log n) | 約33 | 約660 | 約1万 | 約2,000万 | マージソート、Timsort |
O(n²) | 100 | 1万 | 100万 | 1兆 | 素朴な二重ループ、バブルソート |
O(2^n) | 1,024 | 約1.3×10の30乗 | 天文学的 | 天文学的 | 全組み合わせの総当たり |
この表の読み方は単純です。n を10倍にしたとき、手間が何倍になるかを数える。O(n) なら10倍、O(n log n) は10倍より少し多く、O(n²) は100倍。O(n²) の行を見てください。n が1,000で100万回、100万で1兆回です。1回1ナノ秒で実行できたとしても、1兆回は約17分かかります。そして、サーバーのCPU時間は金銭に直結します。
実務での目安として、O(n²) は「n が数百〜数千までなら耐えるが、1万を超えると危ない」と考えておくと扱いやすいです。n=10,000 なら1億回、1ナノ秒で0.1秒。n=100,000 なら100億回で10秒。境界線はこのあたりにあります。
🔬 検証④：整列は「先払いの投資」である
ここまで「探す」話をしてきましたが、探す前に並べる手間を無視できません。整列（ソート）には O(n log n) かかります。これは O(n) より重い処理です。では、なぜ整列するのでしょうか。
理由は、整列すると、その後の作業が安くなるからです。整列したデータには二分探索が使え、重複の検出も隣どうしを比べるだけで済み、範囲の取り出しも速くなります。整列は、後で使うための前払いなのです。
では、前払いが得になるのはいつか。100万件で計算してみます。整列の手間は「100万 × 20 ＝ 2,000万回」の比較です。線形探索1回の手間は平均50万回の比較です。すると、2,000万 ÷ 50万 ＝ 40回。つまり同じデータを40回以上探すなら、先に並べたほうが得になります。1回しか探さないなら、並べるほうが損です。
ここから実務的な判断基準が出ます。整列するかどうかは、「読む回数と書く回数の比」で決める。読み取りが多く更新が少ないなら、整列したデータが有利です。逆に、1件追加するたびに並び直す必要があるなら、整列は負担になります。
そして、ここには第4回で扱った発想と同じ形があります。第4回では「ファイルを開くのは番号札を取ること」でした。今回は「索引を持つのは、後で速く引くための前払い」です。速さの代金は、別の場所で払う。この原則は、計算量の話のいたるところに現れます。
🔬 検証⑤：データ構造は「何をしたいか」で選ぶ
ここまでの話を、データ構造の選択に落とします。「速いデータ構造」というものは存在しません。あるのは「その操作が速いデータ構造」です。
| データ構造 | 添字で取る | 値で探す | 追加 | 順番に読む |
|---|---|---|---|---|
| 配列 | O(1) | O(n) | 末尾は O(1)、途中は O(n) | 得意 |
| 整列済み配列 | O(1) | O(log n) | O(n)（並びを保つため） | 得意（順序付き） |
| 連結リスト | O(n) | O(n) | 位置が分かっていれば O(1) | 得意だがキャッシュに弱い |
| ハッシュテーブル | — | 平均 O(1)、最悪 O(n) | 平均 O(1) | 不得意（順序が保たれない） |
| 木（B-tree・平衡木） | — | O(log n) | O(log n) | 得意（ソート済みの順に読める） |
| ヒープ | — | O(n) | O(log n) | 先頭（最大・最小）だけ O(1) |
この表の読み方を、3つの質問に変換しておきます。第一に「順番は必要か」。順番が要らないなら、ハッシュテーブルが第一候補です。第二に「決まった順に取り出す必要があるか」。範囲検索やソート済みの出力が要るなら、木か整列済み配列です。第三に「真ん中の要素に飛びたいか」。添字で直接アクセスしたいなら配列です。
そして、平均と最悪の違いに注意してください。ハッシュテーブルの O(1) は平均です。すべてのキーが同じ値に集まると、O(n) に落ちます。これは理論上の心配ではありません。2011年ごろ、複数の言語のハッシュテーブル実装で、意図的に衝突を起こす入力によって計算量が著しく悪化する問題が報告され、各実装に対策が入りました。攻撃者が入力を作れる場面では、最悪計算量が攻撃対象になるのです。OWASPもこの種の攻撃（アルゴリズム複雑性攻撃）をサービス妨害の一形態として挙げています。
計算量は性能の話であると同時に、安全の話でもある。これが、この記事でいちばん持ち帰ってほしい視点の1つです。
📊 結果：症状から打ち手を引く
ここまでの内容を、現場で使える形にまとめます。「計算量のクラスが変わったか」で判断するのがポイントです。定数倍の改善は、機械の強化で代替できます。クラスの改善は、代替できません。
| 症状 | 疑う計算量 | 打ち手 | 変わること |
|---|---|---|---|
| データ量に比例して遅くなる | O(n) または O(n²) | ハッシュや索引を導入する | O(n) → O(1) や O(log n) |
| データが10倍で100倍遅くなる | O(n²) の二重ループ | ループの内側を表引き・集合・整列に置き換える | O(n²) → O(n) や O(n log n) |
| ループの中で外部に問い合わせている | ネットワーク往復が O(n) 回 | まとめて1回で取る | 往復回数が n 回 → 1回 |
| リストへの存在確認が遅い | リストの検索は O(n) | 集合や辞書に変える | O(n) → 平均 O(1) |
| 文字列をループで連結すると遅い | 連結の繰り返しで O(n²) | 配列に貯めて最後に1回で結合する | O(n²) → O(n) |
| 毎回並べ替えている | 整列の O(n log n) を繰り返す | 一度だけ並べて再利用する、または索引を持つ | 繰り返しが1回に減る |
| 同じ計算を何度もしている | 再計算の積み重ね | 結果を覚えておく（メモ化） | 指数関数的 → 多項式 |
特に7行目「メモ化」は効果が劇的な例があります。素朴な再帰でフィボナッチ数を計算すると、呼び出し回数は指数的に増えます。ところが計算結果を記録しておくと、各 n について1回計算するだけになります。同じ処理を書いているのに、計算量のクラスが変わった。これは「計算を速くする」のではなく「同じ計算をしない」という発想です。
💭 考察：計算量は「未来の請求書」である
ここまでの話を一段深く掘ります。計算量の本質は、「今の速度」ではなく「増えたときの倍率」を語るという点にあります。
この見方をすると、O(n²) は将来の負債です。今は n が小さいから動いています。しかし n が10倍になれば手間は100倍、100倍になれば1万倍になります。今のデータ量で測った性能は、未来の性能を保証しません。これは、第2回で「型を選ぶとは将来の壊れ方を選ぶこと」と書いたのと同じ構造です。データ構造を選ぶとは、将来の手間の増え方を選ぶことなのです。
もう1つ、深い見方があります。計算量を下げるとは、多くの場合「データの形を変えること」だということです。線形探索を二分探索にするには、データを並べます。ハッシュで引くには、データにハッシュを付けて配置します。索引で引くには、索引という別のデータを作ります。アルゴリズムの改善は、しばしば「元のデータをそのままに、計算を工夫する」のではなく、「データの持ち方を変える」ことで実現します。
これは、第3回で「配列と連結リストの違いはメモリ往復回数だ」と書いたのと同じ方向の話です。性能の問題は、計算ではなくデータの配置の問題であることが多い。この見方は、第7回で扱うデータベースの索引の理解にも直結します。
そして3つ目に、計算量は「測る前の当たり」をつける道具だということです。第3回で「まず計測する」と書きました。今回の話はそれと矛盾しません。当たりを付けてから計測するから、計測の回数が減る。当たりなしに計測すると、やみくもに速い場所と遅い場所を探すことになります。O記法は地図であり、計測は現地調査です。どちらも要ります。
📌 注目ポイント
この記事の核心を4点に絞ります。
第一に、性能を決めるのは「回数の増え方」です。 100万件の探索は、線形で平均50万回、二分で20回。差は2万5,000倍です。ハードウェアを強化して得られる数倍とは桁が違います。
第二に、O記法は「増え方の形」だけを語ります。 定数も、小さい n での振る舞いも語りません。だから要素数が数十件なら、クラスが悪い方法が勝つこともあります。O記法は当たりを付ける道具であり、答えではありません。
第三に、速さには前提と代金があります。 二分探索には整列済みという前提が要ります。索引には作る手間と更新の手間がかかります。速さの代金は、必ず別の場所で払います。
第四に、計算量は安全の話でもあります。 ハッシュの最悪計算量は攻撃対象になりえます。入力を作れる立場の攻撃者にとって、アルゴリズムの弱点は侵入経路です。
💡 活用事例：ディスクの都合が生んだB-tree
ここまでの話が現実でどう使われているかを見ます。データベースの索引です。
索引に使われる B-tree は、1972年に Boeing Scientific Research Laboratories の Rudolf Bayer と Edward M. McCreight が発表したデータ構造です（Bが何の略かは明言されておらず、諸説あります）。当時の課題は、ディスク上にある大量のデータを、いかに少ない読み取り回数で探すかでした。
当時の索引構造（二分探索木）は、1つの節点が2つの子しか持てません。100万件を収めると、木の深さは約20段になります。1段たどるたびにディスクへ行くなら、20回のディスクアクセスが必要です。第3回で見たとおり、ディスクはメモリより桁違いに遅い。これは耐えられません。
B-treeの解決策は単純で強力でした。1つの節点に、多数のキーと多数の子を持たせる。ディスクから読む単位（ページ、典型的には数KB）を丸ごと使って、数百のキーを詰め込みます。
数字で確認します。1つの節点に100の分岐があるとします。根から1回たどると、候補は100件に絞られます。2回で1万件。3回で100万件。つまり100万件のテーブルでも、根を合わせて3回程度のページ読みで目的の行に届きます。実際のデータベースではページサイズやキーの大きさで分岐係数は変わりますが、考え方は同じです。
| 構造 | 1節点の分岐 | 100万件の深さ | ディスク読みの回数 |
|---|---|---|---|
| 二分探索木 | 2 | 約20段 | 約20回 |
| B-tree（分岐100） | 100 | 3段 | 約3回 |
| B-tree（分岐256） | 256 | 3段 | 約3回 |
さらに、B-treeのもう1つの利点はインデックスが整列済みのまま保たれることです。範囲の取り出し（「100以上200未満」のような条件）や順番どおりの出力が、そのまま得意になります。第3回で「連続したデータはまとめて取れる」と書きましたが、B-treeはキーを節点にまとめて詰め込むことで、ディスクの読み取り単位そのものを活かしています。ハードウェアの都合がアルゴリズムの形を決めた、よい例です。
この事例からジュニアエンジニアが持ち帰れる教訓は3つあります。第一に、計算量の話は「抽象的な理論」ではなく、ハードウェアの制約から生まれます。第二に、同じ O(log n) でも、1回のアクセスに何が起きるかで意味が変わります（20回のディスク読みと3回のディスク読みは別物です）。第三に、50年以上前の設計が今も現役です。第1回で「下の階ほど長寿」と書きましたが、B-treeはその好例です。
✅ 要点まとめ
読み終えたあなたが持ち帰るべきエッセンスを、6つに圧縮します。
- 計算量は「データが増えたときに手間がどう増えるか」を測る物差し。今の速度ではなく増え方を語る
- 100万件の探索は、線形で平均50万回、二分で20回。差は2万5,000倍で、ハードウェアの改善とは桁が違う
O(...)は上界の約束。定数も、小さい n の振る舞いも語らない。だから小さいデータではクラスが悪い方法が勝つこともある- 速さには前提（整列済みなど）と代金（作る手間・更新の手間）が付く。速さの代金は別の場所で払う
- 整列は先払いの投資。100万件なら、同じデータを40回以上探すなら元が取れる
- データ構造に「速い・遅い」はない。あるのは「その操作が速い・遅い」。順番・範囲・添字アクセスのどれが要るかで選ぶ
🚀 取り込み方
「明日から使うには何をすればいいか」を、期間ごとに分けて示します。
今日（5分でできること）
自分の環境で、線形探索と二分探索の差を実際に見てください。数字を目で見ると、この記事の内容が記憶に残ります。
import time
import bisect
n = 1_000_000
data = list(range(n)) # ソート済みの配列
target = n - 1 # いちばん最後＝線形探索が最も苦手なケース
t0 = time.perf_counter()
for x in data: # 線形探索
if x == target:
break
t1 = time.perf_counter()
t2 = time.perf_counter()
bisect.bisect_left(data, target) # 二分探索
t3 = time.perf_counter()
print(f"線形探索: {(t1 - t0) * 1000:.2f}ms")
print(f"二分探索: {(t3 - t2) * 1000:.4f}ms")
手元の環境では、線形探索がミリ秒単位、二分探索がマイクロ秒単位になるはずです。倍率は環境で変わりますが、「同じ配列を同じ言語で探しているのに桁が違う」こと自体がこの記事の主張です。
今週（小さく試す）
担当コードから、次の4つを探してください。(1) ループの内側にループがある箇所、(2) ループの内側で外部に問い合わせている箇所、(3) リストに対して in で存在確認している箇所、(4) ループの中で文字列を連結している箇所。見つけたら、すぐ直さずに「n が10倍になったら何倍になるか」を1行書いてください。これが、この記事で身につけた見積もりの練習になります。
今月（業務に組み込む）
チームのレビュー観点に、次の2つの質問を足せないか提案してみてください。「このループは最大で何回まわるか」と、「データ量が10倍になったらこの処理はどうなるか」。どちらもコードを読むだけで答えられる質問で、性能問題の多くを事前に防げます。アルゴリズムの話は抽象的になりがちなので、この2つの質問という形にすると、チームの共通言語にしやすくなります。
🔥 ハマりポイント
つまずきやすい5つの落とし穴を、「〜と思いがちだが、実は〜」の形で整理します。
その1：O(log n) のほうが常に速いと思いがちだが、実は小さいデータでは逆転する
症状は、二分探索に書き換えたら遅くなったこと。原因は、二分探索が毎回違う場所に飛ぶため、キャッシュミスと分岐予測の失敗が増えること（第3回のメモリ階層の話です）。対処法は、要素数が数十〜100程度なら素直な線形探索のままでよいと覚えることです。O記法は「n が十分大きいとき」の話であって、常に正しいわけではありません。
その2：最悪計算量を見ないと思いがちだが、実は攻撃対象になる
症状は、特定の入力でだけ処理が極端に遅くなること。原因は、ハッシュの衝突などで平均 O(1) が最悪 O(n) に落ちること。対処法は、外部から入力のキーを指定できる場面では最悪計算量を確認することです。ライブラリは多くの場合すでに対策済みですが、古いバージョンや自前実装は確認が必要です。実際、検証⑤で触れたように、意図的に衝突を起こす入力でサービスを止める攻撃は現実に報告されています。「平均的に速い」は「どんな入力でも安全」ではありません。
その3：データ構造を変えれば自動的に速くなると思いがちだが、実は操作との組み合わせで決まる
症状は、配列をハッシュテーブルに変えたら別の処理が遅くなったこと。原因は、ハッシュテーブルが順序を保たないため、範囲検索や順番どおりの出力が苦手なこと。対処法は、「どの操作を何回するか」を先に数えることです。読み取りが多いのか、追加が多いのか、範囲で取りたいのか。この3つで答えが変わります。
その4：定数倍の改善を積み上げれば何とかなると思いがちだが、実はクラスの差には勝てない
症状は、細かい最適化を重ねたのに改善が数%にとどまること。原因は、ボトルネックが O(n²) のクラスにあること。対処法は、まず「どのクラスか」を判定することです。O(n²) を2倍にチューニングしても、n が2倍になれば振り出しに戻ります。クラスを変えるのが先、定数を詰めるのは後です。
その5：一度速くしたら、その先もずっと速いと思いがちだが、実はデータが増えると崩れる
症状は、半年後に「昔は速かったのに」と言われること。原因は、データ量が増えて O(n²) の部分が効き始めたこと。対処法は、データ量の増加を監視項目に入れることです。性能は「速い・遅い」ではなく「どのデータ量まで耐えるか」で捉えると、いつ崩れるかを予測できます。
🔄 比較：クラスを変える技術と、定数を詰める技術
最後に、改善手段を「クラスが変わるか」で分類します。効果の持続性がまったく違うところがポイントです。
| 手段 | 何が変わるか | 効果の持続性 | コスト |
|---|---|---|---|
| 機械のスペックを上げる | 定数（数倍） | データが増えると効果が薄れる | 金銭。実装は不要 |
| コードを微修正する | 定数（数%〜数十%） | 同上 | 小さい。ただし可読性を犠牲にしやすい |
| データ構造を変える | クラス（O(n) → O(1) など） | データが増えても崩れにくい | 中程度。呼び出し側の修正が必要 |
| アルゴリズムを変える | クラス（O(n²) → O(n log n) など） | 同上 | 大きい。設計の見直しが必要 |
| 計算しない（結果を覚える） | クラス（指数的 → 多項式） | 崩れにくいが、記憶領域と整合性の管理が要る | 中程度。無効化の設計が必要 |
この表から持ち帰ってほしいのは、「上2行は借金、下3行は投資」という区別です。機械とマイクロ最適化は、データが増えれば効力を失います。データ構造とアルゴリズムの変更は、データが増えても効き続けます。そして一番下の「覚えておく」は、第3回で扱ったキャッシュと同じ発想であり、「いつ捨てるか」という問題が必ず付いてきます。
📅 今後の展望
計算量の話は、これからどうなるのでしょうか。方向性は3つ考えられます。
第一に、クラスの差は埋まらないということです。ハードウェアがどれだけ速くなっても、O(n²) と O(n log n) の差はデータ量とともに開き続けます。過去数十年、この関係は変わりませんでした。そして、扱うデータ量は増え続けています。n が大きくなるほど、クラスの選択の重みは増します。
第二に、AIが書いたコードの計算量を見抜く仕事が増える方向です。AIは「動くコード」を高速に返しますが、そのコードが O(n²) なのか O(n log n) なのかを保証してはくれません。生成されたコードを読んでクラスを判定できる人が、性能の議論で発言権を持ちます。これは第1回で「評価する側に回る人が増えた」と書いた話の、具体的な中身です。
第三に、「計算しない」という選択肢が広がる方向です。結果を覚えておく、近似で済ませる、確率的な手法を使う。データが巨大になるほど、厳密な答えを出すより「十分に良い答えを速く出す」ほうが価値を持つ場面が増えています。ただし、これは正確さと速さのトレードオフを意識的に選ぶということであり、第2回で扱った「誤差を許容するかどうか」の判断と同じ構造です。
なお、O 記法の理論そのものは、1970年代に体系化されたものです。50年たっても使われ続けているのは、「増え方の形」という問いが普遍的だからです。この安定性が、計算量の知識が長く効く理由です。
🗺️ 次回予告：なぜ遠くのサーバーに届くのか
第5回では「何回アクセスするか」という軸を手に入れました。第3回の「1回に何サイクルかかるか」と合わせて、性能を語る両輪が揃ったことになります。
第6回は ネットワーク を扱います。世界中のどこかにあるサーバーに、なぜ私たちのリクエストが届くのか。途中で誰かが入れ替えたり盗み見たりしないのはなぜか。ping で見える往復時間が、その間に何を意味しているのか。そして、遅さはどこで生まれるのか。
第5回で扱った「ネットワーク往復が O(n) 回」というアンチパターンは、第6回の理解で具体的な秒数に換算できるようになります。第6回は、性能の話と遠くの世界をつなぐ回になります。
まとめ
この記事を読んだあなたは、遅いコードを見たときに「どこを速くしよう」ではなく「何回まわっているのか」を先に考えるようになります。そして O(n²) を見つけたとき、定数を詰めるのではなく、クラスを変える方法を探すようになります。
そして「100万件から1人を探すのに20回で足りる」という事実が、魔法ではなく並べ方の工夫の結果だと説明できるようになります。速さには前提があり、代金があります。その代金をどこで払うかを選ぶことが、設計という仕事です。計算量は、その選択を数字で語るための言葉です。
参考文献
- Donald E. Knuth, “The Art of Computer Programming, Volume 3: Sorting and Searching”（二分探索と整列の原典的解説） — https://www-cs-faculty.stanford.edu/~knuth/taocp.html
- Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein, “Introduction to Algorithms” (4th ed.), MIT Press — https://mitpress.mit.edu/9780262046305/introduction-to-algorithms/
- Robert Sedgewick, Kevin Wayne, “Algorithms” (4th ed.), Addison-Wesley（無料の講義資料と可視化あり） — https://algs4.cs.princeton.edu/
- Jon Bentley, “Programming Pearls” (2nd ed.), Addison-Wesley（二分探索を正しく書く難しさの有名な議論を含む） — https://www.oreilly.com/library/view/programming-pearls-2nd/0201657880/
- Joshua Bloch, “Extra, Extra - Read All About It: Nearly All Binary Searches and Mergesorts are Broken”, Google Research Blog, 2006 — https://research.google/blog/extra-extra-read-all-about-it-nearly-all-binary-searches-and-mergesorts-are-broken/
- Rudolf Bayer, Edward M. McCreight, “Organization and Maintenance of Large Ordered Indexes”, Acta Informatica, 1972（B-treeの原論文） — https://link.springer.com/article/10.1007/BF00288683
- Douglas Comer, “The Ubiquitous B-Tree”, ACM Computing Surveys, 1979 — https://dl.acm.org/doi/10.1145/356770.356776
- CPython, “Objects/listsort.txt”（Timsortの設計メモ。小さい区間で挿入ソートに切り替える理由が書かれている） — https://github.com/python/cpython/blob/main/Objects/listsort.txt
- Python Software Foundation, “TimeComplexity”（Python Wiki。操作ごとの平均計算量の一覧） — https://wiki.python.org/moin/TimeComplexity
- PostgreSQL Global Development Group, “PostgreSQL Documentation: Indexes” — https://www.postgresql.org/docs/current/indexes.html
- Markus Winand, “Use The Index, Luke!”（SQLの索引設計を実例で解説するサイト） — https://use-the-index-luke.com/
- OWASP, “Denial of Service Cheat Sheet”（アルゴリズム複雑性攻撃の対策） — https://cheatsheetseries.owasp.org/cheatsheets/Denial_of_Service_Cheat_Sheet.html
- Alfred V. Aho, John E. Hopcroft, Jeffrey D. Ullman, “The Design and Analysis of Computer Algorithms”, Addison-Wesley, 1974 — https://dl.acm.org/doi/10.5555/578775
- Big-O Cheat Sheet（よく使うデータ構造と整列の計算量一覧） — https://www.bigocheatsheet.com/
- 独立行政法人情報処理推進機構（IPA）, 「基本情報技術者試験 シラバス」（アルゴリズムとプログラミング・データ構造及びアルゴリズム） — https://www.ipa.go.jp/
- ACM/IEEE-CS Joint Task Force, “Computer Science Curricula 2023 (CS2023)”（Algorithms and Complexity 領域） — https://csed.acm.org/