S03-X12 · 复杂度分析的常见误判

复杂度是模型，不是测量结果。它假设每一步代价相同、只数增长阶、忽略常数与内存层级——这些假设在课堂里成立，在真实代码里经常不成立。于是同一段代码，纸面上 O(n²)，实测却比"O(n log n)"的那段更快；反过来，纸面上 O(n)，实测却慢十倍，因为每一"步"都是一次隐藏的内置循环。

这篇不讲公式推导，只讲误判发生在哪、怎么在代码里把它抓出来。

1. 为什么"看起来 O(n²)"的代码可能更快

两层循环不等于 n²，除非内层真的跑 n 次。真正的判据是各层实际迭代次数的乘积。

def dedup_pairs(items):
    total = 0
    for i in range(len(items)):
        for j in range(i + 1, len(items)):     # 内层次数随 i 递减
            if items[i] == items[j]:
                total += 1
    return total

内层次数是 n-1, n-2, …, 1，总和 n(n-1)/2——确实是 O(n²)，但常数是 1/2。而一个"O(n)"的实现如果每轮做一次字符串拼接，量级上完全可能反超。三个来源：常数因子（n(n-1)/2 对比 3n，n 小的时候小常数的高阶项更便宜）、缓存局部性（顺序访问对比随机跳指针，步数少但每步都缓存未命中的更慢）、输入分布（内层提前 break，纸面最坏阶数不等于典型耗时）。

判据只有一条：估出各层实际迭代次数再相乘，不能数嵌套层数。

2. 均摊分析：均摊便宜不等于每次都便宜

动态数组扩容是最标准的例子。容量满时申请两倍空间、搬移全部元素，单次代价 O(n)；但只在 2, 4, 8, … 这些容量点触发，摊到每次插入是 O(1)。

class DynArray:
    def __init__(self):
        self._buf = [None] * 4
        self._size = 0

    def append(self, x):
        if self._size == len(self._buf):          # 只在满时扩容
            new = [None] * (len(self._buf) * 2)
            for i in range(self._size):           # 搬移 O(n)，但摊还后是 O(1)
                new[i] = self._buf[i]
            self._buf = new
        self._buf[self._size] = x
        self._size += 1

操作	单次最坏	摊还	关键前提
动态数组 `append`	O(n)	O(1)	每次倍增，不是每次 `+1`
哈希表插入	O(n)（全表再散列）	O(1)（期望）	负载因子有上限
并查集、单调栈	单次可能很深	近 O(1)	按秩合并 / 路径压缩

"摊还"这个词最容易被误用成"不慢"。准确说法是：m 次操作的总代价不超过 m·c，但其中某一次可以慢到 O(n)。对延迟敏感的系统（单次请求有 P99 上限），摊还不等于可接受——扩容那一次就是真的卡了。工程上的对策是把扩容点挪到低峰，或者预先 ensureCapacity。

推导摊还代价有三种方法，结论一致：聚合法（总代价除以次数）、记账法（便宜操作存"信用"供昂贵操作花）、势能法（摊还代价 = 实际代价 + ΔΦ）。

3. 最坏、平均、期望

这三个词经常被当成同义词，其实定义完全不同：

记号	针对什么求平均	快排的例子	哈希表的例子
最坏	所有输入	O(n²)	O(n)
平均	输入的概率分布	依赖分布假设，通常取 O(n log n)	依赖分布假设
期望	算法自身的随机性	随机枢轴下 O(n log n)	随机哈希下 O(1)

差别在最后一行：期望是对算法内部的随机选择求平均，与输入分布无关。快排加随机枢轴后，即使输入是被精心构造的逆序数组，期望仍是 O(n log n)——构造者不知道你抽了哪个枢轴。而"平均 O(n log n)"依赖"输入随机"这个假设，输入一旦来自攻击者就不成立。

哈希表同理：期望 O(1) 建立在"hashCode 均匀"之上；键若可被构造（用户 ID、URL），大量键会落到同一个桶，退化成链表、单次 O(n)。这也是有些实现对超长链表做树化的原因——把最坏情况压到 O(log n)，代价是比较器与树节点的开销。

