1.7 算法复杂度与大 O 记号：看懂 O(n²) 到底在说什么

1.为什么数学基础也要管"复杂度"

前六篇我们把线性代数、概率论、微积分、优化都过了一遍，这些都是"连续"的数学。可这一篇要补的工具——算法复杂度——更像计算机科学的味道，它关心的是"步骤的多少""操作次数怎么随规模涨"。你可能要问，学深度学习为什么要管这个？

因为后面到处都在用它。3.11 节讲 Mamba 会说它把注意力从 $O(n^2)$ 降到 $O(n)$ ；7.2 节讲线性注意力、7.3 节讲稀疏注意力、9.1 节讲 KV cache，三句话离不开 $O(n^2)$ 、 $O(n)$ 、 $O(1)$ 这些记号。更早在第二卷，2.12 节会说 SVM 的训练开销随样本数平方、立方增长。这些记号到底是什么意思、为什么能拿来比较"哪个算法更划算"，如果没在本篇讲清楚，后面你会一直半懂不懂。所以这篇就当一块地基，把它讲透，后面凡是见到 $O(\cdot)$ 都心里有数。

2.复杂度到底在量什么

先说直白点。一个算法跑起来，要花时间（CPU 算了多少步），也要占空间（内存里存了多少东西）。我们想知道：当输入的规模变大时，这个花销是怎么跟着涨的。规模用一个正整数 $n$ 表示，它代表"问题有多大"——比如要排序的元素个数、序列的长度、样本数。

时间复杂度，就是刻画"操作次数随 $n$ 增长"的函数。空间复杂度同理，刻画"占用内存随 $n$ 增长"。两者用同一套记号，下面我们主要拿时间来举例，空间是一个道理。

这里有个关键态度：我们不在乎常数，只在乎增长趋势。 为什么？因为常数和具体硬件、实现、编程语言绑死了，而增长趋势是算法本身的性质。同样是"扫一遍数组"，在快机器上花 1 毫秒、慢机器上花 10 毫秒，但它在两台机器上都是"扫一遍"，增长的快慢是一样的——这就是我们要抓的、不随机器变的那个东西。

3.大 O 记号：只看上界，忽略常数

正式的记号叫大 O 记号（Big-O notation）。说一个算法的时间复杂度是 $O(f(n))$ ，意思是：当 $n$ 足够大时，操作次数 $T(n)$ 的增长不会超过 $f(n)$ 的常数倍。写成数学就是存在常数 $C$ 和一个起点 $n_0$ ，对所有 $n>n_0$ 有 $T(n)\le C\cdot f(n)$ 。

注意三件事：

第一，大 O 是"上界"。 它说的是"最多涨成这样"，可能涨得比这慢，但不会更快。所以我们用大 O 来表达最坏情况的保障——"不管怎样，开销不会超过这个量级"。日常说" $O(n^2)$ 的算法"，就是在说它的操作次数被 $n^2$ 的常数倍封顶。

第二，常数被忽略。 一个要 $3n^2$ 步的算法和一个要 $50n^2$ 步的算法，都写成 $O(n^2)$ 。因为 $n$ 一大，3 倍还是 50 倍这个常数，比起 $n^2$ 本身的增长根本不算什么——把 $n$ 翻一倍，两个算法的开销都变成原来的四倍，这才是它们共同的、本质的增长行为。所以大 O 故意把常数抹掉，只留增长趋势。

第三，只看 $n$ 足够大时的行为。 小规模时谁快谁慢可能被常数主导（一个 $O(n^2)$ 但常数极小的算法，在 $n$ 很小时可能跑赢一个 $O(n\log n)$ 但常数很大的算法）。但算法分析关心的是"规模大了以后会不会撑不住"，所以默认看 $n\to\infty$ 的渐进行为。

举个例子把这三点串起来。两段代码：

# 算法A：把长度为n的数组每个元素看一遍
for x in array:        # n次操作
    do_something(x)

# 算法B：双重循环，每对元素都比较一次
for i in range(n):     # 外层n次
    for j in range(n): # 内层n次
        compare(i, j)

算法 A 操作次数正比于 $n$ ，是 $O(n)$ ；算法 B 操作次数正比于 $n\times n=n^2$ ，是 $O(n^2)$ 。它们的差别用一句话说清：规模翻倍，A 的开销翻倍，B 的开销变成四倍。 当 $n$ 从 1000 涨到 100 万（涨一千倍），A 的开销涨一千倍，B 的开销涨一百万倍——这就是 $O(n^2)$ 真正可怕的地方。

4.常见的阶，从快到慢

把后面要反复见到的几个阶排成一列，从增长最慢（最便宜）到最快（最贵）。这一列你要记熟，因为整个深度学习架构的讨论，本质上就是在"把贵的阶换成便宜的阶"。

O(1)\ <\ O(\log n)\ <\ O(n)\ <\ O(n\log n)\ <\ O(n^2)\ <\ O(2^n)\ <\ O(n!)

逐个说直觉：

$O(1)$ — 常数时间。 开销和规模无关，是个固定值。比如数组里按下标取第 $i$ 个元素，不管数组多大，一步到位。哈希表的平均查找也是这个档。
$O(\log n)$ — 对数时间。 每走一步能把问题规模砍一半，所以 $n$ 翻倍只多走一步。二分查找、平衡二叉搜索树（A.2 节）的查找都在这档。这是极快的增长—— $n$ 是一百万时 $\log n$ 也才二十左右。
$O(n)$ — 线性时间。 扫一遍所有元素，开销和规模成正比。线性注意力（7.2）、状态空间模型（3.11）追求的就是把注意力降到这一档。
$O(n\log n)$ — 线性对数时间。 比线性稍贵，但比平方便宜得多。最快的通用排序算法（归并、快排平均）就在这档。
$O(n^2)$ — 平方时间。 每个元素都要和所有其他元素配对一遍。标准自注意力就在这档——序列里 $n$ 个位置两两算相似度。这是后面要重点攻克的瓶颈。
$O(2^n)$ / $O(n!)$ — 指数 / 阶乘时间。 爆炸式增长，规模稍微大一点就彻底算不动。组合爆炸（枚举所有子集、所有排列）落在这档，工程上基本不可行，得靠启发式绕开。

