メインコンテンツまでスキップ

計算量 — O 記法で速さと使用メモリを見積もる

「このコードは遅い」と言うとき、何を根拠にしているでしょうか。実測は環境に左右されますし、開発機で速くても本番のデータ量で破綻することがあります。

計算量は、入力が増えたときに処理量がどう増えるかという形で速さを表す方法です。マシンの性能に依存しないので、コードを読むだけで見積もれます。

この章で学ぶこと​

  • O 記法が何を表していて、何を捨てているか
  • 代表的なオーダーが、実際のデータ量でどれくらいの差になるか
  • 時間計算量と空間計算量の区別
  • コードからオーダーを数える手順
  • 最悪・平均・最良を使い分ける場面
前提知識

何らかの言語でループと再帰を書いた経験があれば読めます。数学的な準備は不要です。

何を見て、何を捨てているのか​

計算量が表すのは 入力サイズ n が増えたときの増え方 です。実行時間の絶対値ではありません。

そのために 2 つのものを捨てます。

  • 定数倍 — 2n も 100n も O(n) と書きます
  • 低次の項 — n² + 1000n + 5 は O(n²) と書きます

乱暴に見えますが、これは n が十分大きいときに何が支配的かを見るためです。n² + 1000n で n が 100 万なら、n² は 1 兆、1000n は 10 億で、後者は 0.1% 未満にしかなりません。規模が大きくなるほど、最も速く増える項だけが結果を決めます。

逆に言えば、n が小さいときは O 記法の順位が逆転しえます。O(n²) の単純なアルゴリズムが、O(n log n) の複雑なアルゴリズムより速いことは珍しくありません。定数倍が違うためです。実際の言語のソート実装が、小さい配列では挿入ソートに切り替えるのはこの理由です。

代表的なオーダー​

記法呼び方典型例
O(1)定数時間配列の添字アクセス、ハッシュマップの取得 (平均)
O(log n)対数時間二分探索、平衡二分探索木の検索
O(n)線形時間配列の全走査、線形探索
O(n log n)線形対数時間一般的なソート (マージソート、クイックソート)
O(n²)二乗時間二重ループ、素朴なソート
O(2^n)指数時間部分集合の全列挙

数字で見ると差が実感できます。1 ステップ 1 ナノ秒として、n が増えたときの目安です。

nO(log n)O(n)O(n log n)O(n²)
1,000約 101,000約 1 万100 万
100 万約 20100 万約 2,000 万1 兆
10 億約 3010 億約 300 億10 の 18 乗

**O(log n) はほとんど増えません。**データが 1,000 倍になっても手数は 10 増える程度です。この性質を使ったのが二分探索で、データベースのインデックスも同じ理屈で速くなります。逆に O(n²) は 100 万件で 1 兆ステップになり、1 ナノ秒換算でも 16 分かかります。実用になりません。

「データが 10 倍になったらどうなるか」を答えられるかどうかが、O 記法を使えているかの目安になります。O(n) なら 10 倍、O(n²) なら 100 倍、O(log n) ならほぼ変わりません。

時間計算量と空間計算量​

計算量には 2 種類あります。

測るもの
時間計算量処理のステップ数
空間計算量処理に必要な追加のメモリ量

空間計算量で数えるのは、入力そのものを除いた追加分です。長さ n の配列を受け取って、変数を数個使うだけなら O(1) です。入力の配列自体は数えません。

// 空間計算量 O(1) ー 追加で使うのは変数 2 つだけ
function sum(numbers: number[]): number {
  let total = 0;
  for (const n of numbers) {
    total += n;
  }
  return total;
}

// 空間計算量 O(n) ー 入力と同じ長さの配列を新たに作る
function doubled(numbers: number[]): number[] {
  return numbers.map((n) => n * 2);
}

**再帰の呼び出しスタックも空間に数えます。**深さ n まで再帰する関数は、たとえ各段で変数を 1 つしか使わなくても空間計算量 O(n) です。ここは見落としやすい点で、同じアルゴリズムでもループで書くか再帰で書くかで空間計算量が変わります。

コードから数える​

ループの入れ子は掛け算​

// O(n)
for (let i = 0; i < n; i++) {
  doSomething();
}

// O(n²) ー 外側 n 回 × 内側 n 回
for (let i = 0; i < n; i++) {
  for (let j = 0; j < n; j++) {
    doSomething();
  }
}

// O(n²) ー 内側が平均 n/2 回でも定数倍を捨てるので同じ
for (let i = 0; i < n; i++) {
  for (let j = i; j < n; j++) {
    doSomething();
  }
}

3 つ目は内側の回数が n, n-1, ..., 1 と減るので合計は n(n+1)/2 です。定数倍と低次項を捨てて O(n²) になります。

対数が出るのは「毎回何分の一かにする」とき​

// O(log n) ー 1 回ごとに残りが半分になる
let remaining = n;
while (remaining > 1) {
  remaining = Math.floor(remaining / 2);
}

半分にし続けて 1 になるまでの回数が log₂ n です。「毎回一定の割合を捨てる」構造を見つけたら対数と考えてよく、これが二分探索の速さの正体です。

隠れたループに注意する​

// 一見 O(n) だが、実際は O(n²)
for (const item of items) {
  if (others.includes(item)) {   // includes は内部で O(m) の走査
    result.push(item);
  }
}

