計算量とデータ構造

開発環境では 0.2 秒で終わっていた処理が、本番で 40 秒かかる。 よくある話です。原因はたいてい、データ量が増えた時の増え方にあります。

開発:  ユーザー 100人   → 0.2 秒
本番:  ユーザー 10万人  → 40 秒     （1000倍のデータで200倍）

この「増え方」を表すのが計算量です。 そして、増え方を決めるのがデータ構造の選び方です。

この章は、アルゴリズムの本ではありません。 業務コードで実際に踏む数パターンだけを扱います。

何を測るのか

計算量は、データの件数 n が増えた時、処理の手間がどう増えるかを表します。 実行時間そのものではありません（マシンによって変わるので）。

n 件のデータに対して、およそ何回の操作が必要か

書き方は O(n) のように書き、オーダー n と読みます。 ルールは2つだけです。

1. 定数倍は無視する — 3n + 5 も 100n も O(n)
2. 一番大きい項だけ残す — n² + 1000n は O(n²)

雑に見えますが、n が大きい時に効いてくるのはそこだけだからです。

よく出る6つ

数字で見ると、違いが実感できます。

1回の操作を 1ナノ秒としても、O(n²) の n=100万 は約17分です。 O(n log n) なら 0.02 秒。これがオーダーの差です。

データ構造の選択が計算量を決める

「探す」が O(n) か O(1) か。 実務で効くのは、ほぼこの1点です。

最も多い失敗: 配列の中を配列で探す

// O(n × m) — 退会ユーザーが1万人いると1億回の比較になる
const active = users.filter((u) => !bannedIds.includes(u.id));

includes は配列を先頭から順に見るので O(m) です。 それを全ユーザー分繰り返すので、掛け算になります。

// O(n + m) — Set は「ある/ない」を O(1) で判定できる
const banned = new Set(bannedIds);
const active = users.filter((u) => !banned.has(u.id));

Go でも同じです。

// 遅い
for _, u := range users {
    for _, id := range bannedIDs {   // ← 二重ループ
        if u.ID == id { ... }
    }
}
 
// 速い
banned := make(map[string]struct{}, len(bannedIDs))
for _, id := range bannedIDs {
    banned[id] = struct{}{}   // 値が不要なので空構造体（メモリを消費しない）
}
for _, u := range users {
    if _, ok := banned[u.ID]; ok { ... }
}

配列の先頭操作は遅い

// O(n²) — shift() は残り全要素を1つずつ前にずらす
while (queue.length > 0) {
  const item = queue.shift();
}

キューが必要なら、インデックスを進めるか、専用のデータ構造を使います。

let head = 0;
while (head < queue.length) {
  const item = queue[head++];   // O(1)
}

N+1 問題は計算量の問題

データベースの N+1 は、まさにこれです。

const posts = await db.query('SELECT * FROM posts LIMIT 100');
for (const post of posts) {
  post.author = await db.query('SELECT * FROM users WHERE id = ?', post.userId);
}
// クエリ回数: 1 + 100 = 101 回

O(n) 回のネットワーク往復が発生しています。 1回 2ms でも 100 件で 200ms、1000 件なら 2 秒です。

// 2回で済む
const posts = await db.query('SELECT * FROM posts LIMIT 100');
const ids = [...new Set(posts.map((p) => p.userId))];
const users = await db.query('SELECT * FROM users WHERE id IN (?)', ids);
const byId = new Map(users.map((u) => [u.id, u]));   // O(1) で引けるようにする
for (const post of posts) post.author = byId.get(post.userId);

メモリアクセス       約 100ナノ秒
SSD の読み取り       約 100マイクロ秒   （1000倍）
同一リージョンの RPC  約 1ミリ秒        （1万倍）
リージョン間の通信    約 100ミリ秒      （100万倍）

O(log n) — なぜ INDEX が効くのか

ソート済みのデータなら、毎回半分に絞り込めます。

100万件から探す
→ 50万 → 25万 → 12.5万 → ... → 1件
   20回で終わる（2²⁰ ≈ 100万）

これが二分探索で、O(log n) です。 100万件でも20回。これがインデックスの正体です。

データベースの INDEX は B-tree という木構造で、同じ考え方で動きます。

データベースで「INDEX が効かないケース」として挙げたもの （カラムに関数を適用する、前方一致でない LIKE）は、 すべて**「並び順を使えなくなる」から効かない**のです。

WHERE created_at >= '2026-08-01'        -- 効く（並び順で範囲を絞れる）
WHERE DATE(created_at) = '2026-08-01'   -- 効かない（関数を通すと並び順が使えない）
WHERE name LIKE 'sato%'                 -- 効く（前方一致は範囲）
WHERE name LIKE '%sato'                 -- 効かない（先頭が分からない）

メモリと時間のトレードオフ

計算を速くする最も一般的な方法は、結果を覚えておくことです。

毎回計算する       時間: 多い   メモリ: 少ない
結果を保持する     時間: 少ない  メモリ: 多い

