1 / 4概念
Complexity Analysis
复杂度分析回答的是“输入变大十倍,代价会变成多少”。它不是背 O(n log n),而是在写代码之前判断哪种实现值得写、在容量翻倍时系统会不会先崩。
1 概念
1.1 一句话定义
复杂度分析用输入规模 n 的函数描述算法消耗的时间或空间,并只保留增长最快的项。它关心的是 n → ∞ 时的渐进行为,不是某台机器上的绝对毫秒数。
1.2 它解决什么问题
- 选实现:同一问题有 O(n²) 和 O(n log n) 两种写法,先判断 n 的量级再决定是否值得优化。
- 定容量:QPS 翻倍、数据量翻十倍时,先算增长阶,再做压测。
- 找瓶颈:嵌套循环、重复扫描、隐式拷贝通常比“语言快不快”更致命。
- 说清前提:最好/最坏/平均/摊还是四种不同承诺,不能混着用。
没有复杂度分析,团队只能用“跑得快”做决策;数据一涨,结论就失效。
1.3 不属于本页的内容
| 主题 | 去哪 |
|---|---|
| 排序、二分、图算法的具体流程 | Sorting & Searching、Graph Algorithms |
| 数组、链表、树、哈希表的实现 | Linear Structures、Trees & Heaps、Graph Structures |
| P、NP、NP 完全性 | Computational Complexity |
| 基准测试、profiler、火焰图 | 性能测试与可观测性相关页面 |
| 摊还数据结构(并查集、动态数组)的实现 | Linear Structures、Graph Structures |
1.4 关键术语
| 术语 | 含义 | 容易混淆的点 |
|---|---|---|
| 输入规模 n | 决定代价的自变量 | 不是“元素个数”永远;可能是位数、边数、矩阵维度 |
| O | 渐进上界,忽略常数 | 不是“精确运行时间” |
| Ω | 渐进下界 | 不是“最好情况” |
| Θ | 渐进紧确界,上下界同阶 | 不是“平均情况” |
| o / ω | 严格小于 / 严格大于 | 与 O / Ω 差一个等号 |
| 最坏 / 平均 / 最好 | 对输入分布的三种承诺 | 平均不是“均匀分布” |
| 摊还 | 一串操作的平均代价 | 不是概率期望 |
| 辅助空间 | 除输入外额外占用的空间 | 不是总内存 |
| 递归式 | 用自身描述代价的方程 | 不是所有递归都能用主定理 |
| 主定理 | 解 T(n)=aT(n/b)+f(n) 的工具 | 有适用条件,不是万能公式 |
2 机制
2.1 心智模型
把代价画成一条随 n 增长的曲线:常数是水平线,log n 增长极慢,n 是直线,n log n 略高于直线,n² 是抛物线,2ⁿ 是墙。复杂度分析只比较曲线的形状;两条同形状的曲线谁更低,要靠常数、缓存和实现来决定。
2.2 机制拆解
- 渐进定义:
f(n)=O(g(n))表示存在 c>0 和 n₀,使 n≥n₀ 时f(n) ≤ c·g(n);Ω 反过来;Θ 表示同时是 O 和 Ω。o 表示对任意 c>0 最终都小于 c·g(n)。 - 三种情况:最坏情况是“所有输入里代价最大的”;平均情况是对某个输入分布求期望;最好情况通常只用于说明下界,不用于容量规划。
- 摊还分析:一个操作很贵,但连续操作的总代价可以被前面的便宜操作摊平。动态数组扩容是 O(n),但 n 次 push 总代价 O(n),所以单次摊还 O(1)。
- 递归式:先写
T(n)=aT(n/b)+f(n),再用代入法、递归树或主定理求解;不能直接看出时,先猜再归纳。 - 空间复杂度:辅助空间 + 递归栈 + 输出;递归深度 O(n) 的算法可能比原地算法更早爆内存。
- 模型代价:默认每次基本操作 O(1),但大整数运算、哈希、比较字符串都不是免费的;必要时把这些代价算进去。
2.3 完整枚举
渐进记号:
| 记号 | 含义 | 例子 | 常见误用 |
|---|---|---|---|
| O | 上界,f ≤ c·g | 3n²+2n = O(n²) | 把 O 当成“精确阶” |
| Ω | 下界,f ≥ c·g | n²/2 = Ω(n²) | 把 Ω 当成最好情况 |
| Θ | 紧确界,上下界同阶 | 2n+1 = Θ(n) | 对只有上界的算法硬说 Θ |
| o | 严格小于,增长更慢 | n = o(n²) | 与 O 混用 |
| ω | 严格大于,增长更快 | n² = ω(n) | 与 Ω 混用 |
常见增长阶(n 为输入规模):
| 阶 | 名称 | n=10 | n=100 | n=1000 | 典型来源 |
|---|---|---|---|---|---|
| O(1) | 常数 | 1 | 1 | 1 | 数组下标、哈希平均 |
| O(log n) | 对数 | 3 | 7 | 10 | 二分、平衡树高度 |
| O(n) | 线性 | 10 | 100 | 1000 | 单次扫描 |
| O(n log n) | 线性对数 | 33 | 664 | 9966 | 比较排序、分治 |
| O(n²) | 平方 | 100 | 10⁴ | 10⁶ | 双重循环、冒泡 |
| O(n³) | 立方 | 1000 | 10⁶ | 10⁹ | Floyd、矩阵乘法朴素版 |
| O(2ⁿ) | 指数 | 1024 | 10³⁰ | 10³⁰¹ | 子集枚举、暴力搜索 |
| O(n!) | 阶乘 | 3.6M | 巨大 | 巨大 | 全排列 |
2.4 关键数字与复杂度
| 指标 | 量级 | 说明 |
|---|---|---|
| log₂ 1000 | ≈ 10 | 二分 1000 个元素最多 10 次比较 |
| n log₂ n(n=10⁶) | ≈ 2×10⁷ | 现代 CPU 秒级可完成 |
| n²(n=10⁶) | 10¹² | 通常不可接受 |
| 每秒基本操作 | 10⁸–10⁹ | 取决于语言、内存访问和并行 |
| 单次内存访问 | 约 100 ns | 缓存未命中会放大常数 |
| 递归栈深度 | 10³–10⁵ | 取决于线程栈大小 |
3 实践
3.1 最小示例
# 1) 双重循环:n 次外层,每次内层最多 n 次,O(n²)。
for i in 0..n-1:
for j in 0..n-1:
work(i, j)
# 2) 每次减半:O(log n)。
while lo < hi:
mid = (lo + hi) / 2
...
# 3) 归并排序:T(n) = 2T(n/2) + O(n),主定理第二类,O(n log n)。
MERGE_SORT(a):
if |a| <= 1: return a
left = MERGE_SORT(a[0..n/2])
right = MERGE_SORT(a[n/2..n])
return MERGE(left, right)
# 主定理:T(n) = aT(n/b) + f(n),令 c = log_b(a)。
# 1. f(n) = O(n^(c-ε)) -> T(n) = Θ(n^c)
# 2. f(n) = Θ(n^c log^k n) -> T(n) = Θ(n^c log^(k+1) n)
# 3. f(n) = Ω(n^(c+ε)) 且正则 -> T(n) = Θ(f(n))
#
# 例:T(n) = 2T(n/2) + n,c = 1,f(n) = Θ(n^1) -> Θ(n log n)
# 例:T(n) = 2T(n/2) + 1,c = 1,f(n) = O(n^(1-ε)) -> Θ(n)
3.2 常用操作与参数
| 操作 | 做法 | 说明 |
|---|---|---|
| 数循环 | 看每层上界与乘数 | 嵌套相乘,顺序相加 |
| 写递归式 | 子问题数 × 子问题规模 + 合并代价 | 先写对再解 |
| 解递归式 | 主定理、递归树、代入法 | 主定理不适用时换方法 |
| 算空间 | 辅助数组 + 递归栈 + 输出 | 不要只算输入 |
| 摊还 | 聚合、记账、势能 | 说明“总代价 / 操作数” |
| 验证 | 小规模计数 + 大规模计时 | 渐进正确不代表常数可接受 |
| 对比 | 同输入规模、同硬件、同数据分布 | 避免拿不同 n 比较 |
3.3 标准流程
- 定义输入规模 n:元素数、边数、位数、矩阵维数,选真正驱动代价的那个。
- 找主导操作:比较、赋值、内存访问、哈希、递归调用。
- 写出每层循环/递归的代价,得到 T(n) 或求和式。
- 用主定理、递归树或归纳求解;同时写出空间复杂度。
- 检查前提:最坏/平均/摊还、是否允许随机化、是否有隐藏拷贝。
- 用 n=10、100、1000 的实测验证;若实测与理论冲突,先怀疑输入规模或常数,不要先怀疑理论。
3.4 与相邻技术的组合
- 数据结构:同一操作在数组、链表、哈希表上是不同阶;先选结构再谈算法。
- 排序:比较排序的下界 Ω(n log n) 来自决策树,不是某个实现慢。
- 图算法:复杂度必须带 V 和 E;邻接矩阵与邻接表会改变同一算法的阶。
- 基准测试:渐进分析负责筛选候选,profiler 负责找常数和缓存问题。
- 容量规划:把 QPS、数据量、增长率先换成 n,再套增长阶。
3.5 选型维度
| 维度 | 取值 | 影响 |
|---|---|---|
| n 的量级 | 小 / 中 / 大 | 小 n 时常数可能压过阶 |
| 输入分布 | 随机 / 近有序 / 对抗 | 最坏与平均可能差一个量级 |
| 内存 | 紧张 / 充足 | 时间换空间是否可行 |
| 实时性 | 硬实时 / 尽力而为 | 最坏情况比平均更重要 |
| 实现复杂度 | 低 / 高 | 复杂算法更容易写错 |
| 可验证性 | 易 / 难 | 是否有对拍和基准 |
3.6 决策规则
- 先看 n 的量级:n ≤ 几十,O(n²) 往往比 O(n log n) 的复杂实现更快。
- 有硬实时或 SLA 要求时,用最坏情况,不用平均情况。
- 只关心总吞吐且操作成串出现时,用摊还分析。
- 递归深度随 n 线性增长时,先算栈空间;必要时改迭代。
- 库函数的“O(1)”要看前提:哈希平均 O(1),最坏 O(n)。
- 不同阶的算法不要只比较一次实测;先做规模扫描,再看曲线是否分叉。
3.7 替代方案对比
| 方法 | 优势 | 代价 | 适用 |
|---|---|---|---|
| 渐进分析 | 快速、可比较、与机器无关 | 忽略常数和缓存 | 选算法、估容量 |
| 基准测试 | 反映真实常数与缓存 | 受环境、数据分布影响 | 最终选型 |
| Profiler | 找热点和调用链 | 有观测开销 | 优化现有系统 |
| 摊还分析 | 解释“偶发很贵”的结构 | 不给出单次最坏 | 动态数组、并查集 |
| 平均情况分析 | 贴近典型负载 | 依赖分布假设 | 随机化、哈希 |
| 对抗分析 | 给出保证 | 可能过于保守 | 安全、实时系统 |
3.8 何时不该用
- n 很小且固定:直接测,不要为 O(n²)→O(n log n) 引入复杂依赖。
- 常数项占主导:渐进更优但实现慢十倍时,先用实测说话。
- 输入分布未知:平均情况分析只是假设,不能当成保证。
- 缓存/IO 是瓶颈:O(n) 的随机访问可能比 O(n log n) 的顺序访问更慢。
- 算法有隐藏的 O(n) 拷贝:只数循环会漏掉真正的大头。
4 边界
4.1 典型故障
| 症状 | 根因 | 处理 |
|---|---|---|
| 小数据上更慢 | 忽略常数和递归开销 | 小 n 用简单算法 |
| 理论 O(n log n) 实测却像 O(n²) | 隐藏拷贝、字符串拼接、重复分配 | 用 profiler 找分配点 |
| 平均很快、偶发超时 | 只看了平均,没看最坏/尾延迟 | 看 P99、最坏输入 |
| 摊还 O(1) 被当成单次 O(1) | 把总代价平均误读为每次上限 | 单次最坏要单独说明 |
| 递归式解错 | 子问题规模或合并代价写错 | 用递归树/代入法复核 |
| 内存先爆 | 只算时间,没算辅助空间和栈 | 同时写空间复杂度 |
| 不同实现比较结论反复 | 输入规模、分布、硬件不一致 | 固定基准与规模扫描 |
| 哈希表退化成链表 | 哈希冲突被对抗构造 | 随机化哈希、限制负载因子 |
| 大整数运算被当 O(1) | 位数增长未被计入 | 把位数作为输入规模 |
4.2 反模式
| 做法 | 后果 | 替代 |
|---|---|---|
| 只看 Big-O 不看常数 | 选了“更优”但更慢的实现 | 规模扫描 + 基准 |
| 用平均情况承诺 SLA | 尾延迟失控 | 看最坏/P99 |
| 把摊还当单次保证 | 偶发长停顿 | 单次最坏单独评估 |
| 忽略输入规模的定义 | 结论对不上实测 | 先写清 n 是什么 |
| 用不同 n 比较算法 | 结论无意义 | 同规模、同分布 |
4.3 可观测信号
增长阶的理论值与实测曲线是否同形、单次操作的 P50/P99/P999、分配次数、缓存未命中、递归深度、哈希冲突率。基准测试要记录 n、数据分布、硬件和版本,否则结论不可复现。
4.4 安全 / 性能 / 一致性边界
- 正确性:复杂度分析不证明算法正确;先有正确性,再谈阶。
- 最坏保证:安全敏感场景不能只依赖平均情况;对抗输入会专门打最坏。
- 空间:O(n) 辅助空间在嵌入式或高并发下可能先于时间成为瓶颈。
- 模型:O(1) 的基本操作假设不等于真实机器上的 O(1);内存层级会改变常数,极端情况下改变最优选择。