データ構造とアルゴリズム (Data Structures & Algorithms)

はじめに

データ構造とアルゴリズムは、ソフトウェアの「問題をどう表現し、どう解くか」の基盤だ。競技プログラミングのための知識ではなく、日常の設計・実装・レビューで使う実践的な判断力として身につけよう。

Big-O 記法 (Big-O Notation)

アルゴリズムの効率を議論するための共通言語。入力サイズ n に対して、処理時間やメモリ使用量がどう増加するかを表す。

記法	名前	例	実用感
O(1)	定数時間	ハッシュテーブルの参照	最高。データ量に依存しない
O(log n)	対数時間	二分探索	非常に高速。100万件でも約20ステップ
O(n)	線形時間	配列の全走査	妥当。データ量に比例
O(n log n)	準線形時間	効率的なソート	ソートの実用的な下限
O(n^2)	二乗時間	ネストしたループ	1万件超えると厳しくなる
O(2^n)	指数時間	素朴な再帰	数十件で破綻する

実務での目安: API のレスポンスに含まれるデータ量を考えよう。100件なら O(n^2) でも問題ないが、10万件なら O(n log n) 以下にしたい。

主要なデータ構造

配列 (Array) / リスト (List)

連続したメモリに要素を格納する。最も基本的なデータ構造。

Index:  0    1    2    3    4
Value: [10] [20] [30] [40] [50]

操作	計算量	備考
インデックスアクセス	O(1)	最大の強み
末尾への追加	O(1)*	動的配列は償却 O(1)
先頭/中間への挿入	O(n)	要素のシフトが必要
検索 (未ソート)	O(n)	全走査が必要

使いどころ: 順序が重要なデータ、インデックスでアクセスするデータ。API レスポンスのリスト、テーブルの行データなど。

連結リスト (Linked List)

各要素 (ノード) が次の要素へのポインタを持つ。

[10|→] → [20|→] → [30|→] → null

操作	計算量	備考
先頭への挿入/削除	O(1)	配列より有利
インデックスアクセス	O(n)	先頭から辿る必要あり
検索	O(n)	全走査が必要

使いどころ: 実務で直接使う機会は少ないが、キュー・スタックの内部実装や、LRU キャッシュなどの仕組みを理解する上で重要。

ハッシュテーブル (Hash Table)

キーをハッシュ関数で変換し、値を格納する。JavaScript の Object / Map、Python の dict、Ruby の Hash がこれ。

操作	平均計算量	最悪計算量
参照	O(1)	O(n)
挿入	O(1)	O(n)
削除	O(1)	O(n)

使いどころ: キーによる高速な検索が必要な場面。ユーザー ID → ユーザー情報のマッピング、重複チェック、カウンティング。

// 実務例: 患者IDで高速に検索できるようにする
const patientMap = new Map<string, Patient>();
patients.forEach(p => patientMap.set(p.id, p));

// O(1) で取得できる
const patient = patientMap.get("patient-123");

スタック (Stack) とキュー (Queue)

スタック (LIFO - Last In, First Out):

最後に入れたものが最初に出る
使いどころ: 関数呼び出しスタック、Undo 機能、括弧の対応チェック

キュー (FIFO - First In, First Out):

最初に入れたものが最初に出る
使いどころ: タスクキュー、メッセージキュー、BFS

// キューの実務例: バックグラウンドジョブの処理順序
const jobQueue: Job[] = [];
jobQueue.push(newJob);        // enqueue
const nextJob = jobQueue.shift(); // dequeue

木 (Tree)

階層的なデータを表現する。各ノードが子ノードを持つ。

        CEO
       /    \
     CTO    CFO
    /   \
  Dev   DevOps

二分探索木 (BST): 左の子 < 親 < 右の子という制約を持つ木。検索・挿入・削除が平均 O(log n)。

使いどころ: DOM ツリー、ファイルシステム、組織図、カテゴリの階層構造。データベースのインデックス (B-Tree) は木構造の応用。

グラフ (Graph)

ノード (頂点) とエッジ (辺) で構成される。木はグラフの特殊ケース。

