ウェブエンジニア問題集

アルゴリズムと計算量 — Big-O記法と探索・ソートの基本

「このAPI、データが少ないうちは速かったのに、本番で10万件になったら急に遅くなった」。これはアルゴリズムの計算量を意識していないときに典型的に起きる現象です。

この章では、Big-O記法 で計算量を見積もれるようになることと、探索・ソートの代表的なアルゴリズム を押さえます。アルゴリズムの選択は、ライブラリに任せつつも「ここはO(n²)になってないか？」と疑える目を持つのが目的です。

計算量 (Big-O) — 入力が増えたときどれくらい遅くなるか

計算量は、入力サイズ n に対して処理量がどう増えるか を表す指標です。具体的な秒数ではなく「増え方」だけに注目するのがポイントです。

左から右に行くほど遅くなります。n を10倍にしたとき の処理量のイメージはこうです。

計算量n=100n=10,000n=1,000,000典型例
O(1)111ハッシュテーブルの検索
O(log n)71420二分探索
O(n)10010,0001,000,000配列を1回なめる
O(n log n)700133,00020,000,000実用的なソート
O(n²)10,000100,000,0001,000,000,000,000二重ループ

O(n²) が1,000,000件で1兆回 になる、というのが重要です。「ユーザー1,000人に対してループを二重に回す」ような処理は、ユーザー数が10倍になった瞬間に100倍遅くなります。

線形探索 — 素朴に先頭から順に見る

線形探索 は、先頭から順番に目的のデータを探していく方法です。計算量は O(n)。

function linearSearch(arr, target) {
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] === target) return i;
  }
  return -1;
}

ソートされていなくても使えるのが利点です。データが小さいうちはこれで十分ですし、JavaScriptの Array.indexOf や Array.find の実態は線形探索です。

二分探索 — ソート済み配列なら一気に速い

二分探索 は、ソート済みの配列 に対して使える、はるかに効率的な探索です。毎回中央の要素と比較して、探索範囲を半分に絞り込みます。

計算量は O(log n)。要素数が2倍になっても比較回数は1回しか増えません。

要素数線形探索（最悪）二分探索（最悪）
100100回7回
10,00010,000回14回
1,000,0001,000,000回20回
1,000,000,00010億回30回

実務では「事前にソートしておいて、二分探索する」設計を明示的に書くよりも、DBのBツリーインデックス のような裏側で似た仕組みが動いている、という理解の方が役立ちます。WHERE id = ? が速いのは、内部で O(log n) の構造を使っているからです。

ソートアルゴリズム

データを並べ替えるアルゴリズムは山のようにありますが、ここでは考え方の違う3つを押さえます。

バブルソート — 隣同士を比較して入れ替える

隣り合う要素を比較して、順番が逆なら入れ替える、を繰り返します。

分かりやすいですが、計算量は O(n²)。実務で使うことはまずなく、「最も遅いソート」の代名詞として覚えておく程度でOKです。

マージソート — 分割して統合する

配列を半分ずつに分割していき、分割しきったところからソートしながらマージ していく方式です。

計算量は O(n log n)。安定 (同じ値の順序が保たれる) かつ 最悪ケースでも速度が保証される ので、JavaScriptの Array.sort やPythonの sorted などが採用している Timsort のベースになっています。

クイックソート — ピボットを基準に分ける

ピボット（基準値）を選び、それより小さい要素と大きい要素に分けて、それぞれを再帰的にソートします。

[5, 3, 8, 1, 7] (ピボット = 5)
 ↓
[3, 1] + [5] + [8, 7]
 ↓ 再帰
[1, 3] + [5] + [7, 8]
 ↓
[1, 3, 5, 7, 8]

平均 O(n log n) と非常に速く、追加メモリが少なくて済む のが強みです。ただしピボットの選び方が悪い（例 毎回最小値を選んでしまう）と最悪 O(n²) まで劣化します。

3つの比較

アルゴリズム平均最悪メモリ実務での位置づけ
バブルソートO(n²)O(n²)O(1)教材用途
マージソートO(n log n)O(n log n)O(n)言語標準ソートのベース
クイックソートO(n log n)O(n²)O(log n)メモリに余裕がない場面で強い

実務では言語の標準ソートを使えばよい です。自前で実装する代わりに、「それが何をしているか理解する」のがこの章のゴールです。

よくあるハマりどころ

1. 配列の中から重複を探すのに二重ループを書いて遅い

// ❌ O(n²)
for (const a of items) {
  for (const b of items) {
    if (a.id === b.id && a !== b) duplicates.push(a);
  }
}
 
// ✅ O(n) — ハッシュ(Set)で判定
const seen = new Set();
for (const a of items) {
  if (seen.has(a.id)) duplicates.push(a);
  seen.add(a.id);
}

この書き換えはよく登場します。二重ループが出てきたらハッシュで1重にできないか考える、が定番の改善パターンです。

2. .sort() の前提を忘れて二分探索が動かない

二分探索はソート済み が大前提です。データを追加したあとに再ソートを忘れると、時々見つからないという不安定なバグになります。

3. 小さなnでは計算量の差を気にしすぎない

n=100 なら O(n²) = 10,000 回、これは現代のCPUでは一瞬です。小さいデータで過度に最適化するのは逆に読みづらくなります。n が大きくなる可能性がある箇所、特にリクエストごとに増えうるループに集中して気を配ります。

ちゃんと使うためのポイント

  • Big-O は「入力が大きくなったときの増え方」を表す。具体的な秒数ではない
  • O(n²) はn=1,000でもう100万回。ループの中でループを書いたら一度は疑う
  • ソート済み前提なら 二分探索 O(log n)、それ以外は線形探索 O(n)
  • 実務では言語標準のソート を信頼してよい。中身は概ね O(n log n)
  • 「二重ループ → ハッシュで1重」は最頻出の改善パターン

次の章では、Web開発の基盤となる ネットワーク の基礎に進みます。ブラウザにURLを入れてからページが表示されるまでに何が起きているのか、を整理しましょう。