import random

def quickselect(a, k):
    lo, hi = 0, len(a) - 1
    while lo < hi:
        p = a[random.randint(lo, hi)]          # 随机枢轴：把最坏情况推给概率
        i, j = lo, hi
        while i <= j:
            while a[i] < p: i += 1
            while a[j] > p: j -= 1
            if i <= j:
                a[i], a[j] = a[j], a[i]
                i += 1; j -= 1
        if k <= j: hi = j
        elif k >= i: lo = i
        else: return a[k]
    return a[lo]

把"期望"写成"平均"，等于把抗构造的保证降级成假设。

4. 空间复杂度里容易漏掉的部分

空间复杂度不是"申请了几个大数组"，而是峰值存活量。四类常被漏掉：

漏项	例子	量级
递归栈	递归深度 d，每帧常数空间	O(d)，d 可能是 n
临时对象	循环里 `s += x`、装箱、切片	每轮 O(len)，可能累积到 O(n²) 次的分配
字符串视图	有的语言 `substring` 共享底层数组	O(n) 被"看不见地"留住
闭包与捕获	lambda 捕获大对象，延长生命周期	O(捕获对象大小)

Java 的 String.substring 在 JDK 7u6 之后复制新数组，不再有"子串拖住整个大串"的问题，但每次 substring 都是 O(len) 复制，循环里反复切会把时间也变成 O(n²)。Python 切片同理（复制，不是视图）；Go 的切片共享底层数组，于是反过来——内存被小切片拖住不放。

// 反面例子：每次 substring 都复制，总时间 O(n²)、总分配 O(n²)
String[] parts = new String[n];
for (int i = 0; i < n; i++) {
    parts[i] = text.substring(i, i + 10);      // 每轮一次 O(10) 复制，n 次
}

实用的估法是看峰值：递归深度 + 结构本身 + 最坏一次的临时分配，三者相加。

5. 隐藏的循环：内置方法不是免费的

复杂度误判的头号来源，是把库调用当成 O(1)。

# 看起来 O(n)，实际 O(n²)
def has_dup(items):
    seen = []
    for x in items:
        if x in seen:                     # list.__contains__ 是线性扫描
            return True
        seen.append(x)                    # append 摊还 O(1)
    return False

x in seen 对 list 是 O(len)，所以整段 O(n²)；换成 set 才是 O(n)。

写法	表面	实际	修法
`list.contains(x)` / `x in list`	O(1)	O(n)	换 `HashSet`
`s += "a"` 在循环里	O(1)	Java 每次新建，O(n²)	`StringBuilder`
`ArrayList.remove(0)`	O(1)	O(n)（要搬移）	`ArrayDeque` / 反向删除
`String.format` 在热点循环	O(1)	解析格式串 + 多次分配	拼 `StringBuilder` 或延迟格式化
`list.sort()` 每轮调用	O(1)	O(n log n)	移到循环外
`map.get` 在 `HashMap`	O(1)	期望 O(1)，冲突时 O(n)	换好键或用树化实现

Python 里更隐蔽的一条：str.join 是 O(总长)，而 + 在 CPython 里有就地优化的实现细节，不保证。」

6. 对数因子来自哪里

对数只有四个来源，认出来就不容易漏：二分（有序查找、答案二分）、分治（归并排序、FFT，因子是递归树层数）、平衡结构高度（平衡树、堆、跳表）、按位拆分（快速幂，见第 8 节）。

分治的 log 来自树的层数，而不是每个节点做多少次。归并排序每层总代价 O(n)、层数 log n，乘起来 O(n log n)；如果每次只处理一侧（快排的平均情况），树并不平衡，但期望深度仍是 O(log n)。

def power(base, exp, mod):
    result = 1
    while exp:                             # 迭代次数 = exp 的二进制位数
        if exp & 1:
            result = result * base % mod
        base = base * base % mod
        exp >>= 1
    return result

这里的 log 不是"元素个数的 log"，而是"指数本身的位数"。两种 log 混用是最常见的表述错误。

7. 渐进记号忽略的常数

