第8章データ構造と基本アルゴリズム

章間ナビゲーション

前: 第7章組合せと数え上げ

次: 第9章形式言語の入口

章別マップ: 章間リンクマップ

用語確認: 用語索引 / 記号索引

到達判定: 章末確認チェック

この章で使う記号

記号	意味
`push(x)` / `pop()`	スタック操作
`enqueue(x)` / `dequeue()`	キュー操作
`find(x)` / `union(x,y)`	Union-Find の代表元取得と併合
`key`	比較・検索に使う値
`h(k)`	ハッシュ関数
`O(1)` / `O(log n)` / `O(n)`	主要操作の計算量表記

この章で解消する詰まりどころ

理論計算機科学では、データ構造を「便利なライブラリ」としてではなく、次の3点から見ます。

抽象データ型として、どの操作を提供するか。
表現方法として、メモリ上にどう持つか。
各操作の計算量がどうなるか。

同じ集合を扱う場合でも、配列、連結リスト、ハッシュ表、平衡木では、検索・挿入・削除・最小値取得の計算量が異なります。アルゴリズム解析の多くは、適切なデータ構造を選んだ時点で半分決まります。

本体教科書で使う箇所

アルゴリズムの数学的解析: 操作回数とデータ構造の計算量。
データ構造の理論: 抽象データ型、表現、計算量のトレードオフ。
グラフ理論: 隣接リスト、キュー、スタック、優先度付きキュー。
複雑性理論: 入力サイズ、証明検証、探索空間。
並行計算: 共有データ、キュー、状態遷移のモデル化。

1. 抽象データ型と実装

抽象データ型は「何ができるか」を定義します。実装は「どう実現するか」を定義します。

例: Stack

Stack は次の操作を持つ抽象データ型です。

push(x): x を積む
pop(): 最後に積んだ要素を取り出す
top(): 最後に積んだ要素を見る
is_empty(): 空か判定する

これは、配列でも連結リストでも実装できます。抽象データ型と実装を分けて考えることが重要です。

2. 配列

配列は、インデックスで要素にアクセスできる連続的なデータ構造です。

操作	典型計算量
`A[i]` の読み書き	`O(1)`
末尾追加	償却 `O(1)`
先頭・中間への挿入	`O(n)`
線形探索	`O(n)`

なぜ `A[i]` は `O(1)` か

配列では、先頭アドレスと要素サイズから i 番目の位置を計算できます。要素を1つずつ辿る必要がありません。

よくある誤解

「配列は常に高速」ではありません。中間挿入では、後続要素をずらす必要があるため O(n) です。

3. 連結リスト

連結リストは、各要素が次の要素への参照を持つ構造です。

操作	典型計算量
先頭挿入	`O(1)`
先頭削除	`O(1)`
i番目へのアクセス	`O(n)`
値の探索	`O(n)`

配列との違い

配列はランダムアクセスに強い一方、中間挿入に弱いです。連結リストは参照が分かっている位置への挿入・削除に強い一方、i番目の要素へ直接飛べません。

4. Stack と Queue

Stack

Stack は LIFO です。Last In, First Out、つまり最後に入れたものが最初に出ます。

用途:

関数呼び出しスタック
DFS
括弧列の検査
構文解析

Queue

Queue は FIFO です。First In, First Out、つまり最初に入れたものが最初に出ます。

用途:

BFS
タスクキュー
シミュレーション
メッセージ処理

5. ハッシュ表

ハッシュ表は、キーをハッシュ関数で配列の位置に写し、平均的に高速な検索・挿入・削除を実現する構造です。

操作	平均	最悪
検索	`O(1)`	`O(n)`
挿入	`O(1)`	`O(n)`
削除	`O(1)`	`O(n)`

衝突

異なるキーが同じ位置に写ることを衝突と呼びます。

衝突処理には、代表的に次があります。

chaining: 各バケットにリストなどを持つ。
open addressing: 別の空き位置を探す。

理論上の注意

