# 算法复杂度

Source: https://codewiki.com/zh/foundations/algorithmic-complexity/

> - **what**: 算法复杂度描述算法所需时间或额外存储如何随输入增长，不受某一台机器或某一次基准测试限制。
> - **trap**: `O(n)` 表示增长上界，不表示具体时长；`n` 必须对应真正决定工作量的输入维度。
> - **fix**: 先定义输入规模与成本模型，再推导相关情形下的时间、空间界限，最后测量代表性极限并选择实现。

## 是什么，为什么存在

算法复杂度是一种资源增长模型。它把订单数、图的顶点数或字节数等输入规模，与算法所需工作量或额外存储联系起来。模型通常关注输入足够大时的行为，因此使用渐近记号（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)` 分配工作。应说清限制的是哪种资源，避免把内存结论误解为分配速率结论。

### 识别常见增长类别

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

| 类别 | 常见来源 | 较大的 `n` 翻倍后的影响 |
| --- | --- | --- |
| `O(1)` | 按索引直接查找 | 大致不变 |
| `O(log n)` | 不断把剩余范围减半 | 大约多一步 |
| `O(n)` | 每个元素访问一次 | 工作量大约翻倍 |
| `O(n log n)` | 在对数层级中处理每个元素 | 略多于两倍 |
| `O(n²)` | 比较每一对元素 | 工作量大约变为四倍 |
| `O(2ⁿ)` | 探索每种子集选择 | `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)` 个条目，但只有后者会让内存关联整个生命周期内的流量基数。

## 示例

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

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

### 比较增长形状

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

<!-- quick -->

```javascript
// file: growth_table.js
const estimates = [
  ["O(1)", () => 1],
  ["O(log n)", (n) => Math.ceil(Math.log2(n))],
  ["O(n)", (n) => n],
  ["O(n log n)", (n) => n * Math.ceil(Math.log2(n))],
  ["O(n^2)", (n) => n * n],
];

for (const inputSize of [8, 64, 512]) {
  const row = estimates
    .map(([label, steps]) => `${label}=${steps(inputSize)}`)
    .join(", ");
  console.log(`n=${inputSize}: ${row}`);
}
```

```text
n=8: O(1)=1, O(log n)=3, O(n)=8, O(n log n)=24, O(n^2)=64
n=64: O(1)=1, O(log n)=6, O(n)=64, O(n log n)=384, O(n^2)=4096
n=512: O(1)=1, O(log n)=9, O(n)=512, O(n log n)=4608, O(n^2)=262144
```


<!-- /quick -->

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

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

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

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

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

```javascript
// file: duplicate_orders.js
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}`);
}
```

```text
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` 会复制已有元素。

```javascript
// file: amortized_buffer.js
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(", "));
```

```text
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)` 空间中的常数因子依然影响内存规划。

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

## 陷阱

### 把界限当作秒表

> **陷阱:** 声称一个 `O(n)` 函数耗时「n 毫秒」，混淆了增长类别与具体时长。不同操作、常数、运行时、硬件、缓存和工作负载，可能让结果在实际规模下反转。

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

### 为 `n` 选择错误含义

> **陷阱:** 把双输入连接称为 `O(n²)`，会隐藏其中一侧有界、另一侧增长的情况；称为 `O(n)`，又可能隐藏第二个无界维度。用数值本身代替编码长度，还可能产生指数级误导。

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

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

> **陷阱:** 如果键可能来自对抗性输入、哈希函数未知，或延迟目标不允许偶发长暂停，那么「平均 `O(1)` 查找」并不完整。最好情形也不能证明正常输入的分布。

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

### 隐藏重复的线性工作

> **陷阱:** 生成代码和手写代码都常把 `includes()`、`find()`、数组展开、头部删除、序列化或数据库查询放进循环。可见循环是线性的，但循环体可能反复扫描或复制不断增长的数据，让整条路径变成二次复杂度。

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

### 用无界空间换速度

> **陷阱:** 缓存、记忆化表或「已访问」集合可以改善时间界限，却可能永远为每个不同输入保留一个条目。对于长寿命进程或用户可控的键，这种优化会变成耗尽内存的路径。

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

### 只优化渐近标签

> **陷阱:** 只为把 `O(n)` 改成期望 `O(1)` 而重写清晰的有界代码，可能增加分配、同步、缓存失效错误和更差的尾延迟。新界限解决的输入规模，也许产品永远不会达到。

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

<!-- deep -->

## 把复杂度界限变成工程决策

### 界限是带量词的陈述

写出 `T(n) = O(g(n))`，是在声称存在常数 `c` 和 `n₀`，使每个 `n ≥ n₀` 都满足 `T(n) ≤ c g(n)`。阈值允许小输入有不规则表现，常数则允许形状相同的实现做不同数量的工作。只有大 O 记号时，并没有声称 `g` 是最小的有效上界。

产品上限从技术上可以让所有可接受输入都被一个常数约束，但因此把每个操作都称为 `O(1)`，会让模型失去价值。应按自然变量分析增长，再单独说明强制上限。这样既保留有效比较，也给出具体运行保证。

