algorithmic-complexity-review

dot-skills 算法复杂度（Big-O）最佳实践

查找、分类并修复代码中的算法复杂度（Big-O）问题，不限编程语言。这 8 个类别中的 39 条规则涵盖了生产代码中绝大多数意外出现的二次、指数级和 N+1 性能问题：嵌套迭代、循环不变量 I/O、数据结构不匹配、递归爆炸、重复计算、集合构建反模式、搜索与排序选择，以及空间陷阱。

适用场景

在以下情况下使用此技能：

• 审查拉取请求或函数中的性能回归
• 被问到“为什么这么慢？”或“能不能让它更快？”
• 重构热点路径或处理用户规模输入的函数
• 阅读包含以下内容的代码：嵌套循环、迭代中的 .includes/.find/x in list、循环中的 ORM 访问、没有记忆化的递归、通过 += 或展开运算符构建字符串/数组、迭代中的文件/数据库 I/O
• 审查处理列表、树或流的代码，且其规模会不断增长

工作流：查找、分类、修复

此技能针对任何待审查代码，按三个步骤组织工作流：

1. 查找 — 扫描可疑模式

优先查找以下结构信号（命中率最高）：

信号	可能的类别	首先检查的规则
两层嵌套的 for 循环	nested-	nested-explicit-quadratic-loops
循环中的 .includes / .find / x in list	nested-	nested-includes-in-loop
循环中的 ORM 访问（for o in orders: o.customer.x）	io-	io-n-plus-one-query
for-of 中的 await fetch	io-	io-sequential-await-in-loop
使用 array.find“连接”两个数组	ds-	ds-hashmap-for-keyed-access
参数存在重叠的递归函数	rec-	rec-memoize-overlapping-subproblems
循环中的 s = s + part 或 [...acc, x]	build-	build-avoid-quadratic-string-concat、build-avoid-spread-in-reducer
循环内调用 sorted(...)	search-	search-sort-once-outside-loop
readlines() / 加载整个文件	space-	space-stream-dont-load

2. 分类 — 推导 Big-O

根据代码结构计算复杂度：

结构	复杂度
遍历 n 个项目的单层循环，循环体为 O(1)	O(n)
分别遍历 n / m 个项目的两层嵌套循环	O(n*m)
循环调用 O(n) 操作（.includes、.find、x in list）	O(n*m)，常被误判为 O(n)
未使用记忆化的递归 f(n) = f(n-1) + f(n-2)	O(2ⁿ)
递归 f(n) = 2*f(n/2) + O(n)	O(n log n)
递归 f(n) = 2*f(n/2) + O(1)	O(n)（完整遍历树）
递归 f(n) = f(n/2) + O(1)	O(log n)
循环中的 s = s + part	O(n²)（字符串不可变）
reduce 中的 [...acc, x]	O(n²)（展开时复制）
遍历 n 个项目的循环内执行查询/RPC	O(n) 次往返

拿不准时，问自己：“输入翻倍时，运行时间大约会翻倍（线性）、变为四倍（二次），还是增长得更快（指数级）？” 这就是实用的复杂度类别。

3. 修复 — 应用匹配规则中的模式

references/ 中的每个参考文件都是一个 {category}-{slug}.md，包含：

• 模式为何重要（级联效应）
• 一个标注了代价的 Incorrect 代码示例
• 一个展示最小差异的 Correct 示例
• 何时不应应用此修复（规则存在例外）

刻意采用最小差异理念：目标是让 Agent 清楚看到，只需修改多少行就能改变复杂度类别。

按优先级排列的规则类别

#	类别	前缀	影响	规则数
1	嵌套迭代模式	nested-	严重	6
2	循环不变的 I/O 和 N+1	io-	严重	5
3	数据结构不匹配	ds-	高	6
4	递归复杂度	rec-	高	5
5	冗余计算	compute-	中高	5
6	集合构建	build-	中	4
7	搜索与排序选择	search-	中	4
8	空间复杂度陷阱	space-	中低	4

完整的排序依据请参见 references/_sections.md。

快速参考

1. 嵌套迭代模式（严重）

