💡 왼쪽 원문을 읽으면서 오른쪽에 따라 써보세요. Tab 키로 힌트를 받을 수 있습니다.

원문 렌더가 준비되기 전까지 텍스트 가이드로 표시합니다.

1. 計算量分析

Big-O / Omega / Theta 記法

アルゴリズム分析の核心は、入力サイズ `n` に対して時間・空間リソースがどのように増加するかを数学的に表現することです。

| 記法 | 意味 | 説明 |

| ------- | ---------------------- | ------------------------------------ |

| O(f(n)) | 上界 (Upper Bound) | 最悪ケースで f(n) より速く成長しない |

| Ω(f(n)) | 下界 (Lower Bound) | 最良ケースで f(n) より遅く成長しない |

| Θ(f(n)) | 厳密な界 (Tight Bound) | 正確に f(n) の速度で成長する |

**主な計算量クラス**（成長の遅い順）：

O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(n³) < O(2ⁿ) < O(n!)

漸化式とマスター定理

分割統治アルゴリズムの計算量は漸化式で表され、**マスター定理**で解くことができます。

T(n) = aT(n/b) + f(n)

- `a` = サブ問題の数、`b` = 分割率、`f(n)` = 分割・統合のコスト

**マスター定理の3つのケース：**

1. f(n) = O(n^(log_b(a) - ε)) → T(n) = Θ(n^log_b(a))

2. f(n) = Θ(n^log_b(a)) → T(n) = Θ(n^log_b(a) · log n)

3. f(n) = Ω(n^(log_b(a) + ε)) → T(n) = Θ(f(n))

**例：** マージソート T(n) = 2T(n/2) + O(n) → ケース2 → **Θ(n log n)**

償却分析 (Amortized Analysis)

個々の操作が高価でも、操作シーケンス全体の平均コストを分析します。

**動的配列の例：**

- 容量超過時に2倍拡張 → そのpushはO(n)

- n回のpush全体のコスト：O(1) + O(1) + ... + O(n) ≈ O(2n) = O(n)

- **償却コスト：1操作あたりO(1)**

2. 主要データ構造

データ構造の計算量まとめ

| データ構造 | アクセス | 探索 | 挿入 | 削除 | 空間 |

| ---------------- | ----------- | -------- | -------- | -------- | ---- |

| 配列 | O(1) | O(n) | O(n) | O(n) | O(n) |

| 連結リスト | O(n) | O(n) | O(1) | O(1) | O(n) |

| スタック | O(n) | O(n) | O(1) | O(1) | O(n) |

| キュー | O(n) | O(n) | O(1) | O(1) | O(n) |

| ハッシュテーブル | - | O(1)\* | O(1)\* | O(1)\* | O(n) |

| ヒープ | O(1) (最大) | O(n) | O(log n) | O(log n) | O(n) |

\*平均ケース

赤黒木 (Red-Black Tree)

自動的にバランスを維持する自己平衡二分探索木です。

**5つの性質：**

1. すべてのノードは赤か黒

2. ルートノードは黒

3. すべての葉（NIL）は黒

4. 赤ノードの子はすべて黒

5. ルートから任意の葉までの経路上の黒ノード数は同じ

赤黒木の回転 - 左回転(Left Rotation)の概念

x y

/ \ → / \

a y x c

/ \ / \

b c a b

def left_rotate(tree, x):

y = x.right # yはxの右の子

x.right = y.left # yの左部分木をxの右へ

if y.left != tree.NIL:

y.left.parent = x

y.parent = x.parent # xの親をyの親に

if x.parent == tree.NIL:

tree.root = y

elif x == x.parent.left:

x.parent.left = y

else:

x.parent.right = y

y.left = x # xをyの左の子に

x.parent = y

ヒープと優先度付きキュー

ヒープは配列に格納された完全二分木です。

Dijkstra法のための最小ヒープ活用

def dijkstra(graph, start):

distances = {node: float('inf') for node in graph}

distances[start] = 0

(距離, ノード) 形式でヒープに格納

