算法复杂度

是什么，为什么存在

算法复杂度是一种资源增长模型。它把订单数、图的顶点数或字节数等输入规模，与算法所需工作量或额外存储联系起来。模型通常关注输入足够大时的行为，因此使用渐近记号（asymptotic notation）。

时间复杂度统计选定的工作单元，不直接统计秒数。单元可以是比较次数、哈希表操作次数、访问的节点数或解码的字节数。空间复杂度统计随输入规模变化的内存，通常把辅助工作空间与输入本身及必要输出占用的存储分开。

这个模型与基准测试回答不同问题。基准测试说明某个实现在特定数据、硬件、运行时和负载下的表现。复杂度则解释为什么输入翻倍后，工作量可能近乎不变、变为两倍或变为四倍。

这种区别让复杂度结论更持久。处理器速度和运行时优化可以改变常数，却无法挽救操作次数相对目标输入增长过快的实现。分析还能揭示取舍，例如用线性额外空间保存集合，避免二次增长的重复项搜索。

只要集合会增长、循环会嵌套、递归调用会分支，或服务会接收用户可控输入，就会用到复杂度。它能辅助代码审查、容量规划、API 设计、拒绝服务防护和数据结构选择。复杂度本身不能证明正确性、延迟或安全性。

有效的复杂度陈述会写明假设。「在哈希表约定下，包含 n 个条目时查找的期望复杂度为 O(1)」具有可操作性，「这个很快」则没有。陈述还应说明它描述最坏、期望、摊还还是其他情形。

复杂度只是多项要求之一。具有更好界限的实现仍可能出错、泄露数据、改变结果顺序，或超出较小的固定延迟预算。应先保留行为约定，再比较正确候选方案的资源增长。

渐近类别相同的两个实现，实际扩展能力也可能不同。一次线性扫描可能为每个元素分配对象，另一次则连续读取内存。共同的 O(n) 标签是比较的起点，不是结论。

工作原理

计数前先定义输入

第一步是选择输入维度。对于扫描一个数组的函数，n 可以表示数组长度。对于图，通常要同时保留顶点数 V 和边数 E；全部压成一个 n，就会隐藏图是稀疏还是稠密。

多个独立输入应该使用多个变量。把每个新商品与目录中的每个商品比较，需要 O(nm) 时间，其中 n 和 m 分别是两个集合的大小。称其为 O(n²)，就暗中假设二者总是一起增长。

输入的数值可能不同于其表示长度。对整数 x 试除到平方根附近，工作量与 √x 有关，但二进制整数只需要大约 log₂ x 位。分析密码与数值算法时，因此要说明规模指值、位数、行数还是字节数。

输入模型也可以包含结构参数。树的高度、字符串编码后的字节长度，或每个节点的最大邻居数，可能比元素总数更能预测成本。如果产品限制或恶意输入能让某个参数独立变化，就应保留它。

选择成本模型

应统计对当前决策足够稳定的操作。基于比较的搜索可以统计比较次数，解析器可以统计检查的字节数。如果把每次库函数调用都算作一步，就可能漏掉 includes()、sort()、字符串拼接或序列化内部依赖输入规模的工作。

模型可以有意抽象机器细节。在具体语言和数据表示允许时，通常把数组索引与定长算术视为常数时间。如果数值可以无限增长，对一千位整数做运算就不能再等同于机器字运算。

选定单元后，可以推导出 3n + 7 次比较这样的函数。渐近分析按增长方式归类函数，并忽略常数因子和低阶项，因此 3n + 7 属于 O(n)。被忽略的项对小输入和基准测试仍有影响，只是不改变增长类别。

峰值资源与累计工作是不同指标。依次分配并释放十个大小为 n 字节的缓冲区，峰值辅助空间为 O(n)，却会执行十次 O(n) 分配工作。应说清限制的是哪种资源，避免把内存结论误解为分配速率结论。

识别常见增长类别

常见类别构成逐级收紧的容量阶梯。它们描述增长形状，不承诺实际用时。

「常数时间」不等于瞬间完成，「线性」也不等于缓慢。一次 O(1) 的远程请求，可能比扫描二十个内存值的 O(n) 操作更久。当变化的输入大到足以让增长压过常数时，复杂度才成为决定因素。

多项式类别与指数类别的容量上限差异很大。指数搜索处理二十个选项时可能可行，处理一百个时则无法完成；如果行数硬性限制为五十，二次扫描也可能完全可以接受。批准或拒绝方案之前，要把类别换算到真实输入范围。

说明界限的含义

大 O 记号给出渐近上界：超过某个规模后，增长不会快于乘上常数因子的比较函数。大 Omega 记号给出下界，大 Theta 记号给出相互匹配的上界与下界。工程交流常用「大 O」指紧确增长类别，因此要确认对方是否只在陈述一个上界。

线性扫描的最坏情形是 O(n)，因为它可能检查所有元素。第一个元素就匹配时，最好情形是 O(1)。平均或期望界限需要输入分布、随机性假设或数据结构约定；它不是最好与最坏情形的算术平均值。