把这张表和深度学习对上号：3.11 的 Mamba、7.2 的线性注意力，本质就是把注意力从 $O(n^2)$ 拉到 $O(n)$ ；7.3 的稀疏注意力，是把它降到介于 $O(n)$ 和 $O(n^2)$ 之间的某个位置。学会用复杂度的语言去衡量架构，你就能一眼看出一个新设计"省在哪里"。

5.最好、最坏、平均

到这儿还有一层细节。同一个算法在不同输入上，开销可能差很多。比如在一个无序数组里找一个数，运气好第一个就是（一步找到），运气不好在最后才找到（扫到底）。于是复杂度分三种：

最好情况（best case）：最顺的输入下的开销。乐观估计，一般不单独拿来当保障。
最坏情况（worst case）：最坑的输入下的开销。大 O 常用来表达这个，因为它给出"再多也不会超过"的封顶保障。
平均情况（average case）：所有输入上的期望开销，最贴近实际体感。

工程上通常最关心最坏情况和平均情况。比如哈希表查找，平均是 $O(1)$ ，但要是哈希函数设计得很糟、冲突扎堆（A.2 节提过这个坑），最坏能退化到 $O(n)$ 。我们说哈希表查找"是 $O(1)$ "，指的就是平均情况，背后得靠一个分布均匀的哈希函数撑着。

6.空间复杂度：同样一套记号

时间说完了，空间是一个道理，只是把"操作次数"换成"占用内存"。 $O(1)$ 空间意味着不管 $n$ 多大，只用固定几块内存； $O(n)$ 空间意味着内存随规模线性增长。

深度学习里空间复杂度往往比时间更扎手，因为显存是硬约束。9.1 节要讲的 KV cache，随序列长度 $O(n)$ 增长，层数多头数多时总量惊人——100 万 token 的上下文光 KV cache 就能吃掉几百 GB 显存，这才是长上下文落地的真正拦路虎。所以你会看到量化（9.2）、PagedAttention（8.1）这些技术，本质上都是在压空间复杂度的常数、减少浪费。

一句话记住：时间复杂度管"算不算得动"，空间复杂度管"装不装得下"。 长上下文（7.3）是这两者叠加的硬仗，得同时攻。

7.把它用到后面的内容上

光记定义不够，拿两个后面要遇到的实例练练手，你就能上手了。

例一：自注意力为什么是 $O(n^2)$ 。 注意力对序列里 $n$ 个位置，每个位置都要和其他 $n$ 个位置各算一次相似度（点积），一共 $n\times n=n^2$ 次。所以是 $O(n^2)$ 。它的含义：序列长度翻十倍，计算量涨一百倍；涨一千倍，计算量涨一百万倍。这就是为什么 Transformer 一上长文本就吃不消，也就解释了为什么后面要花那么大力气去攻它。

例二：矩阵乘法，谁是 $n$ 。 两个 $n\times n$ 的方阵相乘，按定义每个元素是两行（列）的点积， $O(n)$ 次，一共 $n^2$ 个元素，所以总共 $O(n^3)$ 。注意这里"规模"指的是矩阵的边长 $n$ ，不是元素总数——同一件事换个"规模"的定义，复杂度的式子就不同。所以读复杂度时先问一句" $n$ 代表什么"，是序列长度、样本数、还是矩阵边长，别混了。

8.练习

Q1. 为什么大 O 记号要忽略常数？一个"3n 步"和"50n 步"的算法都是 $O(n)$ ，这合理吗？

合理。大 O 关心的是增长趋势而不是绝对快慢。把规模 $n$ 翻倍，3n 和 50n 都翻倍，增长行为完全一样——常数 3 或 50 是实现细节、随机器和语言变，不是算法的本质属性。大 O 故意抹掉常数，留下"随规模怎么涨"这个不变的趋势。当然常数在工程里很重要（同是 $O(n)$ ，常数小十倍就是十倍快），但那是工程优化的事，不是复杂度分析的事。

Q2.（大厂面试题） 自注意力是 $O(n^2)$ ，请用复杂度的语言解释：为什么序列从 4k 撑到 32k 是件大事？线性注意力（ $O(n)$ ）缓解了什么、又牺牲了什么？

$O(n^2)$ 意味着序列长度翻 8 倍（4k→32k），计算量涨 $8^2=64$ 倍，所以平方复杂度下扩长上下文极其昂贵。线性注意力把它降到 $O(n)$ ，同样的 8 倍只涨 8 倍开销，扩起来便宜得多。代价是线性注意力去掉了 softmax 这种精确的、内容相关的打分，用近似替代，换取了效率但牺牲了一点精确检索能力（7.2 节细讲）。这就是"效率 vs 能力"的权衡，用复杂度的语言能说得一清二楚。

9.小结

复杂度是一把尺子。学会用 $O(\cdot)$ 去度量算法，你就能一眼看穿"这个设计贵在哪里、那个改进省在哪里"。记住那张从 $O(1)$ 到 $O(n!)$ 的阶梯，记住"忽略常数、只看趋势、看渐进行为"这三条，后面凡是见到 $O(n^2)$ 、 $O(n)$ 你就心里有底了。第一卷的数学地基到此打完，下一卷我们就正式进入机器学习，从最朴素的线性模型开始。