heap = [(0, start)]

visited = set()

while heap:

dist, node = heapq.heappop(heap)

if node in visited:

continue

visited.add(node)

for neighbor, weight in graph[node]:

new_dist = dist + weight

if new_dist < distances[neighbor]:

distances[neighbor] = new_dist

heapq.heappush(heap, (new_dist, neighbor))

return distances

使用例

graph = {

'A': [('B', 1), ('C', 4)],

'B': [('C', 2), ('D', 5)],

'C': [('D', 1)],

'D': []

}

print(dijkstra(graph, 'A'))

{'A': 0, 'B': 1, 'C': 3, 'D': 4}

3. グラフアルゴリズム

BFS と DFS の比較

| 特性 | BFS | DFS |

| ---------- | ---------------------- | ------------------------------ |

| データ構造 | キュー | スタック / 再帰 |

| 最短経路 | あり（重みなしグラフ） | なし |

| 空間計算量 | O(V + E) | O(V) |

| 用途 | 最短経路、レベル探索 | 閉路検出、位相ソート、連結成分 |

最短経路アルゴリズムの比較

| -------------- | ------ | ------------ | -------------- | -------- |

| Bellman-Ford | 可 | 可 | O(VE) | 単一始点 |

| Floyd-Warshall | 可 | 可 | O(V³) | 全点対 |

Floyd-Warshall の実装

def floyd_warshall(n, edges):

INF = float('inf')

dist[i][j] = iからjへの最短距離

dist = [[INF] * n for _ in range(n)]

for i in range(n):

dist[i][i] = 0

for u, v, w in edges:

dist[u][v] = w

for k in range(n): # 経由ノード

for i in range(n): # 出発ノード

for j in range(n): # 到着ノード

if dist[i][k] + dist[k][j] < dist[i][j]:

dist[i][j] = dist[i][k] + dist[k][j]

return dist

MST: クラスカル法 vs プリム法

**クラスカル法**（辺ベース、Union-Find使用）：

- すべての辺を重みの昇順にソートし、閉路を作らないように選択

- 時間計算量：O(E log E)

- 疎グラフに適している

**プリム法**（頂点ベース、最小ヒープ使用）：

- 開始ノードから隣接する最小重みの辺を繰り返し選択

- 時間計算量：O(E log V)

- 密グラフに適している

位相ソート (Topological Sort)

DAG（有向非巡回グラフ）における依存関係の順序を決定します。

from collections import deque

def topological_sort(n, edges):

indegree = [0] * n

graph = [[] for _ in range(n)]

for u, v in edges:

graph[u].append(v)

indegree[v] += 1

queue = deque([i for i in range(n) if indegree[i] == 0])

result = []

while queue:

node = queue.popleft()

result.append(node)

for neighbor in graph[node]:

indegree[neighbor] -= 1

if indegree[neighbor] == 0:

queue.append(neighbor)

return result if len(result) == n else [] # 閉路あり → 空リスト

4. 動的計画法

DP の2つのアプローチ

**最適部分構造（Optimal Substructure）：** 問題の最適解が部分問題の最適解から構成される。

**重複部分問題（Overlapping Subproblems）：** 同じ部分問題が繰り返し現れる。

| 方式 | 方向 | メリット | デメリット |

| ----------------------------- | ----------------- | ------------------------------------------------ | ---------------------------- |

LCS（最長共通部分列）

def lcs(s1, s2):

m, n = len(s1), len(s2)

dp[i][j] = s1[:i] と s2[:j] の LCS の長さ

dp = [[0] * (n + 1) for _ in range(m + 1)]

for i in range(1, m + 1):

for j in range(1, n + 1):

if s1[i-1] == s2[j-1]:

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

else:

dp[i][j] = max(dp[i-1][j], dp[i][j-1])

2Dテーブルの可視化 (s1="ABCD", s2="ACBD"):

"" A C B D

"" 0 0 0 0 0

A 0 1 1 1 1

B 0 1 1 2 2

C 0 1 2 2 2