ハッシュ表の O(1) は、多くの場合、平均計算量または期待計算量です。最悪計算量ではありません。理論的議論で使うときは、仮定を明示します。

6. ヒープ

ヒープは、最小値または最大値を効率よく取り出すためのデータ構造です。ここでは最小ヒープを考えます。

性質:

各ノードの値 <= その子の値

操作	計算量
最小値を見る	`O(1)`
挿入	`O(log n)`
最小値を取り出す	`O(log n)`
任意要素の検索	`O(n)`

用途

優先度付きキュー
Dijkstra法
イベントシミュレーション
ヒープソート

7. 二分探索木

二分探索木は、各ノードについて次を満たす二分木です。

左部分木の値 <= ノードの値 <= 右部分木の値

平衡が保たれていれば、検索・挿入・削除は O(log n) です。偏ると O(n) になります。

操作	平衡時	最悪
検索	`O(log n)`	`O(n)`
挿入	`O(log n)`	`O(n)`
削除	`O(log n)`	`O(n)`

理論的に安定した計算量が必要なら、AVL木、赤黒木、B木などの平衡木を考えます。

8. Union-Find

Union-Find は、要素を互いに素な集合に分け、集合の併合と同一集合判定を効率よく行う構造です。

操作:

make_set(x): x だけの集合を作る
find(x): x が属する集合の代表を返す
union(x,y): x の集合と y の集合を併合する

用途:

連結成分管理
Kruskal法
同値関係の実装
動的なグループ統合

経路圧縮と union by rank/size を使うと、実用上ほぼ定数時間で動作します。厳密には逆 Ackermann 関数を用いた評価になりますが、前提補強段階では「非常に遅く増加する関数」と理解すれば十分です。

9. グラフ表現

グラフ G=(V,E) の実装には、主に隣接行列と隣接リストがあります。

隣接行列

n × n の行列 A を用意し、辺 (u,v) があれば A[u][v]=1 とします。

特徴	内容
メモリ	`O(\|V\|^2)`
辺の存在確認	`O(1)`
ある頂点の隣接頂点列挙	`O(\|V\|)`

隣接リスト

各頂点に対して、隣接頂点のリストを持ちます。

特徴	内容
メモリ	`O(\|V\|+\|E\|)`
辺の存在確認	実装依存。通常 `O(deg(v))`
ある頂点の隣接頂点列挙	`O(deg(v))`

疎なグラフでは隣接リストが自然です。

10. 二分探索

二分探索は、ソート済み配列に対して検索範囲を半分ずつ減らすアルゴリズムです。

binary_search(A, x):
    left = 0
    right = len(A)
    while left < right:
        mid = floor((left + right) / 2)
        if A[mid] < x:
            left = mid + 1
        else:
            right = mid
    return left

この擬似コードは、x 以上となる最初の位置を返します。存在判定だけではなく、境界探索として理解すると応用範囲が広がります。

不変条件

A[0:left] の要素はすべて x 未満
A[right:len(A)] の要素はすべて x 以上

ループ終了時に left = right となり、その位置が境界です。

11. ソート

代表的なソートの計算量です。

アルゴリズム	平均	最悪	備考
insertion sort	`O(n^2)`	`O(n^2)`	小規模やほぼ整列済みで有用
merge sort	`O(n log n)`	`O(n log n)`	分割統治。安定にしやすい
quicksort	`O(n log n)`	`O(n^2)`	実用上速いが pivot に依存
heapsort	`O(n log n)`	`O(n log n)`	ヒープを使う

比較ソートでは、一般に Ω(n log n) の下界があります。これは、比較に基づいて n! 通りの順列を区別する必要があるという数え上げの議論と接続します。

12. BFS と DFS

BFS はキューを使い、始点からの距離が近い順に探索します。無重みグラフの最短距離を求めるときに使えます。

DFS はスタックまたは再帰を使い、行けるところまで深く進みます。連結成分、閉路検出、トポロジカルソートなどで使います。

隣接リスト表現なら、どちらも計算量は

