上篇聊了时间复杂度那些基础概念——大O表示法、常数阶线性阶平方阶、普通循环里的复杂计算。这篇继续把硬骨头啃完，重点讲三个东西：递归怎么算、均摊分析到底在分析什么，以及复杂度分析在真实工程和面试里怎么用。这几块内容彼此独立，但合在一起，才算把“分析复杂度”这个技能真正打通。
很多人在递归这一步卡住，根本原因是遇到T(n) = T(n-1) + T(n-2)这种写法就开始懵。其实复杂度分析没有多神秘，它无非是回答一个问题：输入规模变大，运行时间会变成原来的几倍。上篇解决的是“循环层数”这种直观情况，这篇解决的是“函数自己调用自己”这种不那么直观的情况。
1. 递归：程序自己调自己，复杂度怎么算
1.1 写递归先想清楚“递推关系”
递归函数的时间复杂度，本质上是一个递推方程。你别管代码长啥样，先抽象出这样一行式子：
T(n) = a * T(n / b) + f(n)这个式子的意思是：一个规模为n的问题，被拆成了a个规模为n/b的子问题，每个子问题都要继续递归求解；f(n)是合并子问题结果所花的时间。
拿归并排序举例子。归并排序把数组从中间切开，左右各排一遍，最后合并，所以递推式是：
T(n) = 2 * T(n/2) + O(n)这个式子里的O(n)就是合并两个有序数组的线性扫描。只要你把这个递推关系写对了，后续分析目标就非常明确——把这个T(n)展开成一个不含T(.)的直接表达式。
很多初学者看到递归函数第一反应是“函数里有个for循环，所以是O(n)”，这就错了。递归的复杂度不是看函数体内循环层数，而是看“递归的深度×每层的时间”，更严谨地说是要看整棵递归树一共有多少个节点、每个节点花多少时间。这个区分是理解递归复杂度的起点。
1.2 递归树：可视化递归次数
递归树是我个人最推荐的分析工具。它的思想很简单：把每一次函数调用画成一个节点，节点下面的分支就是递归产生的子调用。
画归并排序的递归树，第一层是T(n)，第二层是两个T(n/2)，第三层是四个T(n/4)。到第k层，有2^k个节点，每个节点的问题规模是n/2^k。每层合并的总时间都是O(n)——因为每个节点做合并，把所有节点合起来恰好扫一遍整个数组。树的高度是log₂n（因为每次规模减半，一直减到1）。所以总时间就是：
每层O(n) × 层数log₂n = O(n log n)这个画树的过程换成更通用的表达就是“主定理”的直观来源。但递归树比主定理更不容易记错，因为它逼你把每一层的代价加一遍。一个很实用的习惯是：遇到任何递归复杂度问题，先画三层树找规律，再回答说“第k层有xxx个节点、每层总代价是xxx”。
1.3 斐波那契：一个经典的指数级陷阱
用递归树分析斐波那契，很多人才真正意识到教科书式递归的问题。代码长这样：
def fib(n): if n <= 1: return n return fib(n - 1) + fib(n - 2)它的递推式是T(n) = T(n-1) + T(n-2) + O(1)。画递归树，第一层1个节点，第二层2个，第三层4个……一直分裂到规模为1或0的叶节点，树的高度是n，总节点数大约是2^n量级。所以复杂度是指数级O(2^n)。
这个例子真正值钱的地方在于：它让“指数级”三个字变得具体。你尝试跑n=30可能还行，到n=45就要等十几秒，到n=50已经是肉眼可见的卡顿了。计算的增长速度就是这么恐怖。而改成迭代或者加一个缓存数组，瞬间变成O(n)线性时间。
我见过太多人背“递归是2^n”，却不懂为什么。本质原因在于fib(n)会反复计算同一个子问题。fib(5)要算fib(4)和fib(3)，而这两个又都会去算fib(2)，整个调用树里重复出现过无数个fib(2)。复杂度爆掉的根源是“重复计算”而不是“递归”本身。
2. 主定理：递归复杂度的“速算公式”
2.1 主定理的适用条件
递归树画起来慢，所以有了主定理（Master Theorem）直接帮你算形如T(n) = aT(n/b) + f(n)的复杂度。它的适用条件是：a ≥ 1、b > 1，且子问题规模都相同。很多教科书递推式是满足这个条件的，但实际工作中碰到的递归未必都规整——有些递归会把问题拆成大小不同的子问题，这时候主定理并不适用，必须回退到递归树或者代入法。
主定理的思路核心是拿两个东西比较：子问题的“分裂消耗”和合并的“额外消耗”。定义了临界指数c = log_b(a)，它表示“纯递归分裂产生的总节点代价的指数级”。然后用f(n)和n^c比大小——谁大听谁的。
2.2 三种情况怎么选，怎么套
直接列结果。给定T(n) = aT(n/b) + f(n)，设c = log_b(a)：
- 情况1：
f(n) = O(n^{c - ε})，其中ε > 0。说明合并开销比递归分裂慢，总时间由递归树的最底层叶子节点数决定，结果Θ(n^c)。 - 情况2：
f(n) = Θ(n^c)。两者同阶，总时间就是每层都付出差不多同样代价，结果Θ(n^c log n)。 - 情况3：
f(n) = Ω(n^{c + ε})，且满足正则条件af(n/b) ≤ kf(n)，说明额外消耗主导，结果Θ(f(n))。
举两个最常见的例子。
二分查找：T(n) = T(n/2) + O(1)。这里a=1, b=2，所以c = log₂1 = 0，f(n) = 1刚好等于n^0，是情况2，结果是O(log n)。
归并排序：T(n) = 2T(n/2) + O(n)。a=2, b=2，c = log₂2 = 1，f(n) = n等于n^1，情况2，结果是O(n log n)。
2.3 说实话，工程里我很少硬背主定理
主定理在面试里的价值大于工作里的价值，这话我说得比较直。实际写代码时，遇到递归你先画递归树，假如每层代价清晰可算，就用手工展开；假如发现每层代价变化不规律，再用主定理的结论去验算，两条路可以互相印证。
我自己记忆主定理的方式是把它理解成“两种力量的PK”：递归把问题切成小块，对面是每层合并工件所付出的代价。递归树每层的总代价如果逐层递增，就看最底层；如果逐层递减，就看最顶层；如果每层都差不多，就是层数×单层代价。这个直觉比背公式可靠得多。很多时间里你以为要用情况3，一画递归树发现每层都是线性的，其实就是情况2，输出n log n。
3. 均摊分析：为什么有些算法不按常理出牌
3.1 均摊不等于平均
均摊分析（Amortized Analysis）是网上讨论最少、但实际工程里最常用的复杂度分析。它的目标不是算某一次操作的最坏情况，而是算“连续执行n次操作后，总时间除以n”的平均值。但它又区别于简单的概率平均——这里没有概率，是确定性的最坏情况平均。
最典型的例子是动态数组扩容。假设一个数组初始容量为1，每次装满就扩容到原来的2倍。单次“push”操作最坏情况是O(n)级别的——因为要申请新内存、把旧元素逐个拷过去。如果只这么看，你会觉得动态数组的插入是O(n)，但真实世界里没人说动态数组插入慢。为什么？因为扩容次数很少：扩容到2、4、8、16，总共也就拷贝了2 + 4 + 8 + ... + n次，加起来不到2n。把总代价O(n)分摊到n次插入，平均每次还是O(1)。这就是均摊。
3.2 动态数组扩容的经典案例
我帮你把账算清楚。假设容量从1开始翻倍，到第n次插入之前，最后一次扩容发生在容量刚超过n/2的时候，拷贝的元素数量是n/2。之前每一次扩容拷贝数量分别是1、2、4……加起来是n/2 + n/4 + ... + 1，这个等比数列的和趋近于n。也就是说，n次push操作的总代价大概是n次普通插入（O(1)）再加上n次拷贝的代价，合计O(n)。均摊到每次就是O(1)。
“均摊O(1)”和“每次都是O(1)”不是一回事，这一点必须分清楚。单次扩容操作确实很慢，但它发生的频率反比于它的代价——越贵的操作出现得越少，所以整体下来代价被摊平了。这个思想在Hash表的rehash、并查集的路径压缩里都用得上。
3.3 课堂上的“账本法”
很多人觉得均摊分析抽象，我提供一个直观的“账本法”视角。想象每次普通push操作除了自己的运行成本外，还额外“存”一点时间币，用来支付未来可能发生的扩容拷贝。每次插入存一个固定数额，扩容时一次把所有积蓄拿出来用。只要存款总量能够覆盖未来的开销，均摊就是O(1)。
我第一次看动态数组均摊分析的时候，总觉得这有点“作弊”，后来才明白这就是工程本身——很多数据结构的单次操作都有抖动，但整体吞吐非常稳定，尤其像Java的ArrayList和Go的slice，靠的就是这套均摊机制。分析复杂度如果只看最坏单次，会得出非常偏颇的结论。
4. 排排序，看看复杂度在真实世界的样子
4.1 常见排序复杂度速查
排序是复杂度分析最密集的素材库。我把最常见的几个排序算法的复杂度整理成一张表，方便你随时对照：
| 排序算法 | 最好情况 | 平均情况 | 最坏情况 | 额外空间 | 稳定性 |
|---|---|---|---|---|---|
| 冒泡排序 | O(n) | O(n²) | O(n²) | O(1) | 稳定 |
| 插入排序 | O(n) | O(n²) | O(n²) | O(1) | 稳定 |
| 选择排序 | O(n²) | O(n²) | O(n²) | O(1) | 不稳定 |
| 快速排序 | O(n log n) | O(n log n) | O(n²) | O(log n) | 不稳定 |
| 归并排序 | O(n log n) | O(n log n) | O(n log n) | O(n) | 稳定 |
| 堆排序 | O(n log n) | O(n log n) | O(n log n) | O(1) | 不稳定 |
| 计数排序 | O(n + k) | O(n + k) | O(n + k) | O(k) | 稳定 |
这张表最值得品的地方在快排。快排的平均情况和最好情况都是O(n log n)，但最坏是O(n²)。加上随机化后，最坏情况出现的概率低到可以忽略。为什么大家普遍用快排而不是堆排序？因为快排的常数因子小——访问顺序是连续的，能很好地命中CPU缓存，而堆排序的访问是跳跃的，局部性差。复杂度相同的两个算法，真实性能可能差好几倍，这就引出后面“常数因子”的话题。
4.2 比较排序的“天花板”：nlogn从哪来
一个很深的问题：为什么比较排序最快只能到O(n log n)？答案不是“人猜的”，而是数学上锁死的。考虑一个有n个元素的数组，所有排列有n!种可能。任何基于比较的排序算法每次比较最多产生两种结果，相当于一个二叉树的节点。这棵决策树要能区分出所有n!种排列，树的高度至少是log₂(n!)。根据斯特林公式，log₂(n!) ≈ n log₂ n。所以比较排序的下界就是Ω(n log n)。
这个结论在面试中经常被问“为什么快排是最优的？”的时候用上。它给出的是整个算法类别（基于比较）的极限，不是某个具体算法的极限。因此想要突破n log n，唯一的出路是脱离“比较”这种信息获取方式——桶排序、计数排序、基数排序都是利用数据本身的特性，绕过比较，才能做到线性时间。所以实战中“我的数据能不能不比较就排序？”是一句非常有价值的灵魂拷问。
5. 复杂度分析里的坑
5.1 表面循环和真实代价的错位
拿到一个函数就数循环层数是很多人的条件反射，但越到复杂情况越容易错。核心原因在于：循环层数不等于执行次数。经典错题是那种“内外层都跟n有关，但内层提前break”的写法。
def find_dup(nums): for i in range(n): for j in range(i + 1, n): if nums[i] == nums[j]: return True return False这个二重循环看起来是O(n²)，但最坏情况下，假如数组中不存在重复元素，两层都会跑满，确实是n(n-1)/2次比较，O(n²)。假如前提改成“保证存在重复且数据随机”，平均情况下很快就能找到，但复杂度分析通常讨论最坏，所以面试时你最好答“最坏O(n²)，平均看数据分布”。这样既严谨又体现思考深度。
另一种更隐蔽的坑是“对数阶什么时候出现”。典型例子是二分查找：
while low <= high: mid = (low + high) // 2 ...循环变量不是线性推进，而是每次减半。每执行一次循环，搜索范围除以2，所以执行次数是log₂n。很多人算不对，是因为习惯性地“循环几次就是n的几次方”，而没有意识到循环变量变化的规律才是决定复杂度的根本。
5.2 空间复杂度的“墙面夹角”
时间复杂度和空间复杂度很像一间屋子的两面墙，很多人只盯着时间墙，忽略空间墙。而空间复杂度的计算要求你清楚区分“调用栈占用的空间”和“数据占用的空间”。
递归的空间复杂度特别容易判断错。一个递归深度为d的算法，空间复杂度是O(d)。即使递归函数里没有任何数组，每次递归调用也会在系统栈上压入一层上下文，深度到哪，栈就到哪。比如二分查找如果用递归实现，空间是O(log n)；如果用迭代实现，空间是O(1)。同样的算法逻辑，只是写法不同，空间表现完全不同。
更常见的空间翻车来自“复制数组”。很多人写快排的partition时，直接开两个临时数组来装小于和大于pivot的元素，逻辑很清晰，但空间复杂度直接从理想的O(log n)变成O(n)。数据规模一大，内存占用率就会警告。算法题的判题系统通常会专门卡这种空间浪费——时间超时是红色，内存超限同样爆红。
5.3 常数因子：复杂度相同，性能天差地别
我曾经遇到一个真实案例：同一个功能，两个同事写的代码都是O(n)，一个跑1.2秒，一个跑4.8秒。差异来源就是常数因子。大O忽略了乘的常数和低阶项，但工程里这些恰恰是决定用户体验的因素。
比如一个程序需要频繁执行“判断一个字符串是否在集合里”。用HashMap查，每次是O(1)，但如果有更好的hash函数或采用内存连续的数组存储，可能比用ArrayList线性扫描快几十倍——两者复杂度完全不同，也就不用比了。但即使同为O(1)的HashMap，初始化容量设置不当会导致多次rehash，常数因子可能从1变成3。这些都是分析完大O之后，工程上必须补的第二层功课。
不要机械地认为“O(n)一定比O(n²)快”。一个操作非常少的O(n²)算法处理小数据，可能比一个操作复杂且带大量额外开销的O(n)算法更快。复杂度描述的是“增长趋势”，不是“具体运行时间”，组合起来才是完整的性能画像。
6. 面试和笔试里，复杂度分析到底怎么用
6.1 看到题目第一眼应该想什么
算法题的解题顺序在我这里是固定的：先根据数据范围反推目标复杂度，再设计算法，最后动手写。
n ≤ 20，O(2^n)或O(n!)可能都能过；n ≤ 1000，O(n²)很稳；n ≤ 10^5，O(n log n)是安全线，O(n²)大概率超时；n ≤ 10^7以上，基本要求O(n)甚至O(log n)。
用这个表去卡题目，很多面试题还没动笔就知道自己该往哪个方向走。比如看到“数组里找两个数之和等于目标值”，数据规模是10^5，立刻意识到暴力双循环O(n²)会超时，要往O(n)或O(n log n)想。这个“先估复杂度再写代码”的习惯，也是面试官判断候选人工程素养的一个重要标尺。
6.2 一个具体的优化案例：两数之和
用“两数之和”这道题走一遍全流程。
暴力解法是两个循环嵌套，检查所有组合，复杂度O(n²)。在数据量大时显然不行。
思路一：先排序，再用双指针从两端往中间扫。排序是O(n log n)，双指针是O(n)，总复杂度O(n log n)。这个方案的扩展性很强，尤其当题目变成“找三个数之和”的时候，排序+双指针依然能打。
思路二：用哈希表，一边遍历一边把已经见过的数存进去。每个元素查表一次、插入一次，都是O(1)，整体O(n)。这是时间最优的方案，但代价是额外空间O(n)。
seen = {} for i, num in enumerate(nums): target = total - num if target in seen: return [seen[target], i] seen[num] = i这道题的价值在于：它展示了一条从O(n²)到O(n log n)再到O(n)的优化节奏。每次优化的背后，都是用另一维复杂度去换时间。面试官最爱追问的“还能更快吗”，本质上就是在考察你有没有这个复杂度权衡的全局观。
6.3 结合递归的题目怎么快速定复杂度
遇到树的题目，很多人上来就写递归，写到一半被问复杂度才卡住。这里有一个简单好上手的分析套路：看每个节点被访问几次，每次访问做什么。
二叉树遍历类题目的复杂度几乎可以机械化计算。每个节点最多被访问常数次，每次访问内部的操作如果是O(1)，总复杂度就是O(n)，n是节点数。如果访问内部有一个类似“查找子树最大值”的操作，那就要看这个操作本身的开销，可能变成O(n²)。递归树分析和这里是一脉相承的——每个节点上的额外操作才是决定总复杂度的变量。
7. 几个我越用越顺手的分析技巧
7.1 先猜后证，比硬推快十倍
复杂度分析允许你先猜答案，再证明。比如看到T(n) = 3T(n/2) + n，先猜可能是O(n^{log₂3})，也就是O(n^1.585)。验证方法就是用归纳假设代入递推式：假设T(n/2) ≤ c * (n/2)^{log₂3}，代入右边，如果计算出来的结果能小于等于c * n^{log₂3}，猜对了。硬推主定理当然也行，但“先猜后证”在面试中体现出来的速度感和对递归结构的理解力，往往更让面试官满意。
我自己的习惯是：先在草稿纸上画递归树，从树的形状猜出答案，再用主定理或者代入法验证。两条路径交叉验证，基本不会出大错。
7.2 极限直觉：谁的增长率更快
很多复杂度比较不需要精算，靠直觉就能判断。把常见函数按增长率从低到高排：常数 < log n < √n < n < n log n < n² < n³ < 2^n < n!。这个序列建议记牢，考试和面试时有超过一半的比较题能在几秒内解决。
log n和√n之间很多人容易搞混。一个判断方法是：令n = 2^k，那么log n = k，而√n = 2^{k/2}。这里k是多项式级，2^{k/2}是指数级。在n足够大的时候，指数级会把多项式级甩到看不见。所以√n远大于log n，所有涉及log的算法都值得暗自庆幸。
7.3 大O不是唯一标准，但它是第一标准
写了十几年代码，我对复杂度的态度是这样的：大O分析永远先把危险的算法拦在门外，但它拦不住性能问题的全部。两个不同复杂度的算法，选复杂度低的通常没错；两个复杂度相同的算法，真正决定胜负的是常数因子、缓存友好度、代码维护性。
有一次我把一段O(n²)的代码优化到O(n log n)，以为立竿见影，结果数据量小的时候反而变慢了。原因是我用了复杂的索引结构，每次操作的开销远大于原来的简单双循环。做工程不是纯拼复杂度，而是要在理解复杂度的前提下，结合实际数据规模做出权衡。但话说回来，数据规模从1万涨到1000万时，O(n²)会被吊打，O(n log n)还能稳住，这就是分析复杂度不可替代的价值所在。