D 0 1 2 2 3 <- LCS の長さ = 3 ("ABD" または "ACD")

return dp[m][n]

0/1 ナップサック問題

def knapsack(weights, values, capacity):

n = len(weights)

dp[i][w] = i番目のアイテムまで考慮し、容量wのときの最大価値

dp = [[0] * (capacity + 1) for _ in range(n + 1)]

for i in range(1, n + 1):

for w in range(capacity + 1):

アイテム i を含まない場合

dp[i][w] = dp[i-1][w]

アイテム i を含む場合

if weights[i-1] <= w:

dp[i][w] = max(dp[i][w],

dp[i-1][w - weights[i-1]] + values[i-1])

return dp[n][capacity]

5. 高度なアルゴリズム

セグメントツリー (Segment Tree)

配列の区間クエリ（合計、最小値、最大値）をO(log n)で処理します。

class SegmentTree:

def __init__(self, arr):

self.n = len(arr)

self.tree = [0] * (4 * self.n)

self.build(arr, 0, 0, self.n - 1)

def build(self, arr, node, start, end):

if start == end:

self.tree[node] = arr[start]

else:

mid = (start + end) // 2

self.build(arr, 2*node+1, start, mid)

self.build(arr, 2*node+2, mid+1, end)

self.tree[node] = self.tree[2*node+1] + self.tree[2*node+2]

def query(self, node, start, end, l, r):

if r < start or end < l:

return 0 # 範囲外

if l <= start and end <= r:

return self.tree[node] # 完全包含

mid = (start + end) // 2

left = self.query(2*node+1, start, mid, l, r)

right = self.query(2*node+2, mid+1, end, l, r)

return left + right

def update(self, node, start, end, idx, val):

if start == end:

self.tree[node] = val

else:

mid = (start + end) // 2

if idx <= mid:

self.update(2*node+1, start, mid, idx, val)

else:

self.update(2*node+2, mid+1, end, idx, val)

self.tree[node] = self.tree[2*node+1] + self.tree[2*node+2]

フェニックツリー (Fenwick Tree / BIT)

セグメントツリーより実装が簡単でメモリ効率も優れています。

class FenwickTree:

def __init__(self, n):

self.n = n

self.tree = [0] * (n + 1)

def update(self, i, delta):

while i <= self.n:

self.tree[i] += delta

i += i & (-i) # 最下位ビットを加算

def query(self, i):

total = 0

while i > 0:

total += self.tree[i]

i -= i & (-i) # 最下位ビットを除去

return total

def range_query(self, l, r):

return self.query(r) - self.query(l - 1)

| ---------------- | ---------- | ---------- | -------- | -------- | ------ |

| フェニックツリー | 低い | O(log n) | O(log n) | 限定的 | O(n) |

Union-Find（経路圧縮 + ランク）

class UnionFind:

def __init__(self, n):

self.parent = list(range(n))

self.rank = [0] * n

def find(self, x):

経路圧縮（Path Compression）

if self.parent[x] != x:

self.parent[x] = self.find(self.parent[x])

return self.parent[x]

def union(self, x, y):

rx, ry = self.find(x), self.find(y)

if rx == ry:

return False # すでに同じ集合

ランクによる合併（Union by Rank）

if self.rank[rx] < self.rank[ry]:

rx, ry = ry, rx

self.parent[ry] = rx

if self.rank[rx] == self.rank[ry]:

self.rank[rx] += 1

return True

経路圧縮 + ランク → 事実上 O(α(n)) ≈ O(1)（逆アッカーマン関数）

KMP 文字列マッチング

def kmp_search(text, pattern):

def build_lps(pattern):

lps = [0] * len(pattern)

length, i = 0, 1

while i < len(pattern):

if pattern[i] == pattern[length]:

length += 1

lps[i] = length

i += 1

elif length:

length = lps[length - 1]

else:

lps[i] = 0

i += 1

return lps

lps = build_lps(pattern)

i = j = 0

results = []

while i < len(text):

if text[i] == pattern[j]:

i += 1; j += 1

if j == len(pattern):

