第 7 章データ構造とアルゴリズム¶

まえがき — 同じ問題でも、桁違いに差が出る¶

100 万人のユーザーリストから「特定のユーザー」を探すとき、普通の配列を線形に探すのとハッシュテーブルで探すのとでは、検索時間が 数十万倍 違います。データが多くなればなるほど、その差は致命的になります。

エンジニアの仕事の半分は「動くコードを書くこと」、もう半分は「速く・正しく・読みやすく動くコードを書くこと」。データ構造とアルゴリズムは、その後者を支える基礎技術です。

🎯 章の目標

主要なデータ構造（配列、リスト、ハッシュ、木、ヒープ、グラフ）の動作と計算量を理解する

\(O(n^2)\) と \(O(n \log n)\) の違いを実感し、適切なものを選べる

設計技法（分割統治・動的計画法・貪欲法・バックトラック）を使い分けられる

グラフアルゴリズム（BFS・DFS・Dijkstra）を実装できる

「これは DP に帰着できる」「これは BFS で解ける」と問題を分類する嗅覚を身につける

7.1 計算量とは — 「速い・遅い」を数値化する¶

7.1.1 ランダウの O 記法¶

入力サイズ \(n\) に対する操作回数を関数で表します。定数倍と低次項を無視 するのが O 記法。

例: - 線形探索: \(O(n)\) - 二分探索: \(O(\log n)\) - バブルソート: \(O(n^2)\) - マージソート: \(O(n \log n)\) - 全探索 (TSP): \(O(n!)\)

7.1.2 グラフで見る計算量の差¶

\(n = 1000\) で考えると:

計算量	\(n=1000\) での操作数	体感
\(O(1)\)	1	一瞬
\(O(\log n)\)	10	一瞬
\(O(n)\)	1,000	一瞬
\(O(n \log n)\)	10,000	一瞬
\(O(n^2)\)	1,000,000	0.1 秒
\(O(n^3)\)	10億	数十分
\(O(2^n)\)	\(10^{300}\)	宇宙の年齢より長い
\(O(n!)\)	さらに大きい	計算不能

時間
 ^
 |          O(n!)     O(2^n)
 |          ／         ／
 |        ／         ／
 |      ／         ／              O(n²)
 |    ／         ／                ／
 |  ／         ／              ／
 |／         ／              ／              O(n log n)
 |        ／              ／              ／
 |      ／              ／              ／
 |    ／              ／              ／                  O(n)
 |  ／              ／              ／                  ／
 |／              ／              ／                  ／       O(log n)
 +─────────────────────────────────────────────────────────────→ n
 O

「遅くて済むコード」と「速いコード」の差は、\(n\) が大きくなるほど 爆発的に開く。これがアルゴリズムを学ぶ最大の理由。

7.1.3 マスター定理¶

再帰式 \(T(n) = aT(n/b) + f(n)\) の閉形を与えます。

例: - マージソート: \(T(n) = 2T(n/2) + O(n) = O(n \log n)\) - 二分探索: \(T(n) = T(n/2) + O(1) = O(\log n)\)

7.1.4 償却計算量¶

「たまに重いが、平均すれば軽い」操作の評価。

例: 動的配列の push - 容量に余裕があれば \(O(1)\) - 容量超過時は倍に拡張 \(O(n)\) - でも全体平均は \(O(1)\) 償却

「バンカー法」「ポテンシャル法」で証明します。

7.2 線形構造¶

7.2.1 配列 (Array)¶

連続したメモリ。インデックスアクセス \(O(1)\)、要素挿入・削除 \(O(n)\)。

メリット: キャッシュ局所性が良い (第 9 章)。デメリット: サイズが固定。

arr = [1, 2, 3, 4, 5]
print(arr[2])   # O(1)

7.2.2 動的配列¶

容量不足時に倍々に拡張。push は 償却 \(O(1)\)。

Python の list
Java の ArrayList
C++ の vector
Go の slice

