computer-science-algorithms

社区经典计算机科学算法最佳实践

这是一份面向实践者的参考指南，帮助你正确选择和实现经典算法与数据结构。内容按对执行生命周期的影响排序：最早做出的决策（渐进复杂度、数据结构选择）会层层影响后续工作，因此表格靠前的规则最重要。

范围： 涵盖日常生产代码审查、合理的面试题／竞赛题，以及大规模场景下的工具箱（sketch、流式处理、分布式原语）中常见的模式，并非 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-	严重	O() 复杂度级别选错，其他优化都会失去意义
2	数据结构选择	ds-	严重	容器决定了哪些操作成本低
3	排序与搜索	srch-	高	贪心、双指针、扫描线、答案二分的基础
4	动态规划	dp-	高	将指数级复杂度转化为多项式级复杂度
5	图算法	graph-	高	网络、依赖关系、路由、调度都可归约为图问题
6	分治／递归	divide-	中高	对数级加速；需注意栈深度和递推关系陷阱
7	贪心算法	greedy-	中	正确时速度快，错误时却不易察觉
8	字符串与序列算法	str-	中	模式匹配、解析、子串查询
9	大规模与概率算法	scale-	中	sketch、流式处理、分布式原语——适用场景有限，但适用时至关重要

快速参考

1. 渐进复杂度与算法选择（严重）

• 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 — 平均 O(n) 找到第 k 个元素 / 中位数
• 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 — 有向图的三色标记法
• graph-kruskal-or-prim-for-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 — 随机枢轴；三向荷兰国旗划分

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 — 请使用两个独立的哈希
• str-suffix-array-or-automaton-for-substring-queries — 处理复杂子串查询的强大工具

9. 可扩展性与概率算法（中等难度）

这套工具箱专为“少见但在大规模场景下很有价值”的问题准备：用微小的精度损失换取数量级的内存节省的草图算法、用于处理无法装入 RAM 的输入的流式处理原语，以及能够适应分片变化的分布式结构。

• scale-bloom-filter-for-probabilistic-membership — 每个元素 1 bit，而非 8 bytes；误报率为 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 — 使用 8 GB RAM 对 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 — 静态分析，用于查找这些规则所诊断的模式