サイトアイコンmaita tomoya dev io

#67 アルゴリズム計算量ガイド -- 20の比較問題で学ぶO記法と実装パターン

この記事は、自作のアルゴリズム計算量ビジュアライザの解説記事である。ビジュアライザでは20種類の比較問題を通して、異なるアルゴリズムの速度差を視覚的に確認できる。

アルゴリズム計算量ビジュアライザで実際に動かしてみる

本記事では、ビジュアライザに登場する全アルゴリズムについて、仕組み・計算量・JavaScriptによる実装コードを網羅的に解説する。

対象読者

  • プログラミングを学び始めた初学者
  • 情報系の学生でアルゴリズムの授業を受けている方
  • コーディング面接（技術面接）の対策をしている方
  • 「計算量」という言葉は聞いたことがあるが、具体的にどう違うのか実感を得たい方

O記法（ビッグオー記法）とは

計算量の考え方

アルゴリズムの「速さ」を測る方法として、**計算量（Computational Complexity）**という概念がある。これは「データの件数が増えたとき、処理にかかる時間がどのくらい増えるか」を数学的に表現したものである。

たとえば、100件のデータを処理するのに1秒かかるプログラムがあるとする。データが1000件に増えたとき、処理時間はどうなるだろうか。

  • 10秒になるなら「データ量に比例して増える」 → O(n)
  • 100秒になるなら「データ量の2乗に比例して増える」 → O(n^2)
  • 1秒のままなら「データ量に関係なく一定」 → O(1)

この「増え方のパターン」を表す記法が**O記法（ビッグオー記法、Big-O notation）**である。

O記法の読み方

O記法は「オーダー」と読む。O(n)なら「オーダーn」、O(n^2)なら「オーダーnの2乗」と読む。ここでいうnはデータの件数を指す。

重要なのは、O記法は定数倍を無視するということである。たとえば、ループが2回繰り返されるプログラムと3回繰り返されるプログラムは、どちらもO(n)として扱う。O記法が注目するのは「nが大きくなったときの増加の傾向」であり、細かい係数は問題にしない。

代表的な計算量クラス

O記法名称増加の仕方身近な例
O(1)定数時間データ量に関係なく一定配列のインデックスアクセス
O(log n)対数時間データが倍になっても1ステップ増えるだけ二分探索
O(n)線形時間データ量に正比例配列の全要素走査
O(n log n)線形対数時間nよりやや多い程度効率的なソート
O(n^2)二乗時間データが倍になると4倍に二重ループ
O(2^n)指数時間データが1件増えるだけで2倍に全組み合わせ探索

具体的な計算回数の比較

数字で見ると、計算量クラスの差がどれだけ大きいかが実感できる。

nO(1)O(log n)O(n)O(n log n)O(n^2)O(2^n)
1013.310331001,024
10016.610066410,0001.27 x 10^30
1,0001101,0009,9661,000,000天文学的数値
10,000113.310,000132,877100,000,000計算不能

n=100のとき、O(n^2)は10,000回の処理が必要だが、O(2^n)は宇宙の原子の数（約10^80）をはるかに超える回数が必要になる。これが「アルゴリズムの選択が重要」と言われる理由である。

なぜ計算量が重要なのか

実務では、データ量が数万件、数百万件になることは珍しくない。たとえばECサイトの商品検索で100万件の商品から探す場合を考えてみよう。

  • O(n)のアルゴリズム: 100万回の処理 → 一瞬で完了
  • O(n^2)のアルゴリズム: 1兆回の処理 → 数分から数時間
  • O(2^n)のアルゴリズム: 実質的に計算不可能

1回の処理が1ナノ秒（10億分の1秒）だとしても、1兆回なら約17分かかる。ユーザーが検索ボタンを押して17分待つサービスは成立しない。だからこそ、計算量を理解してアルゴリズムを選ぶ能力が求められる。

ソートアルゴリズム

ソート（並べ替え）は、アルゴリズムの中で最も基本的かつ重要なテーマである。ビジュアライザでは6種類のソートアルゴリズムを比較できる。

バブルソート -- O(n^2)

仕組み

バブルソートは最もシンプルなソートアルゴリズムである。配列の先頭から順に隣り合う2つの要素を比較し、順序が逆なら交換する。これを配列の末尾まで繰り返すと、最も大きい要素が末尾に「浮き上がる（バブルアップする）」。これを全要素分繰り返す。

「泡（バブル）が水面に浮き上がる」様子に似ていることから、この名前がついた。

動作例

配列 [5, 3, 8, 1] をソートする場合:

1回目の走査:
[5, 3, 8, 1] → 5と3を比較、交換 → [3, 5, 8, 1]
[3, 5, 8, 1] → 5と8を比較、そのまま → [3, 5, 8, 1]
[3, 5, 8, 1] → 8と1を比較、交換 → [3, 5, 1, 8]  ← 8が末尾に確定

2回目の走査:
[3, 5, 1, 8] → 3と5を比較、そのまま → [3, 5, 1, 8]
[3, 5, 1, 8] → 5と1を比較、交換 → [3, 1, 5, 8]  ← 5が確定

3回目の走査:
[3, 1, 5, 8] → 3と1を比較、交換 → [1, 3, 5, 8]  ← 完了

JavaScript実装

function bubbleSort(arr) {
  const n = arr.length;
  for (let i = 0; i < n - 1; i++) {
    for (let j = 0; j < n - 1 - i; j++) {
      if (arr[j] > arr[j + 1]) {
        // 隣接要素を交換
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
      }
    }
  }
  return arr;
}

なぜ遅いのか