「配列を使うべきか、連結リストを使うべきか」で迷ったら、ほとんどの場合 配列が勝ち。キャッシュ効率が劇的に違うから。

7.2.3 連結リスト (Linked List)¶

各要素が next ポインタで次を指す。

[1] → [2] → [3] → [4] → null

挿入・削除: 位置がわかれば \(O(1)\)
ランダムアクセス: \(O(n)\)
単方向、双方向、循環

class Node:
    def __init__(self, val):
        self.val = val
        self.next = None

実務では配列のほうが速いことが多いですが、OS のスケジューラやメモリアロケータで連結リストは健在。

7.2.4 スタック・キュー・デック¶

スタック (LIFO): 関数呼び出し、式評価、DFS。push/pop。
キュー (FIFO): タスクキュー、BFS、メッセージング。enqueue/dequeue。
デック: 両端で push/pop。スライディングウィンドウ最大値。

from collections import deque
stack = []
stack.append(1); stack.pop()    # LIFO

queue = deque()
queue.append(1); queue.popleft()  # FIFO

7.2.5 ハッシュテーブル — 平均 \(O(1)\) の衝撃¶

キーをハッシュ関数で「バケット番号」に変換し、そこに格納:

キー "apple" → ハッシュ → 7 → バケット[7] に格納

検索・挿入・削除すべて 平均 \(O(1)\)
最悪 \(O(n)\)（衝突がひどいとき）
ロードファクタが大きくなるとリハッシュ

衝突解決: - チェイン法: バケットに連結リストを保持 - オープンアドレス法: 衝突したら次の空きスロットへ

応用: 連想配列 (dict, Map)、データベースインデックス、キャッシュ、ブルームフィルタ、ビットコインのマイニング。

🧠 ここで考えてみよう ハッシュテーブルが「\(O(1)\) で動く理由」を、「キー数 \(n\)、バケット数 \(m\)、平均で 1 バケットに何個」の議論で説明できますか?

7.3 木構造¶

7.3.1 用語¶

       根 (root)
        │
     ┌──┴──┐
    左の子  右の子
     │
   ┌─┴─┐
   葉  葉

根、葉、親、子、兄弟、深さ、高さ
二分木: 子が高々 2
完全二分木: すべての階層が満たされている

7.3.2 二分探索木 (BST)¶

ルール: 「左の部分木 < ノード < 右の部分木」

def search(node, x):
    if node is None: return None
    if x == node.val: return node
    if x < node.val: return search(node.left, x)
    return search(node.right, x)

検索・挿入・削除: \(O(h)\)（\(h\) = 高さ）
バランスが取れていれば \(O(\log n)\)
偏ると最悪 \(O(n)\)

7.3.3 平衡木¶

自動でバランスを保つ木。

AVL 木: 厳格にバランス、高さ差が 1 以下
赤黒木: 緩めにバランス、Linux カーネル・Java TreeMap で活躍
B 木 / B+ 木: 各ノードに多数の子。データベース・ファイルシステム

B+ 木の例 (順序 4):

        [10, 20, 30]
       /    |   |   \
   [1,5] [11,15] [21,25] [31,40]

データベースのインデックスはほとんど B+ 木。ディスク I/O を最小化する設計です。

7.3.4 ヒープ¶

「親 ≤ 子」を保つ完全二分木 (最小ヒープ)。配列で実装。

最小ヒープのイメージ:

graph TD
    A((1))
    B((3))
    C((5))
    D((7))
    E((4))
    F((8))
    G((9))
    A --> B
    A --> C
    B --> D
    B --> E
    C --> F
    C --> G

    style A fill:#ffeb3b

「親 ≤ 子」が常に成り立ちます。根 (1) が最小。挿入・削除のたびに上下に動かして性質を保ちます。

push/pop: \(O(\log n)\)
最小値取得: \(O(1)\)

応用: 優先度付きキュー、Dijkstra、トップ K、タスクスケジューリング。