results.append(i - j)

j = lps[j - 1]

elif i < len(text) and text[i] != pattern[j]:

j = lps[j - 1] if j else (i := i + 1) and 0

return results

6. AI/ML連携アルゴリズム

k-dツリー（k-NN検索）

k-dツリーはk次元空間を分割し、最近傍探索（k-NN）を効率的に行います。

class KDNode:

def __init__(self, point, left=None, right=None):

self.point = point

self.left = left

self.right = right

def build_kd_tree(points, depth=0):

if not points:

return None

k = len(points[0])

axis = depth % k

sorted_points = sorted(points, key=lambda p: p[axis])

mid = len(sorted_points) // 2

return KDNode(

point=sorted_points[mid],

left=build_kd_tree(sorted_points[:mid], depth + 1),

right=build_kd_tree(sorted_points[mid+1:], depth + 1)

)

def nearest_neighbor(root, query, depth=0, best=None):

if root is None:

return best

k = len(query)

axis = depth % k

dist = sum((q - p) ** 2 for q, p in zip(query, root.point)) ** 0.5

if best is None or dist < best[0]:

best = (dist, root.point)

クエリポイントと分割超平面を比較

diff = query[axis] - root.point[axis]

close, away = (root.left, root.right) if diff <= 0 else (root.right, root.left)

best = nearest_neighbor(close, query, depth + 1, best)

反対側のサブツリーも探索が必要か確認

if abs(diff) < best[0]:

best = nearest_neighbor(away, query, depth + 1, best)

return best

**k-dツリーの平均計算量：O(log n)、最悪：O(n)**（高次元では「次元の呪い」により性能が低下）

LSH（局所性鋭敏型ハッシュ）

高次元データ（埋め込みベクトル）から類似データを高速に探す近似最近傍（ANN）手法です。

- **核心アイデア：** 類似するベクトルは高い確率で同じハッシュバケットに入る

- **コサイン類似度用LSH：** ランダム超平面によるハッシュ生成

- **応用：** 大規模埋め込み検索（Faiss、ScaNN）、重複文書検出

- **時間計算量：** クエリ O(1) ～ O(log n)、インデックス構築 O(nk)

ビームサーチ（NLPデコーディング）

貪欲探索の改善：各ステップで上位k個（ビーム幅）の候補を維持します。

ビーム幅 k=2、各トークンで上位2つを保持：

ステップ1: [A(0.6), B(0.4)]

ステップ2: [AA(0.36), AB(0.24), BA(0.28), BB(0.16)] -> 上位2: [AA, BA]

ステップ3: [AAX, AAY, BAX, BAY] -> 上位2を保持...

**トレードオフ：** ビーム幅を大きくすると品質向上、ただしメモリ・時間が O(k·n) で増加

A\*アルゴリズム（ロボティクス / 経路計画）

Dijkstra法にヒューリスティック関数 h(n) を組み合わせた最適経路探索アルゴリズムです。

f(n) = g(n) + h(n)

g(n) = スタートから現在のノードまでの実際のコスト

h(n) = 現在のノードからゴールまでの推定コスト（許容ヒューリスティック）

- **許容条件（Admissible）：** h(n) が実際のコスト以下 → 最適解を保証

- **ロボティクスへの応用：** グリッドマップ上の移動計画、ROS Navigation Stack

- **時間計算量：** O(E log V)（Dijkstra法と同じだが、実際の探索空間は大幅に削減）

7. コーディング面接重要パターン

二ポインタ (Two Pointers)

ソート済み配列で合計が target になる2つの数を見つける

def two_sum_sorted(arr, target):

left, right = 0, len(arr) - 1

while left < right:

current = arr[left] + arr[right]

if current == target:

return (left, right)

elif current < target:

left += 1

else:

right -= 1

return None

時間 O(n)、空間 O(1)

スライディングウィンドウ (Sliding Window)

長さkの部分配列の最大和

def max_subarray_sum(arr, k):

window_sum = sum(arr[:k])

max_sum = window_sum

for i in range(k, len(arr)):