外側のループがn回、内側のループも最大n回まわるため、比較回数は n x (n-1) / 2 となる。O記法では定数を無視するのでO(n^2)である。データが1000件あれば約50万回の比較が必要になる。

ビジュアライザで動かすと、バブルソートは1つずつ要素が端に移動していく様子が確認できる。クイックソートなどと比べると、明らかにステップ数が多いことが視覚的にわかるはずである。

選択ソート -- O(n^2)

仕組み

選択ソートは「未ソート部分から最小値を見つけて、先頭に配置する」という操作を繰り返す。

  1. 配列全体から最小値を見つけ、先頭の要素と交換する
  2. 2番目以降から最小値を見つけ、2番目の要素と交換する
  3. これを繰り返す

動作例

[5, 3, 8, 1]
→ 最小値1を発見、先頭と交換 → [1, 3, 8, 5]
→ 残り[3, 8, 5]の最小値3、そのまま → [1, 3, 8, 5]
→ 残り[8, 5]の最小値5、交換 → [1, 3, 5, 8]

JavaScript実装

function selectionSort(arr) {
  const n = arr.length;
  for (let i = 0; i < n - 1; i++) {
    let minIndex = i;
    // 未ソート部分から最小値のインデックスを探す
    for (let j = i + 1; j < n; j++) {
      if (arr[j] < arr[minIndex]) {
        minIndex = j;
      }
    }
    // 最小値を現在位置と交換
    if (minIndex !== i) {
      [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
    }
  }
  return arr;
}

バブルソートとの違い

バブルソートと選択ソートはどちらもO(n^2)だが、交換回数が異なる。バブルソートは隣接要素を何度も交換するが、選択ソートは各パスで最大1回しか交換しない。そのため、交換コストが高い場合は選択ソートの方が有利になることがある。

ただし比較回数は両者ともO(n^2)であり、大量データに対してはどちらも実用的ではない。

挿入ソート -- O(n^2)

仕組み

挿入ソートは「未ソートの要素を、ソート済み部分の正しい位置に挿入する」アルゴリズムである。

トランプの手札を整理する場面を想像してほしい。手札の左側はすでにソート済みで、新しく引いたカードを正しい位置に差し込む。これがまさに挿入ソートの動きである。

動作例

[5, 3, 8, 1]
→ 3をソート済み[5]に挿入 → [3, 5, 8, 1]
→ 8をソート済み[3, 5]に挿入 → [3, 5, 8, 1]
→ 1をソート済み[3, 5, 8]に挿入 → [1, 3, 5, 8]

JavaScript実装

function insertionSort(arr) {
  const n = arr.length;
  for (let i = 1; i < n; i++) {
    const key = arr[i];
    let j = i - 1;
    // keyより大きい要素を1つ後ろにずらす
    while (j >= 0 && arr[j] > key) {
      arr[j + 1] = arr[j];
      j--;
    }
    arr[j + 1] = key;
  }
  return arr;
}

「ほぼソート済み」で速い理由

挿入ソートの最悪計算量はO(n^2)だが、**データがほぼソート済みの場合はO(n)**に近い性能を発揮する。なぜなら、各要素の挿入位置がすぐ近くにあるため、内側のwhileループがほとんど回らないからである。

この特性から、実用的なソートライブラリでは「小さい部分配列の仕上げに挿入ソートを使う」というテクニックが使われている。JavaScriptのArray.prototype.sort()の内部実装（V8エンジンのTimSort）でも、この手法が採用されている。

クイックソート -- O(n log n)

仕組み

クイックソートは**分割統治法（Divide and Conquer）**を使うソートアルゴリズムである。

  1. 配列から1つの要素を**ピボット（基準値）**として選ぶ
  2. ピボットより小さい要素を左側、大きい要素を右側に振り分ける（パーティション）
  3. 左側と右側それぞれに対して再帰的に同じ操作を行う

「分割統治法」とは、大きな問題を小さな部分問題に分割し、それぞれを解決してから結果を統合する手法のことである。

JavaScript実装

function quickSort(arr, left = 0, right = arr.length - 1) {
  if (left >= right) return arr;

  const pivotIndex = partition(arr, left, right);
  quickSort(arr, left, pivotIndex - 1);
  quickSort(arr, pivotIndex + 1, right);
  return arr;
}

function partition(arr, left, right) {
  const pivot = arr[right]; // 末尾をピボットに選択
  let i = left - 1;

  for (let j = left; j < right; j++) {
    if (arr[j] <= pivot) {
      i++;
      [arr[i], arr[j]] = [arr[j], arr[i]];
    }
  }
  [arr[i + 1], arr[right]] = [arr[right], arr[i + 1]];
  return i + 1;
}

最悪ケースO(n^2)になる条件

クイックソートの平均計算量はO(n log n)だが、ピボットが常に最小値または最大値になる場合、最悪のO(n^2)に退化する。これは「すでにソート済みの配列」に対して「先頭または末尾をピボットにする」場合に起こる。

ピボット選択の工夫

最悪ケースを避けるための代表的な手法がある。

  • ランダムピボット: ランダムな位置の要素をピボットにする
  • 三値の中央値（Median of Three）: 先頭・中央・末尾の3つから中央値を選ぶ
// 三値の中央値でピボットを選ぶ例
function medianOfThree(arr, left, right) {
  const mid = Math.floor((left + right) / 2);
  if (arr[left] > arr[mid]) [arr[left], arr[mid]] = [arr[mid], arr[left]];
  if (arr[left] > arr[right]) [arr[left], arr[right]] = [arr[right], arr[left]];
  if (arr[mid] > arr[right]) [arr[mid], arr[right]] = [arr[right], arr[mid]];
  return mid;
}

マージソート -- O(n log n)

仕組み

マージソートも分割統治法を使う。

  1. 配列を半分に分割する
  2. 各半分を再帰的にソートする
  3. ソート済みの2つの配列を**統合（マージ）**する

「マージ」とは、2つのソート済み配列を1つのソート済み配列にまとめる操作のことである。2つの配列の先頭同士を比較し、小さい方を取り出すことを繰り返すだけで実現できる。

JavaScript実装

function mergeSort(arr) {
  if (arr.length <= 1) return arr;

  const mid = Math.floor(arr.length / 2);
  const left = mergeSort(arr.slice(0, mid));
  const right = mergeSort(arr.slice(mid));
  return merge(left, right);
}

function merge(left, right) {
  const result = [];
  let i = 0;
  let j = 0;

  // 両方の配列から小さい方を順に取り出す
  while (i < left.length && j < right.length) {
    if (left[i] <= right[j]) {
      result.push(left[i]);
      i++;
    } else {
      result.push(right[j]);
      j++;
    }
  }

  // 残りの要素を追加
  return result.concat(left.slice(i)).concat(right.slice(j));
}

安定ソートとは

**安定ソート（Stable Sort）**とは、同じ値の要素について、ソート前の相対的な順序が保たれるソートのことである。

たとえば、社員リストを「部署→名前」の順でソートする場合、安定ソートなら「名前でソート → 部署でソート」の2段階で正しい結果が得られる。不安定ソートではこの保証がない。

マージソートは安定ソートである。クイックソートやヒープソートは不安定ソートである。

追加メモリの必要性

マージソートの欠点は、マージ時に元の配列と同じサイズの**追加メモリ（O(n)）**が必要なことである。クイックソートは配列内で要素を入れ替えるだけなので追加メモリがほぼ不要（O(log n)、再帰のスタック分のみ）である。メモリが限られた環境ではこの差が重要になる。

ヒープソート -- O(n log n)

ヒープとは何か

**ヒープ（Heap）**は、木構造の一種で、「親ノードは常に子ノード以上（または以下）の値を持つ」という性質を持つデータ構造である。

  • 最大ヒープ: 親 >= 子（根が最大値）
  • 最小ヒープ: 親 <= 子（根が最小値）

配列でヒープを表現する場合、インデックスiの要素の子は 2i + 1 と 2i + 2 に位置する。

配列: [9, 7, 8, 3, 5, 6, 4]

木構造で表すと:
        9
       / \
      7    8
     / \  / \
    3   5 6   4

仕組み

ヒープソートは以下の手順で動作する。

  1. 配列を最大ヒープに変換する（ヒープ構築）
  2. ヒープの根（最大値）を末尾と交換する
  3. ヒープサイズを1減らし、ヒープ性質を修復する（ヒープ化）
  4. 手順2-3を繰り返す

JavaScript実装

function heapSort(arr) {
  const n = arr.length;

  // 最大ヒープを構築
  for (let i = Math.floor(n / 2) - 1; i >= 0; i--) {
    heapify(arr, n, i);
  }

  // ヒープから1つずつ最大値を取り出す
  for (let i = n - 1; i > 0; i--) {
    [arr[0], arr[i]] = [arr[i], arr[0]]; // 根と末尾を交換
    heapify(arr, i, 0); // ヒープサイズを縮めて修復
  }
  return arr;
}

function heapify(arr, size, rootIndex) {
  let largest = rootIndex;
  const left = 2 * rootIndex + 1;
  const right = 2 * rootIndex + 2;

  if (left < size && arr[left] > arr[largest]) {
    largest = left;
  }
  if (right < size && arr[right] > arr[largest]) {
    largest = right;
  }
  if (largest !== rootIndex) {
    [arr[rootIndex], arr[largest]] = [arr[largest], arr[rootIndex]];
    heapify(arr, size, largest);
  }
}

インプレースソートの利点

ヒープソートは**インプレース（in-place）**で動作する。つまり、元の配列上で並べ替えを行うため、マージソートのような追加メモリ（O(n)）が不要である。必要な追加メモリはO(1)のみ。

ただし、実際のベンチマークではクイックソートの方がキャッシュ効率が良いため高速になることが多い。ヒープソートの利点は「最悪でもO(n log n)が保証される」ことである。

ソートアルゴリズム比較表

アルゴリズム平均計算量最悪計算量空間計算量安定性特徴
バブルソートO(n^2)O(n^2)O(1)安定最もシンプル。教育用途向き
選択ソートO(n^2)O(n^2)O(1)不安定交換回数が少ない
挿入ソートO(n^2)O(n^2)O(1)安定ほぼソート済みデータに強い
クイックソートO(n log n)O(n^2)O(log n)不安定平均的に最速。実用で最も使われる
マージソートO(n log n)O(n log n)O(n)安定安定ソートが必要な場面で有用
ヒープソートO(n log n)O(n log n)O(1)不安定最悪計算量が保証される

ソート比較ペアの解説

ビジュアライザでは以下の9ペアの比較を体験できる。それぞれ、なぜ速度差が生じるのかを解説する。

バブルソート vs クイックソート

最も速度差が顕著なペア。バブルソートはO(n^2)で、隣接要素を1つずつ交換するため「局所的な移動」しかできない。一方クイックソートはO(n log n)で、ピボットによるパーティションで「大域的な振り分け」を行う。1回のパーティションで多くの要素が正しい側に配置されるため、圧倒的に効率が良い。

選択ソート vs マージソート

選択ソートO(n^2)は毎回「残り全体」を走査して最小値を探す。マージソートO(n log n)は分割統治により、問題サイズを半分ずつ小さくしていく。問題を分割して解く方が、毎回全体を走査するよりはるかに効率的である。

挿入ソート vs ヒープソート

挿入ソートO(n^2)は1要素ずつ正しい位置に挿入するが、挿入先を探すのに最大O(n)かかる。ヒープソートO(n log n)はヒープ構造を利用することで、最大値の取り出しとヒープの修復をO(log n)で行える。ただし、データがほぼソート済みの場合は挿入ソートの方が速くなることがある。

バブルソート vs 選択ソート

どちらもO(n^2)だが、選択ソートの方がわずかに速いことが多い。理由は交換回数の違いである。バブルソートは比較のたびに交換する可能性があるが、選択ソートは各パスで最大1回しか交換しない。ビジュアライザでは、微妙な速度差として現れる。

クイックソート vs マージソート

どちらもO(n log n)で理論上は同等だが、実測ではクイックソートの方が速いことが多い。理由はキャッシュ効率にある。クイックソートは配列内で要素を入れ替えるため、メモリアクセスの局所性が高い。マージソートは追加配列へのコピーが発生するため、キャッシュミスが増える。

挿入ソート vs バブルソート

どちらもO(n^2)だが、挿入ソートの方がわずかに速い傾向がある。バブルソートは毎回配列全体を走査するが、挿入ソートは挿入位置が見つかった時点でそのパスを終了できるためである。

バブルソート vs マージソート

O(n^2)とO(n log n)の差がはっきり出るペア。データ量が増えるほど差が広がる。n=1000では、バブルソートが約50万回の比較を必要とするのに対し、マージソートは約1万回で済む。

選択ソート vs ヒープソート

選択ソートは「未ソート部分から最小値を線形探索」するためO(n^2)になる。ヒープソートはヒープ構造により「最大値の取り出しがO(log n)」で済むためO(n log n)に改善される。ヒープソートは選択ソートの「最小値探索」をヒープで高速化したものとも言える。

挿入ソート vs クイックソート

挿入ソートO(n^2)は各要素を1つずつ正しい位置に挿入する逐次的な処理。クイックソートO(n log n)はパーティションにより複数の要素を一度に大まかな位置に配置する。ただし、要素数が少ない（おおよそ10以下）場合は、挿入ソートの方がオーバーヘッドが少なく速い。

探索アルゴリズム

データの中から特定の値を見つけ出す「探索」は、ソートと並んで基本的な操作である。

線形探索 -- O(n)

仕組み

配列の先頭から順に、目的の値と一致するかを1つずつ確認する。最もシンプルな探索方法である。

JavaScript実装

function linearSearch(arr, target) {
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] === target) {
      return i; // 見つかったインデックスを返す
    }
  }
  return -1; // 見つからなかった場合
}