最坏情形分析给出上限，特别适合延迟预算或对抗性输入。假设与生产环境匹配时，期望分析可能更能预测常规运行。如果最坏情形明显不同并且确实可达，就应同时报告二者。

平均情况结论应说明具体对什么取平均。对象可以是所有输入排列、观测到的生产流量、随机哈希种子，或一系列操作。这些分布不能互换，昨天的流量样本也未必覆盖明天的滥用模式。

根据代码结构组合成本

顺序阶段的成本相加。先做 O(n) 验证，再做 O(n log n) 排序，总成本是 O(n + n log n)，可简化为 O(n log n)。简化并不允许删除验证，只是指出 n 增长后哪一项占主导。

嵌套工作往往使成本相乘。两个循环都遍历全部 n 个元素时，会产生 n² 次迭代，但嵌套循环不一定是二次复杂度。如果两个指针在整个运行中只向前移动，总成本仍可能是 O(n)，即使一个循环写在另一个内部。

每次按固定比例缩小问题的工作通常是对数复杂度。二分搜索每次比较都把有序范围减半，因此剩余减半次数与 log n 成正比。预先排序不是免费操作：先做 O(n log n) 排序再搜索一次，端到端成本并不是 O(log n)。

分析递归代码时，要看它创建多少子问题、子问题规模如何变化，以及递归调用之外还有多少工作。记忆化可以合并重复子问题，但缓存规模随后会进入空间界限。即使每个栈帧只做常数工作，深度为 n 的递归也会消耗 O(n) 栈空间。

分析依赖数据的循环时，可以求和，不要只看缩进。如果第 i 次迭代检查 i 个元素，总工作量就是 1 + 2 + ... + n，即 Θ(n²)。如果每个元素最多只被移除或越过一次，外观相似的嵌套结构也可能只合计为 Θ(n)。

统计空间与操作序列

辅助空间指输入与必要输出之外使用的内存。成对比较的重复项检查使用 O(1) 辅助空间，基于集合的检查最多保存 n 个标识符，使用 O(n) 空间。对输出敏感的算法还会单独报告输出空间，因为返回 k 个匹配项必然至少需要 O(k) 存储。

有些操作偶尔昂贵，但放到整个序列中很便宜。按几何倍数增长的数组扩容时有时要复制所有现有元素，不过 n 次追加的总复制量仍是线性。追加成本因此是 摊还 O(1) ，尽管单次追加可能达到 O(n)。

摊还分析与平均情况分析不是同义词。摊还分析限制任意相关操作序列的总成本，再把成本分摊到整个序列，不需要概率分布。平均情况分析则依赖输入或操作的分布方式。

空间分析需要生命周期边界，正如时间分析需要操作边界。每个请求使用的集合可以在请求结束后回收，进程级记忆化表则会跨请求累积。二者都可能相对各自的 n 保留 O(n) 个条目，但只有后者会让内存关联整个生命周期内的流量基数。

示例

以下示例统计模型中的操作次数，不对微型程序计时。结果可以复现，并能直接展示增长方式；常数与运行时行为是否适合真实服务，仍要通过后续测量判断。

每个计数器都是示例的一部分，不是通用性能分析器。它只记录相邻分析指定的操作，如果改变工作单元，就必须同时修改插桩与复杂度结论。

比较增长形状

第一个程序把五种复杂度类别变成粗略操作预算。输入采用二的幂，便于检查对数列。

把 n 扩大八倍，对数估算值只增加三步。同样的变化会让二次估算值变为六十四倍。这些函数经过刻意简化，不是在预测纳秒数。

n = 0 还说明了定义输入域的重要性。log₂ 0 不是有限的操作次数，因此真实约定需要处理基础情形。复杂度记号描述超过某个阈值后的增长，不能替代边界验证。

表格使用向上取整，因为一次不可分割的减半操作不可能只执行一部分。其他成本模型可能相差一个小常数，但仍属于同一个对数类别。

消除二次增长的重复项搜索

订单导入器需要拒绝重复标识符。第一个实现在不分配集合的情况下比较每一对标识符，第二个实现用集合记住已经见过的标识符。

function findDuplicatePairwise(orderIds) {
  let operations = 0;
  for (let left = 0; left < orderIds.length; left += 1) {
    for (let right = left + 1; right < orderIds.length; right += 1) {
      operations += 1;
      if (orderIds[left] === orderIds[right]) {
        return { duplicate: orderIds[left], operations };
      }
    }
  }
  return { duplicate: null, operations };
}

function findDuplicateWithSet(orderIds) {
  const seen = new Set();
  let operations = 0;
  for (const orderId of orderIds) {
    operations += 1;
    if (seen.has(orderId)) return { duplicate: orderId, operations };
    seen.add(orderId);
  }
  return { duplicate: null, operations };
}

const orders = ["A-102", "B-205", "C-330", "D-404", "C-330"];
console.log("pairwise:", findDuplicatePairwise(orders));
console.log("set:", findDuplicateWithSet(orders));