window_sum += arr[i] - arr[i - k]

max_sum = max(max_sum, window_sum)

return max_sum

時間 O(n)、空間 O(1)

バックトラッキング (Backtracking)

N-Queens問題

def solve_n_queens(n):

results = []

board = [-1] * n

def is_valid(row, col):

for r in range(row):

if board[r] == col:

return False

if abs(board[r] - col) == abs(r - row):

return False

return True

def backtrack(row):

if row == n:

results.append(board[:])

return

for col in range(n):

if is_valid(row, col):

board[row] = col

backtrack(row + 1)

board[row] = -1 # バックトラック

backtrack(0)

return results

パターン選択ガイド

| 問題の種類 | 推奨パターン |

| ----------------------------------- | ----------------------------------- |

| ソート済み配列、ペア/三つ組の組合せ | 二ポインタ |

| 連続する部分配列/文字列 | スライディングウィンドウ |

| 組合せ/順列/場合の数 | バックトラッキング |

| 最短経路/レベル探索 | BFS |

| 閉路/位相/連結性 | DFS |

| 区間クエリ/更新 | セグメントツリー / フェニックツリー |

| 集合のマージ/連結判定 | Union-Find |

| 最適化問題、重複部分問題 | 動的計画法 |

8. クイズ：実力チェック

**答え**: すべてのキーが同じバケットにハッシュ衝突（Hash Collision）するとき

**解説**: ハッシュテーブルはハッシュ関数でキーをバケットにマッピングします。理想的な場合は衝突なしで O(1) ですが、ハッシュ関数が悪い場合や悪意のある入力によってn個のキーすべてが同じバケットに入ると、チェイニング（Chaining）方式ではそのバケットの連結リストを線形探索する必要があり O(n) になります。これを防ぐために、負荷率（Load Factor）超過時の再ハッシュ（Rehashing）、ランダムハッシュ関数（Universal Hashing）、またはRobin Hood Hashingなどが使われます。

**答え**: Dijkstra法は「既に訪問したノードの距離は最短」という貪欲な仮定に基づいており、負の辺があるとこの仮定が崩れます。

**解説**: Dijkstra法は最小ヒープから取り出したノードを「確定」としてマークします。負の辺がある場合、すでに確定したノードAについて、後から訪問するノードBを経由する経路 A → B → A によってAの距離が改善される可能性があります（負のサイクルがなくても）。つまり、後で訪問するノードを通じて以前に確定したノードの距離が改善される可能性があり、アルゴリズムの前提が成立しません。負の辺にはBellman-Fordアルゴリズムを使う必要があります。

**答え**: メモ化は呼び出された部分問題のみ保存（疎なときに有利）、タビュレーションは常にテーブル全体を埋めるため O(n) 以上。ただし、タビュレーションはスライディングウィンドウで空間最適化が可能。

**解説**: メモ化はTop-Down方式で再帰呼び出し時にキャッシュに保存し、実際に必要な部分問題のみ計算します。全部分問題数がnであっても、実際の呼び出しがk個ならO(k)の空間のみ使います。一方タビュレーションはBottom-Upでテーブル全体を埋めるため、常にO(n)の空間を使います。ただし、フィボナッチ数列のように直前の2つの値だけが必要な場合はO(1)空間に最適化できます。

**答え**: 空間を半分ずつ分割して探索範囲を縮小するため平均 O(log n)。ただし、高次元（dが大きいほど）では「次元の呪い」により性能が O(n) に近づく。

**解説**: k-dツリーは各レベルで1つの軸を基準にデータを半分に分割します。最近傍探索時にクエリポイントと分割超平面の距離を比較し、不要なサブツリーを枝刈り（pruning）します。低次元（d ≤ 20程度）では平均 O(log n) で効率的ですが、次元が高くなるほど分割超平面との距離が小さくなり枝刈り効果が減少し、最終的にはすべてのポイントを訪問することになります。高次元ではLSHやHNSW（Hierarchical Navigable Small World）のような近似最近傍（ANN）アルゴリズムの方が効率的です。