使いどころ

  • データが少ない場合（数十件程度）
  • データがソートされていない場合
  • 探索が1回しか行われない場合

データが少なければ、二分探索のための前処理（ソート）の方がコストが高くなるため、線形探索が最適な場合もある。

二分探索 -- O(log n)

仕組み

ソート済みの配列に対して使える高速な探索方法である。

  1. 配列の中央の要素を確認する
  2. 目的の値が中央より小さければ左半分を、大きければ右半分を探索する
  3. 範囲が1要素になるまで繰り返す

毎回探索範囲が半分になるため、O(log n)で済む。

「電話帳で名前を探す」例え

電話帳から「山田」さんを探すとき、先頭から順にめくる人はいない。まず真ん中あたりを開き、「ま行」だったら後半を探し、「や行」が出てきたら「や」の付近を詳しく見る。これが二分探索の考え方である。

1000ページの電話帳でも、10回ページをめくれば目的の名前にたどり着ける（2^10 = 1024）。

JavaScript実装

function binarySearch(arr, target) {
  let left = 0;
  let right = arr.length - 1;

  while (left <= right) {
    const mid = Math.floor((left + right) / 2);

    if (arr[mid] === target) {
      return mid;
    } else if (arr[mid] < target) {
      left = mid + 1; // 右半分を探索
    } else {
      right = mid - 1; // 左半分を探索
    }
  }
  return -1;
}