例如，`3n + 7` 同时属于 `O(n)` 和 `O(n²)`，但只有线性描述是紧确的。上下界匹配时，有效的审查会要求给出 `Θ(n)`。某个实现的下界也不同于底层问题的下界；一个缓慢实现不能证明所有解法都必须缓慢。

### 输入形状可能比输入数量更重要

两个输入即使 `n` 相同，也可能走不同路径。提前退出取决于匹配位置，快速排序变体取决于划分是否平衡，图遍历取决于顶点数与边数，哈希表则取决于冲突情况。应报告选择这些路径的参数或情形，不要用平均值抹掉区别。

在信任边界上，对抗性输入需要单独处理。请求正文可能强制触发深层递归、病态匹配、过多哈希冲突或巨量输出，即使普通测试数据成本很低。因此，复杂度审查也是滥用场景分析的一部分，而不只是优化工作。

输出规模本身可以产生下界。如果端点必须返回 `k` 条匹配记录，发出这些记录至少需要 `Ω(k)` 时间，线上传输通常也至少需要 `Ω(k)` 字节。分页可以限制单次响应，但计算总数或保留游标可能只是把工作转移到别处。

稀疏表示与稠密表示说明了多个参数的重要性。邻接表占用 `Θ(V + E)` 空间，完整矩阵无论存在多少条边都占用 `Θ(V²)` 空间。如果不知道图的密度和产品所需操作，任何一个标签都不完整。

### 常数与交叉点仍然真实存在

渐近表现更好的实现，可能在产品允许的所有输入上都落后。构建集合需要分配内存和计算哈希，而扫描小数组只是一段缓存友好的短循环。决策应说明支持的输入范围，并通过可复现测量找出交叉点。

硬件与运行时行为会以有规律的方式改变常数。连续访问可利用缓存，分配可能触发垃圾回收，分支模式会影响处理器，库中的向量化代码可能胜过用户代码中更少的操作次数。这些事实是在细化模型，不会让增长分析失效。

远程调用需要单独的维度和预算。把 `n` 次本地操作改成 `n` 次数据库查询，仍可能被写成 `O(n)`，但延迟与服务负载会变得无法接受。除本地 CPU 操作外，还要统计往返次数、字节数、并发量和下游工作。

并发可以改变耗时，却不一定减少总工作量。并行运行 `n` 个独立请求可能缩短关键路径，同时仍保留 `Θ(n)` 个下游操作，并增加峰值连接数或内存。并行性主导设计时，应分别报告工作量、关键路径长度和资源限制。

### 用翻倍测试验证模型

翻倍测试在输入形状和环境稳定时，依次运行规模为 `n`、`2n`、`4n` 及更大的受控输入。比值接近二通常暗示线性增长，接近四暗示二次增长，缓慢上升的比值可能符合 `n log n`。这只是实现对已测范围的证据，不是数学证明。

与短时间计时相比，插桩计数通常更容易诊断。先统计比较次数、访问节点数、分配次数、复制字节数、查询数和保留条目数，再用基准测试检查常数与系统效应。如果计数与推导不一致，应先检查隐藏工作或错误的输入模型，再开始调优。

测量需要书面流程。固定运行时与依赖版本，以确定方式生成数据，在适用时分开预热和稳定运行阶段，重复足够样本，并报告分布而不是单次最快结果。还要保留正确性断言，避免某个实现靠跳过工作取得速度优势。

不要用两个有噪声的数据点拟合增长类别。应使用足够多的规模以越过固定启动成本，尽可能检查操作计数，并绘图或制表查看比值。在测试可能耗尽共享内存或压垮外部依赖之前停止增大输入。

### 把限制换算成预算

应从支持的最大输入开始，而不是只看复杂度记号。把该值代入保守的操作数与内存估算，计入并发请求，再与 CPU、延迟和内存预算比较。如果一次请求就能耗尽全部预算，即使典型输入很小，也要增加准入限制。

最终决策应记录选定实现、输入范围、界限与对应情形、假设、测得的交叉点，以及超过限制时的回退方式。这样后续变化才可审查。当数据形状或服务限制改变时，应重新推导并测量，而不是重复旧标签。

超过限制时必须以可预测方式失败。应尽可能在高成本解析之前拒绝超大请求，对输出分页，限制递归或队列，并为远程工作设置超时。如果运行时保护能执行复杂度界限背后的输入假设，这份书面界限才最有用。

<!-- /deep -->

[检查点: foundations/algorithmic-complexity](https://codewiki.com/zh/foundations/algorithmic-complexity/#checkpoint)

## 延伸阅读

- [NIST 算法与数据结构词典：大 O 记号](https://xlinux.nist.gov/dads/HTML/bigOnotation.html)
- [MIT OpenCourseWare：算法导论课程讲义](https://ocw.mit.edu/courses/6-006-introduction-to-algorithms-fall-2011/pages/lecture-notes/)
- [MDN Web Docs：`Set`](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Set)
- [Python Wiki：内置容器的操作复杂度](https://wiki.python.org/moin/TimeComplexity)
- [Princeton Algorithms：算法分析](https://algs4.cs.princeton.edu/14analysis/)