import heapq
h = []
heapq.heappush(h, 5)
heapq.heappush(h, 1)
heapq.heappush(h, 3)
print(heapq.heappop(h))   # 1 (最小)

7.3.5 Trie (基数木)¶

文字列をエッジに持つ木。プレフィックス検索が \(O(L)\) (\(L\) = 文字列長)。

   r
   │
   ├── e ── d (red)
   ├── e ── d ── d (redd)
   └── i ── c ── e (rice)

応用: オートコンプリート、IP ルーティング、辞書検索。

7.3.6 Union-Find (素集合森)¶

「要素のグループ化」を高速に。

find(x): \(x\) が属するグループ ID
union(x, y): 2 グループを統合

経路圧縮 + ランクで、ほぼ \(O(\alpha(n))\)（実用上 \(O(1)\)）。

応用: MST (Kruskal)、グラフの連結性、画像処理の領域分割。

7.4 ハッシュ深掘り¶

7.4.1 ハッシュ関数の良し悪し¶

良いハッシュ: - 一様分布 (バケットが偏らない) - 計算が速い - 衝突困難（暗号用途では強衝突困難）

非暗号用: MurmurHash, xxHash, FNV 暗号用: SHA-256, BLAKE3

7.4.2 ブルームフィルタ — 確率的データ構造¶

「集合に含まれる」を高速・省メモリで判定。 - 偽陽性あり（含まれないのに「含まれる」と言うことがある） - 偽陰性なし

CDN, データベース、ネットワーク、Bitcoin で大活躍。

7.4.3 Count-Min Sketch / HyperLogLog¶

ストリームデータの頻度推定・ユニーク数推定。\(O(\log n)\) メモリで \(10^{12}\) ユニークの推定が可能。Google Analytics, ad-tech などで利用。

7.5 ソート¶

7.5.1 比較ソート一覧¶

名前	平均	最悪	安定	備考
挿入ソート	\(O(n^2)\)	\(O(n^2)\)	安定	ほぼ整列済みで速い
マージソート	\(O(n \log n)\)	\(O(n \log n)\)	安定	外部ソート向き
クイックソート	\(O(n \log n)\)	\(O(n^2)\)	不安定	実用最速
ヒープソート	\(O(n \log n)\)	\(O(n \log n)\)	不安定	in-place
Timsort	\(O(n \log n)\)	\(O(n \log n)\)	安定	Python・Java の標準

比較ソートの下界は \(\Omega(n \log n)\) （決定木の深さから）。

7.5.2 線形時間ソート¶

計数ソート: 値の範囲が小さいとき \(O(n + k)\)
基数ソート: 桁ごとに計数 \(O(d(n + b))\)
バケットソート: 一様分布なら \(O(n)\)

「値が整数で範囲が限定的」なら比較ソートを超えられます。

7.5.3 安定性とは¶

「等しいキーの順序が保たれる」性質。複数キーでソートするときに重要。

[(田中, 25), (山田, 25), (佐藤, 30)]
を「年齢」でソートすると:
安定: [(田中, 25), (山田, 25), (佐藤, 30)]
不安定: [(山田, 25), (田中, 25), (佐藤, 30)] かも

7.6 探索¶

7.6.1 二分探索¶

整列済み配列で \(O(\log n)\)。境界条件は鬼門。

def binary_search(a, x):
    lo, hi = 0, len(a)
    while lo < hi:
        mid = (lo + hi) // 2
        if a[mid] < x: lo = mid + 1
        else: hi = mid
    return lo

「左閉右開」で書くと off-by-one が減ります。

7.6.2 三分探索¶

単峰関数の最大値探索 \(O(\log n)\)。最適化問題に応用。

7.7 グラフアルゴリズム¶

7.7.1 グラフの表現¶

   A───B
   │   │
   C───D

隣接リスト (実務の主流):

graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D'],
    'C': ['A', 'D'],
    'D': ['B', 'C']
}

隣接行列:

   A B C D
A [0 1 1 0]
B [1 0 0 1]
C [1 0 0 1]
D [0 1 1 0]