前提条件: ソート済みであること

二分探索は配列がソート済みでないと正しく動作しない。これは最も重要な前提条件である。ソートされていない配列に二分探索を適用すると、間違った結果が返る可能性がある。

探索を何度も行う場合は「O(n log n)で一度ソートし、その後はO(log n)で探索」という戦略が有効である。

ハッシュ探索 -- O(1)

ハッシュテーブルの仕組み

ハッシュ探索は**ハッシュテーブル（Hash Table）**を使った探索方法である。JavaScriptではObjectやMapがハッシュテーブルに相当する。

ハッシュテーブルは「キーからハッシュ関数でインデックスを計算し、そのインデックスに値を格納する」データ構造である。

キー "apple" → ハッシュ関数 → インデックス 3 → テーブル[3]に格納
キー "banana" → ハッシュ関数 → インデックス 7 → テーブル[7]に格納

探索時もキーからインデックスを計算するだけなので、O(1)（定数時間）でアクセスできる。

JavaScript実装

// ハッシュテーブルの構築と探索
function hashSearch(arr, target) {
  // 構築: O(n)
  const hashTable = new Map();
  for (let i = 0; i < arr.length; i++) {
    hashTable.set(arr[i], i);
  }

  // 探索: O(1)
  if (hashTable.has(target)) {
    return hashTable.get(target);
  }
  return -1;
}

衝突（コリジョン）の概念

異なるキーが同じインデックスに割り当てられることを**衝突（コリジョン）**という。衝突が多発すると、最悪の場合O(n)に退化する。

