computer-science-algorithms

コミュニティ版・古典的コンピューターサイエンスのアルゴリズムに関するベストプラクティス

古典的なアルゴリズムやデータ構造を正しく選択し、実装するための実践者向けリファレンスです。実行ライフサイクルへの影響順に整理しています。最初の判断（漸近計算量、データ構造の選択）はその後のすべてに波及するため、表の上位にあるルールほど重要です。

対象範囲： 日常的な本番コードのレビューや、妥当な面接／コンテスト問題、そして大規模環境で使うツールボックス（スケッチ、ストリーミング、分散プリミティブ）で見られるパターンです。CLRS の内容をすべて網羅するものではありません。現行版では意図的に対象外としているトピックは、ネットワークフロー、剰余演算、単独のルールとしての Bellman-Ford と Floyd-Warshall、SCC（Tarjan/Kosaraju）、計算幾何学、FFT、単独のルールとしての Manacher／Z 関数です。これらは関連するルール内で明記しています。

CLRS（Introduction to Algorithms, 第4版）、Sedgewick & Wayne（Algorithms, 第4版、Princeton）、Skiena の Algorithm Design Manual、Laaksonen の Competitive Programmer's Handbook、cp-algorithms.com、USACO Guide をもとに要点をまとめています。

適用する場面

次のような場合に、このルールを活用してください。

• 新しい問題に使うアルゴリズムやデータ構造を選ぶとき（「X を解くにはどうするのが適切か？」）
• O(n²) の隠れた性能悪化がないかコードをレビューするとき — リストに対する in の繰り返しチェック、リストに対する pop(0)、ループ内での文字列連結、素朴な部分文字列検索など
• メモ化を書く前に、DP の状態や漸化式を決めるとき
• 問題をグラフとしてモデル化するとき（BFS、Dijkstra、トポロジカルソートのどれを使うか）
• おもちゃのような入力では動作するものの、大規模環境ではタイムアウトする総当たり／素朴な解法をリファクタリングするとき
• 貪欲法を適用できるか、それとも DP／分枝限定法が必要かを判断するとき

優先度別ルールカテゴリー

#	カテゴリー	接頭辞	影響度	波及する理由
1	漸近計算量とアルゴリズムの選択	comp-	CRITICAL	O() のクラスを誤ると、ほかのあらゆる最適化が意味をなさなくなります
2	データ構造の選択	ds-	CRITICAL	コンテナーによって、どの操作を低コストで行えるかが決まります
3	ソートと検索	srch-	HIGH	貪欲法、二ポインター法、スイープライン法、答えに対する二分探索の基礎です
4	動的計画法	dp-	HIGH	指数時間から多項式時間への変換を可能にします
5	グラフアルゴリズム	graph-	HIGH	ネットワーク、依存関係、ルーティング、スケジューリングはすべてグラフに帰着します
6	分割統治法／再帰	divide-	MEDIUM-HIGH	対数因子の高速化をもたらしますが、スタック深度や漸化式には落とし穴があります
7	貪欲アルゴリズム	greedy-	MEDIUM	正しければ高速ですが、そうでない場合は気づかないまま誤った結果になります
8	文字列／列アルゴリズム	str-	MEDIUM	パターンマッチング、解析、部分文字列クエリに使います
9	スケール対応／確率的アルゴリズム	scale-	MEDIUM	スケッチ、ストリーミング、分散プリミティブ — 適用場面は限られますが、当てはまる場合は決定的です

クイックリファレンス

1. 漸近計算量とアルゴリズムの選択（CRITICAL）

• comp-pick-algorithm-class-from-input-bound — コードを書く前に n に応じた O() を選びます
• comp-amortize-instead-of-worst-casing — 操作ごとの最悪ケースではなく、合計コストを考えます
• comp-watch-for-quadratic-blowup-from-membership-in-list — ループ内での線形時間の in チェックは O(n²) になります
• comp-prefer-iterative-builders-over-string-concatenation — += ではなく、join／バッファーを使います
• comp-derive-recurrences-via-master-theorem — 再帰のコードを書く前に、漸化式を立てます
• comp-treat-space-complexity-as-first-class — 時間より先にメモリーがサービスを停止させることがあります

2. データ構造の選択（最重要）

• ds-hash-map-for-keyed-lookup — インデックスを一度作成してから、O(1) で検索します
• ds-set-for-uniqueness-and-membership — 重複の除去と「これを見たことがあるか」の確認を O(1) で行います
• ds-heap-for-top-k-and-priority-queues — O(n log k)、優先度キューの慣用パターン
• ds-deque-for-both-end-operations — BFS キューやスライディングウィンドウで、先頭からの取り出しを O(1) で行います
• ds-balanced-bst-or-sorted-container-for-range-queries — 直前の要素／直後の要素／範囲スキャン
• ds-union-find-for-dynamic-connectivity — ほぼ O(1) でグループ化と統合を行います
• ds-prefix-sums-for-repeated-range-sums — O(n) の前処理後、範囲の合計を O(1) で求めます
• ds-fenwick-or-segment-tree-for-mutable-range-queries — 更新とクエリを O(log n) で行います

3. ソートと検索（優先度：高）

• srch-use-builtin-sort-not-hand-rolled — Timsort／introsort は手書きの実装より優れています
• srch-binary-search-on-sorted-data — bisect と、答えに対する二分探索
• srch-quickselect-for-k-th-element — k 番目の要素／中央値を平均 O(n) で求めます
• srch-counting-and-radix-sort-for-bounded-integer-keys — 整数キーでは O(n log n) より高速です
• srch-two-pointers-on-sorted-data — ソート済み配列で O(n)、スライディングウィンドウ

