复杂度分析与大 O

环境：Windows 11 x64，GCC 13.1.0，g++ -std=c++17 -O2。下面所有毫秒数、比较次数、搬移次数都是本机实测。绝对值依赖机器，比值和结论可以复现。

一、大 O 说的是”增长率”，不是”快慢”

O(f(n)) 的定义只关心 n → ∞ 时的上界，因此它丢掉了常数和低阶项。这带来两个必须记住的后果：

O(n) 不一定比 O(n log n) 快——如果前者的常数是一百万。
同一个 O(n²) 内部，实现差别可以是十几倍（第四节实测）。

所以大 O 用来排除数量级错误，不能用来做精细选型。精细选型要靠实测。

实测：n 翻倍，耗时变几倍

复杂度	n	耗时	n 翻倍时的比值
`O(n)` 累加	100 000	0.02 ms	—
	200 000	0.05 ms	2.5×
	400 000	0.10 ms	2.0×
`O(n²)` 双重循环	20 000	31.90 ms	—
	40 000	127.38 ms	4.0×
	80 000	520.99 ms	4.1×
`O(n log n)` 排序	1 000 000	95.33 ms	—
	2 000 000	183.20 ms	1.92×

O(n²) 稳定地 4 倍、O(n) 稳定地 2 倍——这就是”增长率”的直观含义。

排序那一行的比值略低于理论值 2.02，是因为我把填随机数和分配内存的 O(n) 成本也算进了计时（nlogn_work 里包含 vector 分配 + mt19937 填数）。基准测试里混进与被测算法无关的线性项，就会把超线性增长”稀释”成线性——这是最常见的测不准原因之一。

二、比较次数：把 log 和 n 摆在一起看

100 万个有序元素，查找最后一个（对线性而言的最坏情况）：

二分 20 次比较   线性 1000000 次比较   log2(1000000) = 19.93

20 次对一百万次，5 万倍。这就是为什么”每次请求都线性扫一遍百万级列表”是致命设计。

但注意前提：数据必须在 L1/L2 里。二分的 20 次比较是 20 次依赖跳转（每次地址由上一次结果决定），无法并行；线性的 100 万次比较是顺序流，能被预取和 SIMD 吞掉。所以数据一大、访问不命中缓存时，二分的优势会被侵蚀——但也不会翻转，见第六节。

三、摊还分析：为什么 `push_back` 是 O(1)

单次 push_back 在需要扩容时是 O(n)，但整体是 O(1)。实测 10 万次插入：

扩容 18 次，累计搬移 131071 个元素 ⇒ 摊还 1.31 个/次插入
最终 capacity=131072（不是 100000，倍增留下的余量）

数学上，倍增策略下搬移总量是等比级数：

2^0 + 2^1 + ... + 2^17 = 2^18 - 1 = 262143   （本机实测 131071，因为 libstdc++ 从 capacity=1 起按 2 倍走，最后一次未触发）

关键是它 < 2n。所以 n 次插入的总成本是 O(n)，摊到每次 O(1)。

三个直接推论：

倍增因子不影响阶，只影响常数：1.5 倍（MSVC）比 2 倍（libstdc++）多几次扩容，但都是 O(1) 摊还；2 倍的优势是”之前的所有块可以合并复用”（2^k > 2^(k-1) + 2^(k-2) + ...），1.5 倍不行。
reserve(n) 直接把这 1.31n 次搬移变成 0，代价是最后可能多占 31% 容量（100000 → 131072 那种余量不会出现在 reserve 后）。
clear() 不缩容：capacity 保持 131072，内存不还。要还只能 shrink_to_fit（非约束请求）或 swap 一个空容器。

四、同样 O(n²)，实测差 13 倍

900 万次加法，遍历一个 3000×3000 的矩阵，唯一区别是循环嵌套顺序：

for (i) for (j) s += mat[i * M + j];   // 行优先
for (j) for (i) s += mat[i * M + j];   // 列优先

行优先 6.56 ms | 列优先 85.11 ms | 差 13.0 倍（同样的 O(n²)，同样的指令数）

复杂度完全相同、指令数完全相同，只差内存访问顺序。 列优先时每走一步跳 12000 字节，几乎每次都把整条缓存行丢掉，还打满 TLB。

这是”大 O 会骗人”最典型的例子：它假设所有内存访问等价，而真实机器上缓存层次决定了几十倍差距。写数值/图像/矩阵代码时，遍历顺序是第一位的性能决策。

五、空间复杂度：递归的隐藏账单