衝突の解決方法には以下がある。

  • チェイン法: 同じインデックスにリンクリストで複数の値を格納する
  • オープンアドレス法: 衝突した場合、別の空きインデックスを探す

構築コスト vs 探索コスト

ハッシュテーブルの構築にはO(n)のコストがかかる。そのため、1回だけの探索なら線形探索O(n)と変わらない。ハッシュ探索が有利になるのは、同じデータに対して何度も探索を行う場合である。

探索アルゴリズム比較表

アルゴリズム探索時間前提条件追加メモリ使いどころ
線形探索O(n)なしO(1)少量データ、1回限りの探索
二分探索O(log n)ソート済みO(1)ソート済みデータへの繰り返し探索
ハッシュ探索O(1)平均なしO(n)大量データへの頻繁な探索

探索比較ペアの解説

線形探索 vs 二分探索

線形探索は先頭から順に見るためO(n)。二分探索は毎回半分に絞り込むためO(log n)。100万件のデータでは、線形探索が平均50万回の比較を必要とするのに対し、二分探索はわずか20回で済む。ただし二分探索にはソート済みという前提が必要である。

線形探索 vs ハッシュ探索

線形探索O(n)は前処理不要だが探索のたびに全件走査する。ハッシュ探索O(1)は構築にO(n)かかるが、以降の探索は定数時間。探索回数が多い場面ではハッシュ探索が圧倒的に有利である。

二分探索 vs ハッシュ探索

二分探索O(log n)は追加メモリが不要だが、ソート済み配列が必要。ハッシュ探索O(1)は追加メモリO(n)が必要だが、前提条件がない。メモリに余裕がありソート状態を維持できない場合はハッシュ探索、メモリを節約したい場合は二分探索が適する。

数値計算アルゴリズム

ビジュアライザでは、同じ問題を「素朴な方法」と「効率的な方法」で解く3つの比較を体験できる。

フィボナッチ数列: 再帰O(2^n) vs 動的計画法O(n)

フィボナッチ数列とは

フィボナッチ数列は、最初の2項が0と1で、以降の各項が直前の2項の和であるような数列である。

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...

数学的には F(n) = F(n-1) + F(n-2)、F(0) = 0、F(1) = 1 と定義される。

素朴な再帰実装 -- O(2^n)

定義をそのままコードにすると、以下のようになる。

function fibRecursive(n) {
  if (n <= 1) return n;
  return fibRecursive(n - 1) + fibRecursive(n - 2);
}

一見シンプルだが、このコードには重大な問題がある。

重複計算の問題

fib(5) を計算する場合の呼び出しを図で表すと、以下のようになる。

                    fib(5)
                   /      \
              fib(4)        fib(3)
             /     \        /     \
         fib(3)   fib(2)  fib(2)  fib(1)
        /    \    /    \   /    \
    fib(2) fib(1) fib(1) fib(0) fib(1) fib(0)
    /    \
fib(1) fib(0)

fib(3) が2回、fib(2) が3回、fib(1) が5回呼ばれている。nが大きくなるほどこの重複は爆発的に増え、計算量はO(2^n)になる。n=50を計算しようとすると、約1000兆回の関数呼び出しが必要になり、通常のコンピュータでは終わらない。

動的計画法（DP）による実装 -- O(n)

**動的計画法（Dynamic Programming, DP）**は、計算結果を保存して再利用する手法である。一度計算したfib(k)の結果を記録しておき、2回目以降はその記録を参照する。

// ボトムアップDP（タビュレーション）
function fibDP(n) {
  if (n <= 1) return n;

  const dp = new Array(n + 1);
  dp[0] = 0;
  dp[1] = 1;

  for (let i = 2; i <= n; i++) {
    dp[i] = dp[i - 1] + dp[i - 2];
  }
  return dp[n];
}

さらにメモリを節約するなら、直前の2つの値だけを保持すればよい。

// 空間最適化版: O(1)のメモリで計算
function fibOptimized(n) {
  if (n <= 1) return n;

  let prev2 = 0;
  let prev1 = 1;

  for (let i = 2; i <= n; i++) {
    const current = prev1 + prev2;
    prev2 = prev1;
    prev1 = current;
  }
  return prev1;
}

メモ化（トップダウンDP）

再帰の構造を保ちつつ、計算結果をキャッシュする方法もある。これを**メモ化（Memoization）**という。

function fibMemo(n, memo = {}) {
  if (n <= 1) return n;
  if (memo[n] !== undefined) return memo[n];

  memo[n] = fibMemo(n - 1, memo) + fibMemo(n - 2, memo);
  return memo[n];
}

再帰O(2^n)とDP O(n)の差は、ビジュアライザでn=30程度にすると劇的に体感できるはずである。

べき乗計算: 素朴法O(n) vs 繰り返し二乗法O(log n)

問題

x^n（xのn乗）を効率的に計算するにはどうすればよいか。

素朴な方法 -- O(n)

xをn回掛ける方法。

function powerNaive(x, n) {
  let result = 1;
  for (let i = 0; i < n; i++) {
    result *= x;
  }
  return result;
}

n=1000なら1000回の掛け算が必要。

繰り返し二乗法 -- O(log n)

指数を2進数で分解し、二乗を繰り返すことで計算回数を大幅に削減する手法である。

考え方: x^10 = x^8 * x^2（10を2進数で表すと1010）

  • x^1 → x^2 → x^4 → x^8 と二乗していく
  • 10の2進表現 1010 の「1」が立っている桁に対応する値を掛け合わせる