for (const size of [10, 100]) {
  const unique = Array.from({ length: size }, (_, index) => `O-${index}`);
  console.log(`unique ${size}: pairwise=${findDuplicatePairwise(unique).operations}, set=${findDuplicateWithSet(unique).operations}`);
}

pairwise: { duplicate: 'C-330', operations: 9 }
set: { duplicate: 'C-330', operations: 5 }
unique 10: pairwise=45, set=10
unique 100: pairwise=4950, set=100

没有重复项时，成对比较版本执行 n(n - 1) / 2 次相等比较，因此最坏时间为 Θ(n²)。在集合的哈希约定下，集合版本为每个标识符做一次成员检查，期望时间为 Θ(n)。它使用 Θ(n) 辅助空间，成对比较版本则使用 Θ(1)。

这些计数不能直接等同于 CPU 指令数，因为一次集合操作比一次字符串相等比较做的工作更多。不过输入包含一百个唯一标识符时，两者已经是 4,950 次模型操作与 100 次模型操作的差距。如果内存紧张或输入总是很小，应在预期交叉点附近对两个实现做基准测试。

较早出现重复项会减少两个实现实际执行的工作，却不会改变其最坏情形界限。测试中保留全部唯一的输入，才能迫使两个实现走完建立这些界限的路径。

观察追加操作的摊还成本

这个小型缓冲区暴露动态数组通常隐藏的扩容过程。每当追加时没有空槽，容量就翻倍，所以部分 push 会复制已有元素。

class OrderBuffer {
  #items = new Array(1);
  #size = 0;

  copiedSlots = 0;

  push(orderId) {
    if (this.#size === this.#items.length) {
      const grown = new Array(this.#items.length * 2);
      for (let index = 0; index < this.#size; index += 1) {
        grown[index] = this.#items[index];
        this.copiedSlots += 1;
      }
      this.#items = grown;
      console.log(`resize: capacity=${this.#items.length}, copied=${this.#size}`);
    }
    this.#items[this.#size] = orderId;
    this.#size += 1;
  }

  snapshot() {
    return this.#items.slice(0, this.#size);
  }
}

const buffer = new OrderBuffer();
for (let id = 1; id <= 8; id += 1) buffer.push(`O-${id}`);

console.log(`pushes=8, total copies=${buffer.copiedSlots}`);
console.log(buffer.snapshot().join(", "));

resize: capacity=2, copied=1
resize: capacity=4, copied=2
resize: capacity=8, copied=4
pushes=8, total copies=7
O-1, O-2, O-3, O-4, O-5, O-6, O-7, O-8

高成本的三次 push 分别复制一、二和四个槽位，八次追加总共复制七个槽位。继续扩展到容量十六时会增加八次复制，几何级数之和仍小于追加次数的两倍。这个总成本论证说明追加具有摊还 O(1) 复杂度。

按几何倍数增长是关键假设。如果容量每次只增加一个槽位，就会复制 1 + 2 + ... + (n - 1) 个元素，使整个追加序列达到 Θ(n²)。缓冲区还会保留未使用容量，因此其 O(n) 空间中的常数因子依然影响内存规划。

示例自行实现缓冲区，只是为了暴露计数过程。生产代码通常应使用运行时提供的集合，并依据它记录的行为，而不是替换成熟实现。

陷阱

把界限当作秒表

修复方法： 先用复杂度排除无法容纳目标输入的增长方式，再用代表性数据对剩余方案做基准测试，并报告单位、百分位、环境和方差。把推导出的操作次数与计时结果一起保留，让测量结果有可检查的解释。

为 n 选择错误含义

修复方法： 在复杂度之前先写简短输入模型，例如「n 行新数据、m 行目录数据，每个键 b 字节」。先保留独立变量，只有产品限制确实规定二者关系时再合并。

不写假设就声称平均复杂度

修复方法： 写明运行时或数据结构约定、键分布、随机性和冲突处理方式。如果单次慢请求也很重要，就增加最坏情形或百分位预算，并同时测试恶意输入和代表性输入。

隐藏重复的线性工作

修复方法： 展开循环体中每次调用的成本，并统计调用次数。用合适的索引或集合代替重复成员扫描，批量处理远程工作，再增加翻倍测试，记录操作次数或受控计时。

用无界空间换速度

修复方法： 在分析中加入辅助空间，并说明谁拥有这些条目。限制基数或生命周期，定义淘汰与清理方式，测试高唯一性流量；如果正确性不能依赖保留状态，还要提供无缓存路径。

只优化渐近标签

修复方法： 改变设计前，先记录支持的最大规模、当前操作次数和测得的交叉点。如果简单实现仍有充足余量，就接受它；同时设置回归阈值，明确何时需要重新评估取舍。

延伸阅读

• NIST 算法与数据结构词典：大 O 记号
• MIT OpenCourseWare：算法导论课程讲义
• MDN Web Docs：Set
• Python Wiki：内置容器的操作复杂度
• Princeton Algorithms：算法分析