上篇聊了时间复杂度那些基础概念——大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)。这个例子真正值钱的地方在于它让“指数级”三个字变得具体。你尝试跑n30可能还行到n45就要等十几秒到n50已经是肉眼可见的卡顿了。计算的增长速度就是这么恐怖。而改成迭代或者加一个缓存数组瞬间变成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)情况1f(n) O(n^{c - ε})其中ε 0。说明合并开销比递归分裂慢总时间由递归树的最底层叶子节点数决定结果Θ(n^c)。情况2f(n) Θ(n^c)。两者同阶总时间就是每层都付出差不多同样代价结果Θ(n^c log n)。情况3f(n) Ω(n^{c ε})且满足正则条件af(n/b) ≤ kf(n)说明额外消耗主导结果Θ(f(n))。举两个最常见的例子。二分查找T(n) T(n/2) O(1)。这里a1, b2所以c log₂1 0f(n) 1刚好等于n^0是情况2结果是O(log n)。归并排序T(n) 2T(n/2) O(n)。a2, b2c log₂2 1f(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 ≤ 20O(2^n)或O(n!)可能都能过n ≤ 1000O(n²)很稳n ≤ 10^5O(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)还能稳住这就是分析复杂度不可替代的价值所在。