function powerFast(x, n) {
  let result = 1;
  let base = x;

  while (n > 0) {
    if (n % 2 === 1) {
      result *= base; // nの2進表現の現在の桁が1なら掛ける
    }
    base *= base; // baseを二乗
    n = Math.floor(n / 2);
  }
  return result;
}

n=1000の場合、素朴法は1000回の掛け算だが、繰り返し二乗法はわずか約10回（log2(1000) ≒ 10）で済む。

暗号処理での応用

RSA暗号などの公開鍵暗号では、非常に大きな数のべき乗を計算する必要がある（たとえば x^65537 mod m）。素朴法では65537回の掛け算が必要だが、繰り返し二乗法なら17回（log2(65537) ≒ 17）で済む。暗号処理の実用性を支える重要なアルゴリズムである。

素数列挙: 試し割りO(n*sqrt(n)) vs エラトステネスの篩O(n log log n)

問題

n以下のすべての素数を列挙するにはどうすればよいか。

試し割り

各数について、2からsqrt(n)までの数で割り切れるかを確認する方法。

function trialDivision(n) {
  const primes = [];
  for (let num = 2; num <= n; num++) {
    let isPrime = true;
    for (let div = 2; div * div <= num; div++) {
      if (num % div === 0) {
        isPrime = false;
        break;
      }
    }
    if (isPrime) primes.push(num);
  }
  return primes;
}

各数に対してsqrt(num)回の割り算を行うため、全体でO(n * sqrt(n))程度かかる。

エラトステネスの篩 -- O(n log log n)

紀元前3世紀のギリシャの数学者エラトステネスが考案した方法で、2000年以上前のアルゴリズムが現代でも使われている。

手順:

  1. 2からnまでの数を並べる
  2. 最小の数（2）を素数として確定し、その倍数をすべて消す
  3. 次に残っている最小の数（3）を素数として確定し、その倍数を消す
  4. これをsqrt(n)まで繰り返す
  5. 残った数がすべて素数
初期状態: [2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]

2の倍数を消す: [2, 3, _, 5, _, 7, _, 9, __, 11, __, 13, __, 15]
3の倍数を消す: [2, 3, _, 5, _, 7, _, _, __, 11, __, 13, __, __]

結果: [2, 3, 5, 7, 11, 13]

function sieveOfEratosthenes(n) {
  // trueで初期化（trueは「素数の候補」を意味する）
  const isPrime = new Array(n + 1).fill(true);
  isPrime[0] = false;
  isPrime[1] = false;

  for (let i = 2; i * i <= n; i++) {
    if (isPrime[i]) {
      // iの倍数をすべて消す（i*iから始める最適化）
      for (let j = i * i; j <= n; j += i) {
        isPrime[j] = false;
      }
    }
  }

  const primes = [];
  for (let i = 2; i <= n; i++) {
    if (isPrime[i]) primes.push(i);
  }
  return primes;
}

篩（ふるい）の計算量O(n log log n)は、ほぼO(n)に近い。試し割りO(n * sqrt(n))と比べて、特にnが大きい場合に顕著な速度差が出る。

応用アルゴリズム

ここからは、コーディング面接でも頻出の実践的な問題を取り上げる。

最大部分配列: 全探索O(n^2) vs カダネのアルゴリズムO(n)

問題

整数の配列から、連続する部分配列の和が最大となるものを見つけよ。

例: [-2, 1, -3, 4, -1, 2, 1, -5, 4] → 最大部分配列は [4, -1, 2, 1] で和は6。

全探索 -- O(n^2)

すべての開始位置と終了位置の組み合わせを試す。

function maxSubarrayBruteForce(arr) {
  let maxSum = -Infinity;
  const n = arr.length;

  for (let i = 0; i < n; i++) {
    let currentSum = 0;
    for (let j = i; j < n; j++) {
      currentSum += arr[j];
      maxSum = Math.max(maxSum, currentSum);
    }
  }
  return maxSum;
}

カダネのアルゴリズム -- O(n)

**カダネのアルゴリズム（Kadane's Algorithm）**は、配列を一度走査するだけで最大部分配列和を求める。

考え方: 各位置iにおいて「位置iで終わる部分配列の最大和」を考える。これは「直前までの最大和 + 現在の要素」と「現在の要素のみ」の大きい方である。

function maxSubarrayKadane(arr) {
  let maxSum = arr[0];
  let currentSum = arr[0];

  for (let i = 1; i < arr.length; i++) {
    // 「直前の部分配列を延長する」か「ここから新しく始める」か
    currentSum = Math.max(arr[i], currentSum + arr[i]);
    maxSum = Math.max(maxSum, currentSum);
  }
  return maxSum;
}

なぜ効率的なのか: 全探索では「どこからどこまで」のすべての組み合わせを試すが、カダネのアルゴリズムでは「直前までの最大和がマイナスなら捨てて新しく始める」という判断により、1回の走査で答えが出る。

Two Sum（二数の和）: 全探索O(n^2) vs ハッシュO(n)

問題

整数の配列と目標値targetが与えられたとき、和がtargetになる2つの要素のインデックスを見つけよ。

例: nums = [2, 7, 11, 15], target = 9 → [0, 1]（2 + 7 = 9）

この問題はLeetCodeで最も有名な問題であり、コーディング面接では定番中の定番である。

全探索 -- O(n^2)

すべてのペアを試す。

function twoSumBruteForce(nums, target) {
  for (let i = 0; i < nums.length; i++) {
    for (let j = i + 1; j < nums.length; j++) {
      if (nums[i] + nums[j] === target) {
        return [i, j];
      }
    }
  }
  return [];
}

二重ループなのでO(n^2)。

ハッシュテーブルを使う方法 -- O(n)

