Big-O記法とは？アルゴリズム計算量を3分で理解

アルゴリズムの計算量を表すBig-O記法は、コードのスケーラビリティを評価するための共通言語です。「データが100倍に増えたらどれだけ遅くなるか」を見積もるのに不可欠です。本記事では、Big-O記法を3分で理解できるよう整理します。

Big-Oとは

入力サイズnに対して、アルゴリズムが「最悪どれくらい時間/空間を使うか」を表す表記です。定数倍や低次項は無視するため、「ざっくり傾向」を比較できます。

代表的な計算量

• O(1)：定数時間（配列のインデックスアクセス、ハッシュマップの参照）
• O(log n)：対数時間（二分探索、平衡木の操作）
• O(n)：線形時間（配列を1回ループ）
• O(n log n)：マージソート・クイックソートの平均
• O(n²)：2重ループ（バブルソート）
• O(2ⁿ)：指数時間（フィボナッチ再帰）
• O(n!)：階乗時間（順列全列挙）

具体例

// O(1) - 配列の先頭アクセス
arr[0];

// O(n) - 配列をループ
for (const x of arr) { ... }

// O(n²) - 2重ループ
for (const a of arr) {
  for (const b of arr) { ... }
}

// O(log n) - 二分探索
let lo = 0, hi = arr.length - 1;
while (lo <= hi) {
  const mid = (lo + hi) >> 1;
  ...
}

nの増加と実行時間のイメージ

• n=1,000 → O(n²) = 100万回 → まだ高速
• n=10,000 → O(n²) = 1億回 → 数秒
• n=1,000,000 → O(n²) = 1兆回 → 実用不能

O(n)とO(n²)の差は、n=100万になると100万倍違ってきます。

空間計算量

時間と同じ表記でメモリ使用量も表します。例えば配列を1つ作るならO(n)、再帰呼び出しのスタックは深さに比例します。

実務での意識ポイント

• 大きな配列に対する arr.includes の繰り返しは O(n²) になりがち → Setに変換してO(n)
• Nested for は要素数次第で危険
• SQLでN+1問題はO(N)が積み重なる典型
• ハッシュマップは挿入・参照がO(1)平均、メモリと交換に時間を稼ぐ

まとめ

Big-O記法は「アルゴリズムのスケーラビリティを比較する物差し」です。O(1) ＜ O(log n) ＜ O(n) ＜ O(n log n) ＜ O(n²) ＜ O(2ⁿ)の順序を覚え、実装時に常に意識すると、性能問題を未然に防げます。