O(|V| + |E|)

です。

13. Dijkstra法の入口

辺の重みが非負のグラフで、始点から各頂点への最短距離を求める代表的アルゴリズムです。

必要なデータ構造:

距離配列 dist
優先度付きキュー
隣接リスト

優先度付きキューをヒープで実装した場合、典型的には

O((|V| + |E|) log |V|)

程度になります。

ここでは詳細な証明までは扱いません。重要なのは、ヒープが入ることで「毎回最小距離の未確定頂点を選ぶ」操作が高速になる点です。

14. 動的計画法の入口

動的計画法は、同じ部分問題を何度も解かないための方法です。

Fibonacci の例

単純再帰では、同じ fib(k) を何度も計算します。

fib(n):
    if n <= 1:
        return n
    return fib(n-1) + fib(n-2)

メモ化すると、各 k を一度だけ計算します。

fib(n):
    memo = array of size n+1
    memo[0] = 0
    memo[1] = 1
    for k = 2 to n:
        memo[k] = memo[k-1] + memo[k-2]
    return memo[n]

計算量は O(n) です。

状態設計

動的計画法では、まず状態を定義します。

dp[i] = 長さ i まで見たときの最適値または場合数

次に遷移を定義します。

dp[i] = dp[i-1] + dp[i-2]

最後に初期条件を決めます。

15. 計算量表

構造・操作	典型計算量
配列アクセス	`O(1)`
配列の線形探索	`O(n)`
ソート済み配列の二分探索	`O(log n)`
Stack push/pop	`O(1)`
Queue enqueue/dequeue	`O(1)`
ハッシュ表検索	平均 `O(1)`
ヒープ挿入	`O(log n)`
ヒープ最小値削除	`O(log n)`
平衡二分探索木検索	`O(log n)`
BFS/DFS	`O(\|V\|+\|E\|)`

16. 証明の型

ループ不変条件

探索・二分探索・ソートでは、次の型を使います。

初期化: ループ開始前に不変条件が成り立つ。
保存: 1回の反復後にも不変条件が成り立つ。
終了: ループ終了条件と不変条件から正しさを導く。

帰納法

再帰アルゴリズムでは、入力サイズに関する帰納法を使います。

サイズ < n の入力で正しいと仮定する。
サイズ n の入力では、より小さい入力への再帰呼び出しが正しい。
それらを組み合わせて結果が正しい。

データ構造不変条件

ヒープや二分探索木では、構造が保つべき条件を不変条件として扱います。

ヒープ: 親 <= 子
BST: 左部分木 <= ノード <= 右部分木
Union-Find: parent を辿ると代表に到達する

17. よくある誤り

誤り1: ADT と実装を混同する

Queue は抽象データ型です。配列で実装するか、連結リストで実装するかは別問題です。

誤り2: 平均計算量を最悪計算量のように扱う

ハッシュ表の O(1) は通常、平均または期待値です。

誤り3: グラフ表現を無視して計算量を書く

BFS の O(|V|+|E|) は、通常、隣接リスト表現を前提にしています。隣接行列で隣接頂点を走査すれば O(|V|^2) になることがあります。

誤り4: 二分探索の境界条件を曖昧にする

left, right が閉区間か半開区間かを決めずに書くと、無限ループや off-by-one エラーになります。

章末チェック

次を説明できれば、この章の最低ラインは満たしています。

抽象データ型と実装の違い。
配列、連結リスト、スタック、キュー、ハッシュ表、ヒープの基本操作。
ハッシュ表の平均計算量と最悪計算量の違い。
隣接行列と隣接リストの違い。
二分探索の不変条件。
BFS/DFS が O(|V|+|E|) になる理由。
動的計画法で状態と遷移を分けて考えること。

次に読む章

通常ルート: 第9章形式言語の入口
演習: Standard 演習
解答: 演習解答
図表: 関連図表
実装確認: Python実装ノート
全体導線: 学習チェックリスト

第8章 データ構造と基本アルゴリズム