4. 動的計画法（優先度：高）

• dp-memoize-overlapping-subproblems — @cache で指数時間の計算を解消します
• dp-tabulate-when-recursion-depth-or-order-matters — ボトムアップ方式とローリング配列
• dp-define-state-precisely — 状態の定義が不十分だと、気づかないまま誤った答えになります
• dp-knapsack-pattern — 0/1 ナップサックと非有界ナップサック。ループの方向が正しさを左右します
• dp-bitmask-for-small-set-states — n ≤ ~20 では、n! を 2ⁿ · poly に削減します
• dp-prove-optimal-substructure-before-coding — 動的計画法には最適部分構造が必要です。コーディング前に検証してください

5. グラフアルゴリズム（優先度：高）

• graph-bfs-for-unweighted-shortest-path — O(V+E)、ヒープは不要です
• graph-dijkstra-for-non-negative-weights — 遅延削除を用いるヒープの変種
• graph-topological-sort-for-dependency-order — Kahn のアルゴリズムと DAG 上の動的計画法
• graph-represent-as-adjacency-list-not-matrix — 疎グラフには隣接リストが必要です
• graph-detect-cycles-during-dfs — 有向グラフ向けの 3 色方式
• graph-kruskal-or-prim-for-mst — Union-Find またはヒープを用いた MST

6. 分割統治／再帰（中〜高）

• divide-merge-sort-pattern-for-counting-inversions — マージのステップに反転数のカウントを組み込みます
• divide-watch-recursion-depth-and-stack — 反復処理にするか、スタックを増やします
• divide-meet-in-the-middle-for-subset-problems — 2ⁿ → 2^(n/2)
• divide-quickselect-vs-quicksort-partitioning — ランダムなピボット、3-way Dutch flag

7. 貪欲アルゴリズム（中）

• greedy-prove-exchange-argument-before-using — 貪欲法には正しさの証明が必要です
• greedy-sort-by-the-right-key-for-scheduling — 終了時刻、期限、価値／重さ
• greedy-interval-merge-and-sweep-line — イベント＋ソート＋線形スイープ
• greedy-huffman-and-priority-queue-greedies — ヒープを使って「繰り返し最小値を選択」

8. 文字列・シーケンスアルゴリズム（中）

• str-kmp-or-builtin-find-not-naive-search — 最悪時でも線形時間の部分文字列検索
• str-trie-for-prefix-queries — O(|query|) でオートコンプリート
• str-rolling-hash-for-multiple-substring-comparisons — 独立したハッシュを2つ使用します
• str-suffix-array-or-automaton-for-substring-queries — 高度な部分文字列検索ツール

9. 大規模処理・確率的アルゴリズム（中）

「大規模処理では珍しいものの、役に立つ」ツールボックスです。わずかな精度の低下と引き換えにメモリを桁違いに節約するスケッチ、RAM に収まらない入力向けのストリーミングプリミティブ、シャーディングの変更に耐える分散データ構造が含まれます。

• scale-bloom-filter-for-probabilistic-membership — 要素あたり1ビット対8バイト、偽陽性率1%
• scale-hyperloglog-for-cardinality-estimation — 約12 KB で数十億件のユニーク数をカウント
• scale-count-min-sketch-for-frequency-estimation — 固定メモリで頻出要素や頻度をクエリ
• scale-reservoir-sampling-for-streams — 長さ不明のストリームから一様な k 件のサンプルを取得
• scale-consistent-hashing-for-distributed-sharding — ノード変更時にすべてのキーではなく、k/n 個のキーを再割り当て
• scale-external-merge-sort-for-out-of-memory-data — RAM 8 GB で1 TBをソート
• scale-aho-corasick-for-multi-pattern-search — テキストを一度走査して m 個すべてのパターンを検索
• scale-minhash-lsh-for-near-duplicate-detection — 近似重複ペアを O(n) で検出（O(n²) ではありません）

使い方

質問に合ったカテゴリから始めてください。

• 「n = 10⁶ に適したアルゴリズムは何ですか？」 → comp-（入力サイズに依存）
• 「ループ内でリストを検索しています」 → ds-hash-map-for-keyed-lookup または comp-watch-for-quadratic-blowup-from-membership-in-list
• 「再帰が遅いです」 → dp-memoize-overlapping-subproblems と comp-derive-recurrences-via-master-theorem
• 「最短経路／連結性／順序付けのタスク」 → graph-
• 「価値を最大化するように項目を選ぶ」 → greedy-prove-exchange-argument-before-using から始め、うまくいかなければ dp-knapsack-pattern を使います
• 「文字列を検索／照合する」 → str-
• 「時間ではなくメモリが制約です」／「大規模データのサンプリング／集計／重複排除」／「シャーディング」 → scale-

コード例は Python で記述しています（幅広い読者にとって最も読みやすいためです）。考え方はどの言語にも応用できます。異なる場合は、同等の標準ライブラリ機能を記載しています。

リファレンスファイル

ファイル	説明
references/_sections.md	カテゴリの定義と順序
assets/templates/_template.md	新しいルール用のテンプレート
metadata.json	バージョンとリファレンス情報
AGENTS.md	自動生成された目次ナビゲーション

関連スキル

• complexity-optimizer — これらのルールが診断するパターンを見つける静的解析