• nested-explicit-quadratic-loops — 用基于哈希的单次遍历替代成对循环
• nested-includes-in-loop — 避免在循环中使用 .includes() / .indexOf()
• nested-find-in-loop — 预先建立索引查找，避免每次迭代都调用 .find()
• nested-cartesian-comparison — 按键分组，避免笛卡尔积比较
• nested-set-operations-on-arrays — 使用集合执行交集、并集和差集运算
• nested-substring-search-in-loop — 只分词一次，避免为每种模式重新扫描

2. 循环不变的 I/O 和 N+1 查询（严重）

• io-n-plus-one-query — 一次往返获取相关数据，消除 N+1 查询
• io-sequential-await-in-loop — 并行运行彼此独立的异步操作
• io-batch-instead-of-per-item — 使用批量端点，而非逐项调用
• io-file-read-in-loop — 在紧密循环之外读取或查询文件状态
• io-missing-eager-load — 预加载将要访问的 ORM 关联

3. 数据结构不匹配（高）

• ds-hashmap-for-keyed-access — 按键将记录存储在哈希映射中，而不是使用并行数组
• ds-heap-for-top-k — 使用堆查找前 k 项，而不是完整排序后再切片
• ds-deque-for-front-operations — 在头部插入和移除元素时使用双端队列
• ds-counter-for-histograms — 使用 Counter / 多重集进行频次统计
• ds-sorted-structure-for-range-queries — 使用有序结构执行范围查询
• ds-trie-for-prefix-search — 使用字典树进行前缀搜索

4. 递归复杂度（高）

• rec-memoize-overlapping-subproblems — 对存在重叠子问题的递归进行记忆化
• rec-tabulate-bottom-up — 使用自底向上的制表法消除递归开销
• rec-iterative-for-deep-recursion — 使用显式栈代替深度递归
• rec-prune-with-bounds — 使用边界和约束剪枝递归搜索
• rec-share-memo-across-top-level-calls — 在顶层调用之间共享记忆化结果

5. 冗余计算（中高）

• compute-hoist-loop-invariants — 将循环不变量计算移到循环外
• compute-precompile-regex — 预编译正则表达式模式
• compute-cache-expensive-pure-results — 缓存开销较大的纯函数结果
• compute-cache-property-lookup — 在热点循环中缓存重复的属性查找结果
• compute-defer-or-short-circuit — 延迟执行或短路可能不需要的工作

6. 集合构建（中）

• build-avoid-quadratic-string-concat — 使用 join 或构建器构建字符串，而非反复拼接
• build-avoid-spread-in-reducer — 推入可变累加器，而非使用展开运算符
• build-avoid-immutable-object-spread — 先用普通对象构建，再冻结
• build-presize-when-length-known — 已知长度时预先调整集合大小

7. 搜索与排序选择（中）

• search-binary-search-on-sorted — 对已排序数据使用二分查找
• search-sort-once-outside-loop — 在循环外排序一次，而非每次迭代都排序
• search-quickselect-not-full-sort — 使用 quickselect 查找第 k 个元素，而非完整排序
• search-build-index-once-amortize — 查询占主导时只构建一次索引

8. 空间复杂度陷阱（低中）

• space-stream-dont-load — 对大型输入使用流式处理，而非一次性全部加载
• space-generators-over-intermediate-lists — 使用生成器管道处理，而非物化中间列表
• space-shallow-not-deep-copy — 使用浅拷贝（或不拷贝），而非深度克隆
• space-release-retained-references — 释放阻止垃圾回收的引用

使用方法

1. 先查看上方的 Find 信号表，找到最可能匹配的模式。
2. 打开匹配的参考文件，查看原因（WHY）和最小差异修复方案。
3. 如果要从头分类复杂度，请使用 Classify 表，根据代码结构推导 Big-O。
4. 提出修复方案时，请注明规则的文件路径，以便审阅者核实推理。
5. 有关类别排序的理由，请参阅 references/_sections.md；添加新规则时，请参阅 assets/templates/_template.md。

参考文件

文件	描述
references/_sections.md	类别定义、影响级别和排序依据
assets/templates/_template.md	添加新规则的模板
metadata.json	领域、类型和来源引用

相关技能

• bug-review — 多轮 PR Bug 审查（这项技能专注于性能问题，可作为其补充）
• 某种语言的最佳实践技能（React、Python、Go）——涵盖 Big-O 之外的惯用法；对于性能关键型审查，可与这项技能搭配使用