使いどころ: ソーシャルネットワーク、依存関係、ワークフロー、経路探索。医療文脈では、患者の紹介ネットワークや、診療フローのモデリングなど。

主要なアルゴリズム

ソートアルゴリズム

アルゴリズム	平均計算量	安定性	実用メモ
クイックソート	O(n log n)	不安定	実用上最速。多くの言語の標準ソート
マージソート	O(n log n)	安定	安定ソートが必要な場合
ヒープソート	O(n log n)	不安定	追加メモリ不要

実務での判断: 自前でソートを実装する必要はほぼない。言語の標準ソート関数を使おう。重要なのは 何でソートするか と 安定性が必要か の判断。

// 安定ソートの実務例: まず名前でソートし、次に日付でソート
// 安定ソートなら、同じ日付内で名前順が保持される
appointments.sort((a, b) => a.patientName.localeCompare(b.patientName));
appointments.sort((a, b) => a.date.getTime() - b.date.getTime());

探索アルゴリズム

線形探索 (Linear Search): O(n) - 先頭から順に探す。未ソートのデータに対して使う。

二分探索 (Binary Search): O(log n) - ソート済みデータを半分に分割しながら探す。

// 二分探索の考え方: ソート済み配列で特定の値を見つける
function binarySearch(sortedArr: number[], target: number): number {
  let left = 0;
  let right = sortedArr.length - 1;
  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    if (sortedArr[mid] === target) return mid;
    if (sortedArr[mid] < target) left = mid + 1;
    else right = mid - 1;
  }
  return -1;
}

グラフ走査

幅優先探索 (BFS - Breadth-First Search): キューを使い、近いノードから順に探索。最短経路の発見に有用。

深さ優先探索 (DFS - Depth-First Search): スタック (または再帰) を使い、一方向に深く探索してからバックトラック。

実務での使いどころ: ツリー構造の走査 (DOM 操作、カテゴリ一覧の取得)、依存関係の解析、到達可能性の判定。

実践的な判断フレームワーク

データ構造の選び方

データを格納したい
├── キーで検索する必要がある？
│   └── Yes → ハッシュテーブル (Map/Object)
├── 順序が重要？
│   ├── LIFO (最新を最初に) → スタック
│   ├── FIFO (最古を最初に) → キュー
│   └── ソート順を維持 → ソート済み配列 or 木
├── 階層構造がある？
│   └── Yes → 木
├── 関係性を表現する？
│   └── Yes → グラフ
└── その他 → 配列 (デフォルトの選択肢)

パフォーマンス改善の典型パターン

問題	解決策
リスト内の重複チェックが O(n^2)	Set を使って O(n) に
頻繁な検索が O(n)	ハッシュテーブルで O(1) に
ソート済みデータの検索が O(n)	二分探索で O(log n) に
N+1 クエリ問題	バッチ取得 + ハッシュテーブルで結合

// N+1 問題の解消例
// Bad: O(n) のクエリ発行
for (const appointment of appointments) {
  const patient = await db.patients.findById(appointment.patientId); // N回のクエリ
}

// Good: バッチ取得 + Map
const patientIds = appointments.map(a => a.patientId);
const patients = await db.patients.findByIds(patientIds); // 1回のクエリ
const patientMap = new Map(patients.map(p => [p.id, p]));
appointments.forEach(a => {
  const patient = patientMap.get(a.patientId); // O(1) の参照
});

Agent-first 開発においてこれが重要な理由

AI コーディングエージェントはコードを書けるが、パフォーマンス要件を自分で判断することは難しい。

計算量を指定できる: 「この検索は O(1) で実行できるようにハッシュテーブルを使って」と指示できる
非効率なコードを見抜ける: エージェントが生成したネストしたループが O(n^2) であることに気づき、改善を指示できる
適切なデータ構造を指定できる: 「患者データは ID をキーとした Map で管理して」のように、具体的な構造を指示できる
トレードオフを判断できる: 「このデータ量なら O(n^2) でも十分」「ここは将来のデータ増加を見据えて効率的な実装にすべき」といった判断ができる

エージェントは「動くコード」は書けるが、「適切な効率のコード」を書くには人間の判断が必要だ。