7.7.2 BFS — 幅優先探索¶

「近い順に」探索。重みなし最短路を求められる。

graph TD
    Start((A<br/>距離 0))
    B((B<br/>距離 1))
    C((C<br/>距離 1))
    D((D<br/>距離 2))
    E((E<br/>距離 2))
    F((F<br/>距離 2))
    G((G<br/>距離 3))
    Start --> B
    Start --> C
    B --> D
    B --> E
    C --> F
    E --> G
    F --> G

    style Start fill:#ffeb3b
    style B fill:#c5e1a5
    style C fill:#c5e1a5
    style D fill:#90caf9
    style E fill:#90caf9
    style F fill:#90caf9
    style G fill:#ce93d8

階層ごとに探索が広がっていきます。「A から G まで何ステップか」が即座に分かる。

from collections import deque

def bfs(graph, start):
    visited = {start}
    queue = deque([start])
    while queue:
        node = queue.popleft()
        print(node)
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

応用: SNS の友達の友達、Web クローラ、ゲーム AI、ソーシャルネット解析。

7.7.3 DFS — 深さ優先探索¶

「行けるところまで」探索。スタックまたは再帰で。

応用: 連結成分、トポロジカルソート、橋・関節点、サイクル検出、迷路の解。

7.7.4 Dijkstra — 重み付き最短路¶

非負重みで \(O((V+E) \log V)\)（ヒープ使用）。

    2     5
A ───→ B ───→ D
│      │
3      1
│      ↓
C ───→ E
   4

ヒープから「現在最短距離が確定していない最も近い頂点」を取り出して更新。

応用: GPS 経路探索、ネットワークルーティング (OSPF)、ゲームの NPC AI。

7.7.5 Bellman-Ford¶

負の重みも OK。負閉路検出可能。\(O(VE)\)。

7.7.6 Floyd-Warshall¶

全頂点ペアの最短路。\(O(V^3)\)。動的計画法。

7.7.7 A* — ヒューリスティック付き¶

Dijkstra にゴールへの推定距離を加えて高速化。ゲームの経路探索の定番。

7.7.8 最小全域木 (MST)¶

「すべての頂点をつなぐ最小重み木」。

Kruskal: 辺を重み順、Union-Find で。\(O(E \log E)\)
Prim: 頂点を貪欲に追加、ヒープで。\(O((V+E) \log V)\)

応用: 通信網設計、クラスタリング、回路設計。

7.7.9 トポロジカルソート¶

DAG の頂点を「依存関係に従って」並べる。

build → test → deploy
        ↑
     lint

応用: ビルドシステム、タスクスケジューリング、コース履修順。

7.7.10 ネットワークフロー¶

最大流問題: - Ford-Fulkerson, Edmonds-Karp, Dinic - 最大流 = 最小カット定理

応用: 二部マッチング、課題割当、画像セグメンテーション。

7.8 アルゴリズム設計技法¶

7.8.1 分割統治¶

「大きな問題を小さな問題に分けて、解いて、結合」。

例: - マージソート - クイックソート - 高速フーリエ変換 (FFT) - 最近点対 (\(O(n \log n)\)) - Strassen 行列積 (\(O(n^{2.81})\))

7.8.2 動的計画法 (DP)¶

「部分問題の解を保存して再利用」。最適部分構造 + 部分問題の重複が条件。

フィボナッチ数列で例示¶

# 素朴: O(2^n)
def fib(n):
    if n < 2: return n
    return fib(n-1) + fib(n-2)

# DP: O(n)
def fib(n):
    dp = [0, 1] + [0] * (n-1)
    for i in range(2, n+1):
        dp[i] = dp[i-1] + dp[i-2]
    return dp[n]

主要 DP 問題¶

ナップサック (0/1, 完全)
最長共通部分列 (LCS)
編集距離 (Levenshtein)
最長増加部分列 (LIS)
区間 DP (行列連鎖積)
ビット DP (TSP)

