プロローグ ── 計算量という「設計言語」を身につける

シリーズ構成（全12章）

Part 1 — 計算量と基本データ構造 Ch.1 プロローグ（本章） / Ch.2 配列とハッシュテーブル / Ch.3 連結リスト・スタック・キュー / Ch.4 木構造（BST・AVL・Red-Black Tree） / Ch.5 ヒープと優先度付きキュー

Part 2 — グラフとアルゴリズム設計 Ch.6 グラフの表現とトラバーサル / Ch.7 ソートアルゴリズム / Ch.8 二分探索とその応用 / Ch.9 動的計画法

Part 3 — 実務のデータ構造 Ch.10 B-Tree / LSM-Tree / Skip List / Ch.11 確率的データ構造 / Ch.12 エピローグ

---

この記事で何を扱うか

「この処理は O(n²) だからダメだ」──こういう会話をチームでしたことはないだろうか。

計算量（Big O）はエンジニアの共通言語だ。しかし「O(n²) がなぜダメか」を感覚的に理解している人は多くても、「ではどうすれば O(n log n) や O(1) にできるか」──つまり適切なデータ構造を選ぶ力──を体系的に持っている人は意外と少ない。

このシリーズでは、データ構造とアルゴリズムを以下の視点で扱う。

• なぜそのデータ構造が存在するのか（どんな問題を解決するために発明されたか）
• 内部でどう動いているのか（ブラックボックスにしない）
• 実際のシステムのどこで使われているか（理論と実務の橋渡し）

---

対象読者

対象：実務経験1〜5年のソフトウェアエンジニア
      「配列とハッシュマップは使えるが、なぜ速いかは説明できない」という方
      コーディング面接の準備をしている方
難易度：★★★☆☆
読了時間：約4時間（全章通読時）
前提知識：何かしらのプログラミング言語でコードが書ける

---

Big O 記法：「最悪どれくらいかかるか」の言語

Big O は入力サイズ n が十分大きいとき、処理時間がどう増加するかを表す。

# O(1) — 定数時間：入力サイズに関係なく一定
def get_first(arr):
    return arr[0]

# O(log n) — 対数時間：入力が2倍になっても、処理は1ステップ増えるだけ
def binary_search(arr, target):
    lo, hi = 0, len(arr) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

# O(n) — 線形時間：入力に比例
def find_max(arr):
    return max(arr)

# O(n log n) — 線形対数時間：効率的なソートの典型
def sort_it(arr):
    return sorted(arr)  # Timsort: O(n log n)

# O(n²) — 二次時間：二重ループ
def has_duplicate_naive(arr):
    for i in range(len(arr)):
        for j in range(i + 1, len(arr)):
            if arr[i] == arr[j]:
                return True
    return False

# O(2^n) — 指数時間：部分集合の列挙
def all_subsets(arr):
    if not arr:
        return [[]]
    rest = all_subsets(arr[1:])
    return rest + [[arr[0]] + s for s in rest]

直感的なスケール感

n = 1,000,000（100万）のとき：

計算量	操作数	1GHz CPU での概算
O(1)	1	1 ns
O(log n)	20	20 ns
O(n)	1,000,000	1 ms
O(n log n)	20,000,000	20 ms
O(n²)	1,000,000,000,000	16 分
O(2^n)	宇宙が終わっても終わらない	—

O(n²) と O(n log n) の差は「1000倍」ではなく「5万倍」になる。n が大きくなるほどこの差は広がる。

---

空間計算量：メモリも計算量の一部

時間だけでなく、使用メモリも計算量で評価する。

# O(1) 空間：追加メモリなし
def sum_array(arr):
    total = 0  # 定数個の変数
    for x in arr:
        total += x
    return total

# O(n) 空間：入力サイズに比例するメモリ
def reverse_array(arr):
    return arr[::-1]  # 新しい配列を作成

# O(n) 空間 → O(1) 空間に最適化
def reverse_in_place(arr):
    lo, hi = 0, len(arr) - 1
    while lo < hi:
        arr[lo], arr[hi] = arr[hi], arr[lo]
        lo += 1
        hi -= 1

時間と空間のトレードオフ：ハッシュテーブルは O(n) のメモリを使うことで検索を O(1) にする。メモ化は O(n) のメモリで再計算を O(1) にする。「メモリを使って時間を買う」のは設計の常套手段だ。

---

償却計算量（Amortized Complexity）

Python の list.append() は O(1) か？

内部的な動作：
  配列の容量が足りなくなると、2倍の容量で再確保してコピーする
  → その1回は O(n)
  
  しかし、n 回の append で再確保は log(n) 回しか起きない
  → n 回の操作の合計は O(n)
  → 1回あたりの平均は O(n) / n = O(1)
  
  これを「償却 O(1)」（amortized O(1)）と呼ぶ

ハッシュテーブルのリハッシュも同じ原理だ。たまに O(n) かかるが、平均すると O(1) に収まる。

---

データ構造の選択マップ

このシリーズで扱うデータ構造を「何が得意か」で整理する。

「キーで高速に検索したい」
  → ハッシュテーブル（Ch.2）  O(1) 平均
  → BST / AVL（Ch.4）       O(log n) + 順序付き

「最大値 / 最小値を高速に取りたい」
  → ヒープ（Ch.5）           O(1) で取得、O(log n) で追加

「順序付きデータを高速に検索したい」
  → 二分探索（Ch.8）          O(log n)
  → B-Tree（Ch.10）          ディスクI/O最適化

「FIFO / LIFO で処理したい」
  → キュー / スタック（Ch.3）  O(1)

「グラフの経路や関係を探索したい」
  → グラフ + BFS/DFS（Ch.6）  O(V + E)

「ソートしたい」
  → ソートアルゴリズム（Ch.7） O(n log n)

「存在するか高速に判定したい（近似でOK）」
  → Bloom Filter（Ch.11）     O(k) で判定、省メモリ

---

このシリーズの読み方

各章は以下の構造で書かれている。

1. そのデータ構造が「何を解決するか」
2. 内部動作の図解とコード実装
3. 計算量の分析（なぜその計算量になるか）
4. 実際のシステムでの使用例
5. よくある面接問題と解法

コードは全て Python で書いている。言語依存の部分はほぼないので、他言語ユーザーもそのまま読める。

では、最も基本的なデータ構造──配列とハッシュテーブル──から始めよう。

＋ － ⟳ ✕