includes や indexOf は配列を走査するので O(m) です。ループの中で呼べば掛け算になります。others を Set に変換しておけば、判定が平均 O(1) になって全体が O(n + m) に落ちます。

**ライブラリの関数を「1 ステップ」と数えないこと。**中で何をしているかを知らないと、オーダーを見誤ります。

ハッシュ以外にも、二重ループを一重に落とす型がいくつかあります。どの型が当たるかは配列を走査する型で整理します。

最悪・平均・最良​

同じアルゴリズムでも、入力によって手数が変わります。

意味使いどころ
最悪計算量最も手数がかかる入力での値保証が要る場面。O 記法は通常これを指す
平均計算量入力が偏っていないときの期待値実用上の目安
最良計算量最も手数が少ない入力での値ほとんど使わない

ハッシュマップが分かりやすい例です。取得は平均 O(1) ですが、すべてのキーが同じハッシュ値に衝突すると 1 本の連鎖を走査することになり、最悪 O(n) です。実用上は平均で語られますが、悪意ある入力でわざと衝突を起こす攻撃 (ハッシュ衝突攻撃) が成立するのは、この最悪値が理由です。

クイックソートも平均 O(n log n)、最悪 O(n²) です。ピボットの選び方で最悪を避ける工夫が入っています。

よくある誤解​

「O(n²) は必ず O(n log n) より遅い」 — n が小さいときは逆転しえます。O 記法は定数倍を捨てているので、絶対的な速さの比較ではありません。

「計算量が同じなら実行速度も同じ」 — 違います。O(n) どうしでも定数倍が 100 倍違えば実行時間も 100 倍違います。O 記法が答えるのは「増え方」だけです。

「空間計算量には入力のサイズも含まれる」 — 通常は含めません。数えるのは入力を除いた追加のメモリです。

「再帰で書いても空間計算量は変わらない」 — 変わります。呼び出しスタックが深さぶん積まれます。

「ハッシュマップは常に O(1)」 — 平均が O(1) で、最悪は O(n) です。

確認問題​

問 1. 次の関数の時間計算量と空間計算量を答えてください。
function hasDuplicate(numbers: number[]): boolean {
  for (let i = 0; i < numbers.length; i++) {
    for (let j = i + 1; j < numbers.length; j++) {
      if (numbers[i] === numbers[j]) return true;
    }
  }
  return false;
}

答え: 時間計算量 O(n²)、空間計算量 O(1)

二重ループで、内側の回数は n-1, n-2, ..., 1 と減ります。合計は n(n-1)/2 で、定数倍と低次項を捨てて O(n²) です。

追加で確保しているのはカウンタ変数 2 つだけなので、空間計算量は O(1) です。入力の配列は数えません。

なお、これは Set を使えば時間 O(n)・空間 O(n) に改善できます。時間を稼ぐためにメモリを払うという典型的なトレードオフです。

function hasDuplicateFast(numbers: number[]): boolean {
  const seen = new Set<number>();
  for (const n of numbers) {
    if (seen.has(n)) return true;
    seen.add(n);
  }
  return false;
}
問 2. 次の再帰関数の空間計算量はいくつですか。
function factorial(n: number): number {
  if (n <= 1) return 1;
  return n * factorial(n - 1);
}

答え: O(n)

各段で使っている変数は引数 1 つだけですが、factorial(n) は factorial(n-1) を呼び、それがさらに factorial(n-2) を呼び、と n 段まで積み上がります。この呼び出しスタックが空間計算量になります。

同じ計算をループで書くと空間計算量は O(1) になります。

function factorialLoop(n: number): number {
  let result = 1;
  for (let i = 2; i <= n; i++) {
    result *= i;
  }
  return result;
}

時間計算量はどちらも O(n) で同じです。空間だけが違います。

問 3. データ件数が 1,000 件のときに 1 秒かかる処理があります。100 万件にしたら何秒かかりますか。計算量が O(n) の場合と O(n²) の場合で答えてください。

答え: O(n) なら約 1,000 秒 (約 17 分)、O(n²) なら約 100 万秒 (約 11.6 日)

件数は 1,000 倍になっています。

  • O(n) — 手数も 1,000 倍。1 秒 × 1,000 = 1,000 秒
  • O(n²) — 手数は 1,000² = 100 万倍。1 秒 × 100 万 = 100 万秒

「1,000 件で 1 秒なら 100 万件でも数秒だろう」という直感は O(n²) では完全に外れます。開発環境の小さなデータで問題が出ないアルゴリズムが、本番のデータ量で破綻するのはこの構造です。

なお O(log n) なら 1 秒が約 2 秒にしかなりません。

まとめ​

  • O 記法は入力が増えたときの増え方を表し、定数倍と低次項を捨てます
  • 定数倍を捨てているので、n が小さいときは順位が逆転しえます
  • 時間計算量はステップ数、空間計算量は入力を除いた追加メモリです
  • 再帰の呼び出しスタックも空間計算量に数えます
  • ループの入れ子は掛け算、毎回一定割合を捨てる構造は対数です
  • ライブラリ関数を 1 ステップと数えないでください。includes などは内部で走査しています
  • ハッシュマップは平均 O(1)、最悪 O(n) です
関連リファレンス

次に読む​