O(n log n) 对 O(n²) 的优势要到某个 n 才出现。以比较排序为例：归并排序的移动次数约为 n·log₂n，插入排序最坏约为 n²/4。令两者相等：n log₂n = n²/4，解得 n ≈ 16·log₂n，n 在数十这个量级附近。也就是说几百个元素以内，插入排序完全可能更快——它的内层循环是紧的顺序访问，缓存友好，没有递归开销。

标准库正是这么做的：小数组走插入排序，超过阈值才切分治（Arrays.sort 对基本类型用双轴快排 + 小数组插入排序，TimSort 对近乎有序的输入接近 O(n)）。

顺带记住一条常被忘的：O(n log n) 的界只对基于比较的排序成立。计数排序、基数排序是 O(n + k)，代价是要额外的键空间。

8. 输入规模的真实含义

n 到底是什么，直接决定阶数：

问题	n 的含义	常见误判
数组排序	元素个数	把比较次数当"操作数"漏掉常数
判断素数	数值本身	试除到 √n 说成 O(√n) 却忘了 n 是数值
快速幂	指数的数值	O(log n) 里的 n 是指数，不是位数
大整数乘法	位数	把位数当数值，阶数全错
图的算法	点数 V 与边数 E	只写一个 n，稠密/稀疏全糊在一起
字符串匹配	文本长 n、模式长 m	写成 O(n) 漏掉 m

"n 是元素数还是位数"这条决定了整个估算是差一个数量级还是差一个指数。判断素数的试除法是 O(√n)（n 是数值），换成位数就是 O(2^(b/2))——指数级。同一段代码，两种 n，天壤之别。

9. 排错：六种"分析对了但结论错了"

现象	原因	处理
代码 O(n log n) 却比 O(n²) 慢	常数与缓存局部性没算进去	小 n 段用实测或插入排序兜底
单次请求偶发超时	把摊还当成了每次都便宜	找到扩容点，预热或分批
宣称 O(1) 却在大键集上退化	期望 O(1) 依赖哈希均匀	换键设计、树化或加盐
内存 O(1) 但 OOM	漏了递归栈、临时对象、切片共享	看峰值而不是看大数组
循环内耗时与 n 不成比例	内置方法里藏着线性扫描	`contains` / `+` / `remove(0)` 逐个换成对的结构
只算时间不看 I/O 与网络	每个"步"其实是毫秒级的往返	把 I/O 次数单独算一维（见边界表）

最后一条杀伤力最大：一次数据库往返按毫秒计，一次内存访问按纳秒计，差六个数量级。"N+1 查询"正是复杂度分析里漏掉的整维成本——循环里每步访问数据库，代码看着 O(n)，但每步的成本系数比内存操作大六个数量级。

10. 边界：复杂度之外还有什么

维度	什么时候比阶数更重要	怎么估
I/O 与网络	任何跨进程调用	按往返次数 × 单次延迟，单独一维
内存	大数据集、容器限额	峰值 × 常数，考虑对象头与装箱
缓存局部性	顺序对比随机访问	按"缓存行数"而不是"元素数"
并行度	多核可拆分的任务	阶数不变，常数除以核数，但有同步开销
GC 压力	高频临时对象	分配速率 × 对象大小，比渐近阶更致命
常数可预测性	延迟敏感服务	看 P99 而不是平均值

一句话收束：复杂度回答"规模翻倍会怎样"，不回答"这一秒要多久"。两件事都要，但别用前者的答案去回答后者。

11. 自测

两层嵌套循环什么情况下不是 O(n²)？判断依据是哪两个量？
动态数组 append 的摊还 O(1) 依赖什么前提？改成每次 +1 扩容会怎样？
"平均 O(n log n)"与"期望 O(n log n)"差在哪一类随机性上？
递归算法的空间复杂度里，最容易被漏掉的一项是什么？它和什么成正比？
为什么几百个元素以内插入排序可能比归并排序快？用哪两个式子能估出交叉点？
快速幂的 O(log n) 里，n 指的是什么？把它当成"元素个数"会错到什么程度？