「target - nums[i]」がすでに出現済みかをハッシュテーブルで確認する。

function twoSumHash(nums, target) {
  const map = new Map(); // 値 → インデックス

  for (let i = 0; i < nums.length; i++) {
    const complement = target - nums[i];

    if (map.has(complement)) {
      return [map.get(complement), i];
    }

    map.set(nums[i], i);
  }
  return [];
}

なぜ効率的なのか: 全探索では「ペアの片方を固定し、もう片方を全件走査」するためO(n^2)。ハッシュ版では「ペアの片方を固定し、もう片方をO(1)で検索」するためO(n)になる。

コーディング面接でのTips

Two Sumは面接で以下のポイントが評価される。

  1. まず素朴な解法を説明する: いきなり最適解を出すより、「O(n^2)の方法は思いつきますが、ハッシュテーブルでO(n)に改善できます」と段階的に説明する方が好印象
  2. エッジケースを考慮する: 同じ要素を2回使ってよいか、答えが複数あるか、答えがない場合はどうするか
  3. 空間と時間のトレードオフを説明する: ハッシュテーブルはO(n)の追加メモリが必要だが、時間計算量をO(n^2)からO(n)に改善できる
  4. ソート+両端ポインタという別解も知っておく: O(n log n)の解法だが、追加メモリがO(1)で済むため、メモリ制約がある場合に有用
// ソート+両端ポインタによるTwo Sum（インデックスではなく値を返す場合）
function twoSumSorted(nums, target) {
  const sorted = [...nums].sort((a, b) => a - b);
  let left = 0;
  let right = sorted.length - 1;

  while (left < right) {
    const sum = sorted[left] + sorted[right];
    if (sum === target) return [sorted[left], sorted[right]];
    if (sum < target) left++;
    else right--;
  }
  return [];
}

重複検出: 二重ループO(n^2) vs ソート+走査O(n log n)

問題

配列内に重複する要素があるかを判定せよ。

例: [1, 2, 3, 1] → true、[1, 2, 3, 4] → false

二重ループ -- O(n^2)

すべてのペアを比較する。

function hasDuplicateBruteForce(arr) {
  for (let i = 0; i < arr.length; i++) {
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[i] === arr[j]) {
        return true;
      }
    }
  }
  return false;
}

ソート+走査 -- O(n log n)

配列をソートすると、重複する要素は必ず隣り合う。そのため、隣接要素を比較するだけで重複を検出できる。

function hasDuplicateSort(arr) {
  const sorted = [...arr].sort((a, b) => a - b); // O(n log n)

  for (let i = 1; i < sorted.length; i++) { // O(n)
    if (sorted[i] === sorted[i - 1]) {
      return true;
    }
  }
  return false;
}

全体の計算量はソートのO(n log n)が支配的。

なお、ハッシュテーブル（Set）を使えばO(n)にもできる。

function hasDuplicateHash(arr) {
  const seen = new Set();
  for (const num of arr) {
    if (seen.has(num)) return true;
    seen.add(num);
  }
  return false;
}

なぜソート版が効率的なのか: 二重ループでは「すべてのペア」を比較する必要があるが、ソートにより「隣接ペアだけ」を見れば十分になる。比較対象をO(n^2)からO(n)に削減できるわけである（ソート自体のコストO(n log n)は含む）。

回文判定: 反転比較O(n) vs 両端ポインタO(n/2)

問題

文字列が回文（前から読んでも後ろから読んでも同じ）かどうかを判定せよ。

例: "racecar" → true、"hello" → false

反転比較 -- O(n)

文字列を反転させて元の文字列と比較する。

function isPalindromeReverse(str) {
  const reversed = str.split("").reverse().join("");
  return str === reversed;
}

splitでO(n)、reverseでO(n)、joinでO(n)、比較でO(n)。合計O(n)だが、定数倍が大きい。また、反転した文字列を格納するためのO(n)の追加メモリが必要である。

両端ポインタ -- O(n/2)

先頭と末尾から同時に内側へ向かって比較する。

function isPalindromeTwoPointer(str) {
  let left = 0;
  let right = str.length - 1;

  while (left < right) {
    if (str[left] !== str[right]) {
      return false;
    }
    left++;
    right--;
  }
  return true;
}

O記法ではO(n/2)もO(n)として扱う（定数倍を無視するため）。しかし実測では約半分のステップで済み、追加メモリもO(1)で済む。回文でない文字列に対しては、不一致が見つかった時点で即座に終了できるため、平均的にはさらに速い。

なぜ両端ポインタが効率的か

反転比較は「文字列全体のコピーを作ってから全体を比較」する。両端ポインタは「コピーを作らず、必要最小限の比較だけ行う」。O記法上は同じO(n)だが、実際のプログラムでは定数倍やメモリ使用量の差が性能に影響する。

計算量を改善するための5つのテクニック

ここまでの内容を踏まえ、計算量を改善するための汎用的なテクニックを5つ紹介する。コーディング面接や実務で「もっと速い方法はないか」と考えるときの指針にしてほしい。

1. ソートして二分探索 -- O(n^2)をO(n log n)に

「配列から特定の条件を満たす要素を探す」問題で、全探索O(n^2)をソート+二分探索でO(n log n)に改善できるケースは多い。

// 例: 配列内にtarget - arr[i]が存在するか調べる
function findPairSorted(arr, target) {
  arr.sort((a, b) => a - b); // O(n log n)

  for (let i = 0; i < arr.length; i++) { // O(n)
    const complement = target - arr[i];
    // 二分探索で complement を探す: O(log n)
    if (binarySearch(arr, complement) !== -1) {
      return true;
    }
  }
  return false;
}
// 全体: O(n log n) + O(n log n) = O(n log n)