long long sum_v1(const int *a, int n) { return n == 0 ? 0 : a[0] + sum_v1(a + 1, n - 1); }
long long sum_v2(const int *a, int n) { long long s = 0; for (int i = 0; i < n; i++) s += a[i]; return s; }

两者都是 O(n) 时间，但空间是 O(n) vs O(1)。C 专栏第八节量过：一个只带 int 参数的递归函数每层约 64 字节，本机栈预留 2 MB ⇒ 约 3 万层见顶。递归写法在 n 很大时不是”慢一点”，而是直接崩。

判断标准：递归深度有没有上界、上界是多少。没有明确答案就改迭代。

六、把”小 n 用线性扫描”这条经验拿掉

网上流传”数组很小时线性扫描比二分快”（源自 Epic 的那篇著名测试）。我在本机按未命中查询实测三种实现：

n	带分支线性扫描	无分支计数扫描	`lower_bound`
8	9 ms	18 ms	9 ms
16	26 ms	35 ms	9 ms
32	57 ms	76 ms	10 ms
64	95 ms	131 ms	11 ms

（各 300 万次查询，未命中，所以线性必须扫完）

结论：在这台机器和 -O2 下，线性扫描一次都没赢，n=8 时二分就已经持平。 原因是小数组全在 L1 里，二分”缓存不友好”的代价根本不存在，而它的比较次数优势立刻兑现；同时线性扫描那个 if (v[i]==key) break 是数据依赖分支，n 越大预测失败越多。

那条经验成立的前提是：数据大到装不进缓存 + 未命中查询 + 扫描被向量化（无 SIMD 障碍）。条件不满足就照搬，等于用一个不存在的收益换一次真实的风险。

教训通用：任何”X 比 Y 快”的经验，都要问清它的前提条件，并在自己的机器上重测。 我在这一节里同时推翻了自己准备写的两个说法。

七、怎么正确地测复杂度

测操作数，别只测时间：比较次数、赋值次数、内存分配次数是确定性的，不受负载影响。第二、三节就是这么测的。
n 至少取 3 个点，看比值是否稳定（2 倍/4 倍），才能区分 O(n)、O(n log n)、O(n²)。
隔离被测代码：把填数据、分配内存从计时里剔除，或者单独测一次作为基线扣除（第一节的排序就犯了这个错）。
防止编译器把活干完：结果必须被使用（写进 volatile 变量或参与输出），否则整个循环会被删——我在 C++ 专栏里就遇到过”30 万次 map 查找耗时 0µs”，因为那段的返回值没被用。
多跑取中位数，别信第一次（缓存冷、频率调节未稳）。
换编译器/换机器要重测：倍增因子、SSO 阈值、RAND_MAX 都是实现相关的。

八、常见复杂度陷阱清单

写法	你以为	实际
`std::string s; for(...) s += c;`	O(n)	摊还 O(n)，但没 `reserve` 时有多次搬移
`for (i=0;i<s.length();i++)`（`length()` 每轮调用）	O(n)	仍是 O(n)（`std::string::length()` 是 O(1)），但 `strlen()` 就是 O(n²)
`s.insert(s.begin(), c)` 循环	O(n)	O(n²)（每次搬全部）
`std::list` 随机访问 `++it` n 次	O(n) 但”常数小”	O(n) 且常数极大（缓存 miss）
`map[key]` 在只读循环里	O(log n)	O(log n) 且会插入，容器无限增长
递归斐波那契	O(n)	O(2ⁿ)，n=45 就要十亿次调用
双重循环里 `i <= n`	O(n²)	边界多一轮，仍是 O(n²)，但 off-by-one 是 bug
在无序数组上 `binary_search`	O(log n)	结果无意义，且仍 O(log n) 时间

九、这一节的自查清单

先估数量级：n 最大是多少？O(n²) 在 10 万级就已经不可接受（实测 80000 就 520ms）
递归必须有深度上界，且算过栈用量
大量小对象操作先看摊还成本（push_back、substr、insert(begin)）
二维数据按行遍历，别按列
别用”小 n 线性更快”这类经验替代测量
基准测试要防死代码消除、要隔离无关成本、要取中位数
复杂度结论后面标注实现与环境，换平台重测
用比较次数/分配次数这类确定性指标交叉验证时间测量

下一节讲线性表：数组与链表的真实取舍、单/双/循环链表的 C++ 实现、std::forward_list 与 std::list 的差别，以及为什么”链表插入 O(1)“这句话在真实机器上常常是错的。