上で Set を作ったのも、Map を作ったのも、これです。 メモリを O(n) 使う代わりに、検索を O(1) にしています。

キャッシュも同じ構造です。ただし、

早すぎる最適化はしない。ただしオーダーは別

矛盾するようですが、両立します。

O(n²) を O(n) にするのは、後から直すと設計ごと変わることがあります。 一方、「この関数を10%速くする」は、遅いと分かってからで十分です。

そして測らずに直さないでください。

# Go: ベンチマークとプロファイル
go test -bench=. -benchmem ./...
go test -bench=BenchmarkX -cpuprofile=cpu.out ./... && go tool pprof cpu.out
 
# Node: 実行時間の計測
node --prof app.js

見積もりの手順

「この処理、大丈夫か？」を判断する手順です。3ステップで足ります。

1. n は何かを特定する    （件数？ 文字数？ ユーザー数？ リクエスト数？）
2. ループの構造を見る    （入れ子になっているか、中で検索していないか）
3. n の実際の値を当てる  （今いくつ？ 1年後いくつ？）

数字で当てる

1秒間に処理できる回数は、ざっくり 1億回（10^8） と考えてください。 （言語や処理内容で数倍変わりますが、桁の見当をつけるには十分です）

□ n が 10万を超えるなら、O(n²) は成立しない
□ n が 1000 以下なら、O(n²) でも実用上は問題ない

「今は1000件だから大丈夫」で書いたコードが、 1年後に10万件になって落ちる——これが実務で最も多い形です。

□ 登録ユーザー数に比例する      → 増え続ける。O(n²) は禁止
□ 1回の注文の明細数に比例する   → 上限がある（100件など）。O(n²) でも可
□ 検索結果の件数に比例する      → 上限を設ければ制御できる

典型的な改善パターン

競技プログラミング（AtCoder など）で定番の手法は、 実務でもそのまま使えます。名前を知っていると、調べられます。

1. ループの中の検索 → ハッシュ

O(n × m) → O(n + m)

事前に Map / Set を作る（本章の冒頭で扱ったもの）。最も出番が多い手法です。

2. ソート + 二分探索

O(n²) → O(n log n)

「一番近い値を探す」「範囲内のものを数える」時に効きます。 DB の INDEX がやっていることと同じです。

3. 累積和 — 区間の合計を O(1) で

// 悪い: 問い合わせのたびに合計する → 1回 O(n)
const sum = (from, to) => data.slice(from, to).reduce((a, b) => a + b, 0);
 
// 良い: 先に累積を作っておく → 1回 O(1)
const cum = [0];
for (const v of data) cum.push(cum[cum.length - 1] + v);
const sum2 = (from, to) => cum[to] - cum[from];

「◯月〜◯月の売上合計」を何度も出すような処理で、そのまま使えます。

4. しゃくとり法 — 連続する範囲を効率よく走査

条件を満たす連続区間を、左右の端をずらしながら1回のループで探す
O(n²) → O(n)

「直近5分間のアクセス数」「連続してエラーが続いた区間」などで使えます。

5. メモ化・前計算

同じ計算を何度もしている → 結果を覚えておく

計算量とデータ構造のキャッシュと同じ発想です。まず「同じ計算を繰り返していないか」を疑う。

実務での言い換え

□ AtCoder / LeetCode などで、計算量を意識して解く練習は有効
□ ただし「解けること」より「なぜその計算量になるか」を説明できることが重要

実務の落とし穴まとめ

1. ループの中で includes / find — O(n²)。Set か Map にする
2. ループの中で DB クエリ / HTTP — N+1。まとめて取る
3. shift() でキューを回す — O(n²)。インデックスを進める
4. LIMIT の無い SELECT — 件数が増えた瞬間にメモリと時間が破綻する
5. 開発データが少なすぎて気づかない — 本番相当の件数で1回試す
6. 測らずに最適化 — ボトルネックは予想と違う
7. O(n) だから安心 — n がネットワーク往復の回数なら致命的

まとめ

• 計算量はデータが増えた時の増え方。定数倍と小さい項は捨てる
• 実務で効くのは O(n²) を作らないこと。二重ループを探す
• 配列の検索は O(n)、Map / Set は O(1)。ループの前に Map を作る
• N+1 は O(n) 回のネットワーク往復。1回の重さが桁違いなので致命的になる
• INDEX が O(log n) なのは、並び順で半分ずつ絞れるから。 関数を通したり後方一致にすると並び順が使えず効かない
• メモリを使って時間を買う（Map・キャッシュ）。ただしキャッシュは無効化が本体
• オーダーは最初から意識し、定数倍は測ってから直す
• 見積もりは n の特定 → ループ構造 → n の実際の値の3ステップ。 1秒 ≒ 1億回を基準に桁で判断する
• 改善の定番は ハッシュ化・ソート+二分探索・累積和・しゃくとり法・メモ化

公式ドキュメント

迷ったら一次情報に戻ってください。

章末問題

次の章からは、1台のマシンの外に出ます。 ネットワーク・HTTP・ブラウザと、順にたどっていきます。