**答え**: セグメントツリーは実装が複雑だが汎用的（区間更新、様々な集計関数）、フェニックツリーは実装が簡単で高速だが主に累積和などの限定的な演算に特化。

**解説**: フェニックツリー（BIT）はビット演算（最下位ビット）で実装が非常に簡潔でキャッシュ効率が高いです。主にprefix sum（区間合計）クエリと点更新に使われます。セグメントツリーは実装は複雑ですが、区間最小/最大値、Lazy Propagationによる区間更新、複雑な集計関数（GCD、XORなど）まで対応しています。競技プログラミングでは「区間合計だけならBIT、それ以外はセグメントツリー」が一般的なガイドラインです。

まとめ

アルゴリズムとデータ構造はAIエンジニアリングの重要な基盤です。

- **計算量分析**はシステム設計におけるボトルネックの予測とスケーリングの意思決定に不可欠です。

- **グラフアルゴリズム**は知識グラフ、推薦システム、経路最適化に直接応用されます。

- **動的計画法**はシーケンスモデリングや強化学習のベルマン方程式と深く関連しています。

- **k-dツリー、LSH、ビームサーチ**は現代のMLシステムの効率的な推論を可能にする中核アルゴリズムです。

継続的な問題演習と実装練習を通じて、理論と実践の両方をマスターしましょう。

目次

1. 計算量分析

Big-O / Omega / Theta 記法

漸化式とマスター定理

償却分析 (Amortized Analysis)

2. 主要データ構造

データ構造の計算量まとめ

赤黒木 (Red-Black Tree)

赤黒木の回転 - 左回転(Left Rotation)の概念

x y

/ \ → / \

a y x c

/ \ / \

b c a b

ヒープと優先度付きキュー

Dijkstra法のための最小ヒープ活用

(距離, ノード) 形式でヒープに格納

使用例

{'A': 0, 'B': 1, 'C': 3, 'D': 4}

3. グラフアルゴリズム

BFS と DFS の比較

最短経路アルゴリズムの比較

Floyd-Warshall の実装

dist[i][j] = iからjへの最短距離

MST: クラスカル法 vs プリム法

位相ソート (Topological Sort)

4. 動的計画法

DP の2つのアプローチ

LCS（最長共通部分列）

dp[i][j] = s1[:i] と s2[:j] の LCS の長さ

2Dテーブルの可視化 (s1="ABCD", s2="ACBD"):

"" A C B D

"" 0 0 0 0 0

A 0 1 1 1 1

B 0 1 1 2 2

C 0 1 2 2 2

D 0 1 2 2 3 <- LCS の長さ = 3 ("ABD" または "ACD")

0/1 ナップサック問題

dp[i][w] = i番目のアイテムまで考慮し、容量wのときの最大価値

アイテム i を含まない場合

アイテム i を含む場合

5. 高度なアルゴリズム

セグメントツリー (Segment Tree)

フェニックツリー (Fenwick Tree / BIT)

Union-Find（経路圧縮 + ランク）

経路圧縮（Path Compression）

ランクによる合併（Union by Rank）

経路圧縮 + ランク → 事実上 O(α(n)) ≈ O(1)（逆アッカーマン関数）

KMP 文字列マッチング

6. AI/ML連携アルゴリズム

k-dツリー（k-NN検索）

クエリポイントと分割超平面を比較

反対側のサブツリーも探索が必要か確認

LSH（局所性鋭敏型ハッシュ）

ビームサーチ（NLPデコーディング）

A\*アルゴリズム（ロボティクス / 経路計画）

7. コーディング面接 重要パターン

二ポインタ (Two Pointers)

ソート済み配列で合計が target になる2つの数を見つける

時間 O(n)、空間 O(1)

スライディングウィンドウ (Sliding Window)

長さkの部分配列の最大和

時間 O(n)、空間 O(1)

バックトラッキング (Backtracking)

N-Queens問題

パターン選択ガイド

8. クイズ：実力チェック

まとめ

7. コーディング面接重要パターン