DP の解き方 4 ステップ¶

状態を定義: \(dp[i][j]\) が何を表すか
遷移を立式: \(dp[i][j]\) を小さな状態から
初期値・順序: 基底ケース
答えの取り出し: どこに最終答えがあるか

7.8.3 貪欲法¶

各ステップで局所最適を選ぶ。最適性を証明できることが大事 (交換論法、Matroid)。

例: - Huffman 符号 - 最小全域木 - 活動選択 - コインの両替（特定の体系）

7.8.4 バックトラック¶

「試して、失敗したら戻る」。

例: N クイーン、数独、ハミルトン路、組合せ生成。

枝刈りで高速化。

7.9 文字列アルゴリズム¶

KMP, Boyer-Moore: パターンマッチ \(O(n + m)\)
Z アルゴリズム: 文字列の構造解析
サフィックス配列・自動オートマトン: 大規模文字列検索
ローリングハッシュ・Rabin-Karp: ハッシュベース
編集距離: スペルチェッカー、DNA シーケンス
Aho-Corasick: 複数パターン同時検索

応用: gravir, ripgrep のような高速検索ツール、Git の diff、生物学のシーケンス解析。

7.10 数値・幾何アルゴリズム¶

高速冪 (\(O(\log n)\))
ユークリッドの互除法、拡張ユークリッド
篩 (Eratosthenes 線形)
行列累乗で漸化式 (\(O(\log n)\))
凸包 (Graham scan, Andrew)
セグメント木、フェニック木 (BIT)、永続データ構造

7.11 並列・近似・確率的アルゴリズム¶

並列ソート、スキャン、MapReduce: 第 16 章
近似アルゴリズム: NP 困難問題に 2-近似など
ランダム化アルゴリズム: クイックソートのピボット、ミラー・ラビン素数判定、スキップリスト

7.12 計算量の限界¶

P / NP / NP 完全（第 8 章）
「速いアルゴリズムが存在するか」が決着していない問題が多い
既知の難問は近似・ヒューリスティック・SAT/SMT・ILP で

7.13 演習問題¶

動的配列の push が償却 \(O(1)\) である理由を、\(2^k\) 倍拡張で説明せよ。
赤黒木の挿入で行う 5 つのケースを列挙せよ。
Dijkstra が負の重みで誤動作する例を 1 つ挙げよ。
ナップサック問題の DP 解の状態と遷移を書け。
文字列 ABCBDAB と BDCAB の LCS を求めよ。
Union-Find の経路圧縮 + ランク実装を Python で書け。
二分探索で「a[i] >= x を満たす最小の \(i\)」を求める関数を書け。
隣接リストでグラフを定義し、Kosaraju 法で SCC を求める疑似コードを書け。
動的計画法で「コインを使って \(n\) 円を作る最少枚数」を解け。
Trie を使ってオートコンプリートを 5 文字で動かすコードを書け。

7.14 この章のまとめ¶

構造・技法	出番
配列・連結リスト	あらゆる場面
ハッシュ	高速検索
木	階層・順序
ヒープ	優先度
グラフ	つながり、依存関係
分割統治	ソート、探索
DP	最適化、文字列、最短路
貪欲	局所最適から大域

「これは BFS だ」「これは DP に帰着できる」と即座に分類できる嗅覚は、繰り返し問題を解いて身につけます。

7.15 次に読むもの¶

Cormen, Leiserson, Rivest, Stein, Introduction to Algorithms (CLRS)
Sedgewick & Wayne, Algorithms
Skiena, The Algorithm Design Manual
競技プログラミング: AtCoder, Codeforces, LeetCode で 300 問
渋谷哲朗『プログラミングコンテスト攻略のためのアルゴリズムとデータ構造』

🌟 メッセージ アルゴリズムは「手で書いて初めて分かる」分野です。最初は「読むだけ」でも、必ず最低 50 問は手で書いてみてください。論理回路を実装するように、感覚が変わります。

第 7 章 データ構造とアルゴリズム¶