適用場面: 「ある値が存在するか」を繰り返し確認する問題全般。

2. ハッシュテーブル -- O(n^2)をO(n)に

「2つの要素の関係を調べる」問題で、片方をハッシュテーブルに格納しておくことで、もう片方の検索をO(1)にできる。

// 例: 2つの配列に共通する要素を見つける
function findCommon(arr1, arr2) {
  const set = new Set(arr1); // O(n)
  return arr2.filter((x) => set.has(x)); // O(m)
}
// 二重ループならO(n*m)だが、これはO(n+m)

適用場面: Two Sum、重複検出、アナグラム判定、頻度カウントなど。

3. 分割統治法 -- O(n^2)をO(n log n)に

問題を半分ずつに分割し、再帰的に解く。マージソートやクイックソートがこの典型である。

// 分割統治の基本構造
function divideAndConquer(problem) {
  // ベースケース
  if (problem.size <= 1) return solve(problem);

  // 分割
  const [left, right] = split(problem);

  // 再帰
  const leftResult = divideAndConquer(left);
  const rightResult = divideAndConquer(right);

  // 統合
  return combine(leftResult, rightResult);
}

適用場面: ソート、最近接点対問題、行列乗算（ストラッセン法）など。

4. 動的計画法/メモ化 -- O(2^n)をO(n)に

同じ部分問題を何度も解いてしまう再帰を、計算結果のキャッシュで劇的に改善する。

// 動的計画法の基本パターン
function dpSolve(n) {
  const dp = new Array(n + 1).fill(0);

  // ベースケース
  dp[0] = baseCase0;
  dp[1] = baseCase1;

  // ボトムアップで計算
  for (let i = 2; i <= n; i++) {
    dp[i] = dp[i - 1] + dp[i - 2]; // 漸化式
  }
  return dp[n];
}

適用場面: フィボナッチ数列、ナップサック問題、最長共通部分列、コイン問題など。

DPを適用できるかどうかは、以下の2つの性質があるかで判断する。

  • 最適部分構造: 問題の最適解が、部分問題の最適解から構成できる
  • 重複する部分問題: 同じ部分問題が何度も現れる

5. 両端ポインタ/スライディングウィンドウ -- O(n^2)をO(n)に

ソート済み配列や連続部分配列に対して、2つのポインタを使って効率的に走査するテクニック。

// 両端ポインタの例: ソート済み配列で和がtargetになるペアを探す
function twoPointer(sortedArr, target) {
  let left = 0;
  let right = sortedArr.length - 1;

  while (left < right) {
    const sum = sortedArr[left] + sortedArr[right];
    if (sum === target) return [left, right];
    if (sum < target) left++;
    else right--;
  }
  return [-1, -1];
}

// スライディングウィンドウの例: 長さkの部分配列の最大和
function maxSumWindow(arr, k) {
  let windowSum = 0;
  for (let i = 0; i < k; i++) {
    windowSum += arr[i];
  }

  let maxSum = windowSum;
  for (let i = k; i < arr.length; i++) {
    windowSum += arr[i] - arr[i - k]; // 右端を追加、左端を除去
    maxSum = Math.max(maxSum, windowSum);
  }
  return maxSum;
}

適用場面: ソート済み配列でのペア探索、部分文字列問題、コンテナ問題など。

テクニック選択のフローチャート

問題に直面したとき、以下の順で考えるとよい。

1. 入力データにソートなど前提条件はあるか?
   → ある場合: 二分探索や両端ポインタを検討

2. 「値の存在チェック」や「値の出現回数」が必要か?
   → 必要な場合: ハッシュテーブルを検討

3. 問題を半分に分割できるか?
   → 分割できる場合: 分割統治法を検討

4. 同じ計算を繰り返していないか?
   → 繰り返している場合: DP/メモ化を検討

5. 連続する部分配列/部分文字列を扱うか?
   → 扱う場合: スライディングウィンドウを検討

まとめ

本記事では、ビジュアライザに登場する20の比較問題を通して、以下の内容を解説した。

  • O記法の基本: 計算量の表現方法とその重要性
  • ソートアルゴリズム6種: バブル、選択、挿入のO(n^2)組と、クイック、マージ、ヒープのO(n log n)組
  • 探索アルゴリズム3種: 線形O(n)、二分O(log n)、ハッシュO(1)
  • 数値計算3組: フィボナッチ、べき乗、素数列挙における素朴法と効率的手法の比較
  • 応用問題4組: 最大部分配列、Two Sum、重複検出、回文判定
  • 計算量改善の5つのテクニック: ソート+二分探索、ハッシュ、分割統治、DP、両端ポインタ

アルゴリズムの理解を深めるには、コードを読むだけでなく実際に動かして観察することが最も効果的である。

アルゴリズム計算量ビジュアライザで実際に動かしてみる

ビジュアライザで各アルゴリズムの動きを確認し、データ数を変えたときの速度差を体感してほしい。「O(n^2)とO(n log n)の差がどれだけ大きいか」を目で見れば、教科書の数式が実感に変わるはずである。

参考リンク

  • アルゴリズム計算量ビジュアライザ -- 本記事で解説したアルゴリズムを視覚的に比較できるツール
  • Big-O Cheat Sheet -- 各アルゴリズムの計算量を一覧できるリファレンスシート
  • VisuAlgo -- アルゴリズムの可視化ツール（英語）
  • AtCoder -- 競技プログラミングサイト。アルゴリズムの実践練習に最適
  • LeetCode -- コーディング面接対策の定番サイト。Two Sumをはじめとする問題が豊富