1. 双重循环复杂度分析先弄清出题人到底在考什么每年到考研冲刺阶段都有学弟学妹拿着数据结构习题来问我时间复杂度题开场白几乎都是同一句双层for循环外层n次、内层n次答案不就是O(n²)吗可一旦题目里出现外层变量参与了内层循环的范围、内层步长会变化、循环体中间夹着break之类的情况立刻卡壳四个选项看着哪个都像最后只能蒙。其实考研里关于双重循环复杂度的题目核心考察能力只有一条你能不能把一个嵌套循环的总执行次数准确数出来。注意我说的是数次数不是猜量级。很多人翻车不是因为不懂大O记号而是因为压根不知道从哪开始数、数的时候该保留什么、数完又怎么化简成最终答案。我当年复习备考到后来给学弟学妹讲题类似的双重循环题粗算下来分析了不下两三百道最后沉淀出一套固定的分析套路就是这篇文章标题里说的四行表格法。它的核心思路极其朴素不要凭感觉看循环结构而是把每一次分析强制拆成四行固定内容逐行填写、逐行检查。这样一来双重循环复杂度分析就从玄学变成了填空每道题都能按同一个流程走完。下面把方法讲透再拿四道非常典型的考研真题把拆解过程完整过一遍看完你再去刷题正确率会有肉眼可见的提升。2. 四行表格法到底怎么用2.1 四行分别填什么先上表格模板这是整个方法的核心。行号要填的内容一句话说明第1行外层循环变量区间从几开始、到几结束、每次怎么变由此得出外层总迭代次数第2行内层循环次数公式内层的初值、条件、步长里有没有外层变量写出内层次数 f(i)第3行总执行次数求和式把 f(i) 对外层所有取值求和得到 T(n)第4行化简结论保留最高阶项、去掉系数和低阶项写成 O(?)以最经典的题目为例先感受一下填完之后的效果int cnt 0; for (int i 1; i n; i) { for (int j 1; j i; j) { cnt; } }行号填写内容结果第1行外层 i: 1→n步长1外层迭代 n 次第2行内层 j: 1→i步长1上限含外层变量 if(i) i第3行T(n) 1 2 ... n等差数列第4行T(n) n(n1)/2最高阶 n²/2O(n²)这套流程的关键在于第2行。内层循环的次数公式里有没有外层变量 i决定了这道题是直接相乘还是必须求和。如果内层次数完全不含 i比如内层固定是j n那么 T(n) 外层次数 × 内层次数一步乘法就结束了。一旦含 i就必须老老实实走完第3行的求和过程。四行表的存在就是强迫你在第2行把依赖关系看清楚而不是跳过去直接写答案。2.2 为什么这个套路能稳定秒杀可能有人觉得四行表不过就是先写外层再写内层再求和嘛这有什么稀奇的。确实任何一本算法书都会告诉你循环复杂度等于求和但实际做题时大家的操作往往非常随意有人直接盯着循环体数几个例子有人凭经验猜有人算到一半忘了外层变量的取值范围。四行表的优势在于每一步都有明确产物而且可以逐格核验。我自己的体会是四行表真正解决的是卡住了不知道卡在哪的问题。学生拿着题来问我说老师我觉得这题不是O(n²)但不知道是哪我让他把四行表填出来十有八九是第2行写错了——内层次数公式没写对后面自然全错。只要能正确填出第2行第3行不过是套求和公式第4行是机械化简几乎不存在失分的可能。还有一个容易被忽略的好处四行表产出的第3行精确表达式正好对应考研选择题里那种该算法执行次数与以下哪个表达式最接近的考法。只写个O(n²)在这种题面前是不够的你要能写出 n(n1)/2 或者 n²/4 这种带系数的形式。四行表把精确次数写在了明面上这类题顺手就解决了。2.3 填表时必须遵守的三个底层原则第一数的是循环体执行次数不是代码行数更不是循环变量的取值个数。循环变量的每次赋值、条件判断、步长更新这些在复杂度分析里都是 O(1)不参与累加。真正要数的是最内层那条语句到底被执行了多少次。第二循环变量的变化方式决定内层公式长什么样。步长是常数 1内层次数就是简单的区间长度步长是翻倍内层次数会变成等比数列的项步长是外层变量 i 本身内层次数就和 i 成反比。做题时盯着步长看基本能预判该往哪类求和公式上靠。第三前面三步要求精确只有最后一步才允许粗糙。第3行必须写出严格的和式比如 Σ⌈i/2⌉、Σ2^m不能上来就写约等于n²/4。化简放在最后统一做顺序反了容易把求和结构搞错算出一个对不上的答案。3. 四道考研真题完整拆解3.1 真题一最基础的三角循环题目求下列代码中 cnt 语句执行次数的数量级。int cnt 0; for (int i 1; i n; i) { for (int j 1; j i; j) { cnt; } }填表过程行号填写内容结果第1行i 从1到n步长1外层共 n 次第2行j 从1到i步长1上限是外层变量f(i) i第3行Σ(i) 从 i1 到 nT(n) n(n1)/2第4行最高阶是 n²/2去掉系数O(n²)计算细节T(n) 1 2 3 ... n n(n1)/2。这里用的是等差数列求和公式首项1、末项n、项数n直接套公式就行。这道题最值得注意的地方是有人图快直接写外层n次 × 内层n次 n²写完发现答案碰巧也是O(n²)于是觉得自己会了。可一旦选择题问的是执行次数最接近下面哪个表达式选项里同时出现 n²/2 和 n² 时这种偷懒的理解就会翻车。内层次数从1递增到n平均是 (n1)/2外层n轮精确总数是 n(n1)/2这些细节必须能算出来。顺带说一个常见变体把内层改成for (int j i; j n; j)此时 f(i) n-i1求和得到 n (n-1) ... 1 n(n1)/2和本题一模一样。原因很简单内层从1到i与从i到n在数量上是镜像对称的复杂度自然相同。考场上见到这种变体不用慌四行表填一遍就清楚了。3.2 真题二外层倍增的经典陷阱题题目求下列代码的时间复杂度。int cnt 0; for (int i 1; i n; i * 2) { for (int j 1; j i; j) { cnt; } }填表过程行号填写内容结果第1行i 取值 1, 2, 4, ...直到不超过 n共 ⌊log₂n⌋ 1 次第2行j 从1到i步长1上限是外层变量f(i) i第3行Σ(i) 对 i 2^0, 2^1, ..., 2^kT(n) 2^(k1) - 1第4行2^(k1) ≤ 2n去系数O(n)这是四道题里最容易做错的一道典型错误答案是 O(n log n)我见过至少一半的学生第一次做都会掉进这个坑。他们的思路是外层跑 log₂n 轮内层每轮最多 n 次所以 n log n。问题出在哪内层每轮不是 n 次而是 i 次i 从1开始倍增真正执行次数是 1 2 4 ... 2^k 这样一个等比数列而不是每轮都是 n。设 2^k ≤ n 2^(k1)即 k ⌊log₂n⌋。外层依次取 1, 2, 4, ..., 2^k对应内层执行 1, 2, 4, ..., 2^k 次。等比数列求和T(n) 1 2 4 ... 2^k 2^(k1) - 1因为 2^k ≤ n所以 2^(k1) ≤ 2n于是 T(n) ≤ 2n - 1去掉系数就是 O(n)。这道题我建议你把外层倍增 内层上限等于外层变量和外层倍增 内层上限恒为n放在一起对比记忆。后者才是真正的 O(n log n)因为内层每轮都完整跑 n 次。区分点就一个内层上限里有没有外层变量。有这个变量内层次数随外层变化必须求和没有这个变量直接相乘。考研出题人特别喜欢把这两个结构放在同一套卷子的不同题里考的就是你能不能看出这个区别。3.3 真题三内层步长为2考察精确计数能力题目求下列代码 cnt 执行次数的数量级并写出精确次数表达式。int cnt 0; for (int i 1; i n; i) { for (int j 1; j i; j 2) { cnt; } }填表过程行号填写内容结果第1行i 从1到n步长1外层共 n 次第2行j 从1到i步长2上限是外层变量f(i) ⌈i/2⌉第3行Σ⌈i/2⌉ 从 i1 到 n分奇偶讨论第4行T(n) ≈ n²/4最高阶去系数O(n²)难点在第2行的取整符号。内层 j 取 1, 3, 5, ...当 i5 时执行 3 次i6 时也执行 3 次i7 时执行 4 次。次数不是恰好 i/2而是向上取整 ⌈i/2⌉。很多人一看到取整就不知道怎么求和了这里教大家一个通用办法按外层变量 i 的奇偶分类。当 i 为偶数 2m 时j 取 1,3,...,2m-1共 m 次 当 i 为奇数 2m-1 时j 取 1,3,...,2m-1共 m 次。 所以 f(2m) f(2m-1) m也就是说每一对外层奇偶取值贡献是一样的成对出现。若 n 2k则 T(n) 2(1 2 ... k) k(k1) ≈ n²/4 若 n 2k1则 T(n) 2(1 2 ... k) (k1) (k1)² ≈ n²/4。两种情况下最高阶都是 n²/4去掉系数写成 O(n²)。但注意如果选择题问执行次数最接近下列哪个那就要能区分 n²/4 和 n² 这两个表达式这时候第3行的精确结果就是得分关键。这道题还带出一个判断规则内层步长只要是正的常数比如2、3、100都不会改变复杂度的量级只是改变系数。所以下次遇到步长是常数的内层循环第一反应应该是整体量级不变系数可能差个常数倍而不是重新怀疑要变成 O(n log n)。3.4 真题四内层步长等于外层变量引出调和级数题目求下列代码的时间复杂度。int cnt 0; for (int i 1; i n; i) { for (int j 1; j n; j i) { cnt; } }填表过程行号填写内容结果第1行i 从1到n步长1外层共 n 次第2行j 从1到n步长 i步长含外层变量f(i) ≈ n/i第3行Σ(n/i) 从 i1 到 nn·H_n第4行H_n ≈ ln n γO(n log n)这道题是四道题里最难的也是不少自命题学校的保留题型。内层循环 j 的步长是外层变量 i意味着当 i 越大内层跳得越远执行次数越少。当 i1 时j 走遍 1 到 n执行 n 次当 i2 时j 只取 1, 3, 5, ...约 n/2 次当 in 时j 取 1 和 1n 两个值约 n/n 1 次。所以第2行写 f(i) ≈ n/i。精确一点内层次数是 ⌊(n-1)/i⌋ 1当 n 比较大时约等于 n/i。于是T(n) ≈ Σ(n/i) 从 i1 到 n n · (1 1/2 1/3 ... 1/n) n · H_n这里的 H_n 是第 n 个调和数它有一个重要的渐近公式H_n ≈ ln n γ其中 γ 是欧拉常数约为 0.577。把系数 n 乘进来T(n) ≈ n ln n量级就是 O(n log n)。做错这道题的人通常有两种。第一种是把内层步长为 i误读成内层从1到i然后套用第一题的做法算出 O(n²)这是读代码时把步长和条件搞混了内层条件是 j n不是 j i必须把初值、条件、步长三个要素分开确认。第二种是算出了和式 Σ(n/i)但不知道 H_n 的渐近公式卡在最后一步写不出答案。H_n ≈ ln n 这个结论建议直接记住考研里凡是出现分母是外层变量的求和基本都是这个套路。延伸一个常见变式如果题目改成统计1到n中能被每个 i 整除的数的个数本质就是 Σ⌊n/i⌋计算过程完全一样结论也是 O(n log n)。看到内层步长等于外层变量这类结构直接往调和级数上靠能省不少时间。4. 双重循环分析的高频失分点4.1 最危险的习惯看到双循环就写 O(n²)这不是夸张是我在批改习题时见过最多的问题。三重循环也未必是 O(n³)双重循环更不一定是 O(n²)一切取决于内层次数是否依赖外层变量。依赖关系存在时复杂度可能是线性、对数线性或者 n²依赖关系不存在时直接乘法。写答案之前用两秒钟扫一眼内层循环的边界和步长确认有没有外层变量出现这一个小动作能避免绝大多数误判。4.2 求和公式用错四行表第3行的计算依赖三类公式等差、等比、调和。考前值得专门默写一遍等差Σ_{i1}^{n} i n(n1)/2平方和Σ_{i1}^{n} i² n(n1)(2n1)/6三重循环里可能用到等比Σ_{i0}^{k} 2^i 2^(k1) - 1注意首项是1还是2公比是2还是1/2调和H_n 1 1/2 ... 1/n ≈ ln n γ容易翻车的细节是等比数列项数。比如外层 i 从1倍增到不超过 n实际项数是 ⌊log₂n⌋1不是 ⌊log₂n⌋。这个 1 错误会让求和结果差出一个数量级必须小心。另外log 的底数在大O记号里是可以忽略的换底公式保证任何底数的对数只差一个常数倍。写 O(n log n) 时不用纠结底数是2还是e但如果在选择题里要比较哪个表达式更接近真实次数那还是要回到精确和式看不能只看大O。4.3 break 和 continue 的影响要分情况见到 break 先别慌我是这样处理的先按完整循环写出内层次数公式再看 break 条件会把 f(i) 截断成多少。比如内层写成for (j 1; j n; j) { if (j i) break; cnt; }理论上内层要跑 n 次但 j 一旦超过 i 就退出实际次数是 min(n, i)。因为 i 不超过 n所以就是 i 次等价于第一题复杂度 O(n²)。关键在于break 让实际执行的前缀变短了你要找到这个前缀的长度。continue 的情况稍微绕一点。如果 continue 出现在计数语句之前它会让计数语句的执行次数减少但循环本身的迭代次数不变。考试时先看清楚统计对象是循环迭代次数还是某条语句执行次数这两者的答案可能不同。统计语句就按语句实际执行的路径数统计循环迭代就把整轮判断条件都算上。4.4 最坏情况和平均情况别混为一谈考研复杂度题默认讨论最坏情况除非题目里明确出现平均。最坏情况分析的思路是构造一个让循环执行次数最大的输入然后对那个输入数次数。典型场景是内层有个if判断数据是否满足条件满足就 break。最坏情况下条件始终不满足内层完整跑完这时候的循环次数才是复杂度分析的对象。我见过有同学看见 break 就直接写 O(n)忽略了 break 可能根本不会触发这是把最好情况当成了答案。5. 考场上的快速判断法与自查习惯5.1 十秒钟判断该直接乘还是该求和拿到双重循环先做三个顺序判断内层循环的边界或步长里有没有外层变量如果没有直接相乘外层次数 × 内层次数。如果有看依赖的形式内层边界是外层变量比如 j i往等差求和上想内层步长是外层变量比如 j i往调和级数上想外层步长倍增且内层边界是外层变量往等比求和上想。对应套公式填四行表。这三个判断我实际用下来能覆盖考研题里九成以上的双重循环结构。剩下的变体比如循环里套条件语句、带 break、甚至三重循环只要老老实实回到四行表逐行过思路不会乱。5.2 第4行化简的固定顺序化简时我永远按照同样的顺序操作先写精确和式再找最高阶项再去掉常数系数最后写 O(...)。这里有一个容易忽略的点最高阶项是关于 n 的增长最快的项。n(n1)/2 的最高阶是 n²/2不是 n/2n·H_n 的增长项是 n ln n不是 n。千万别写成 O(2n) 或者 O(n(n1)/2) 这种带系数还带括号的形式那不是大O记号的最终表达。5.3 一个能救分的验算小技巧最后分享一个我用了很多年的检查习惯代入一个具体的小 n 手工数次数。比如做完一道题取 n8在草稿纸上把双重循环的实际执行次数逐个数出来和四行表第3行的表达式对比。对上了基本稳了对不上说明第2行或第3行有问题马上回头检查。这个方法在考场上的性价比很高。取一个具体的 n 数循环次数熟练的话三十秒内能完成但能确认整个分析过程没有低级错误。到了冲刺阶段我要求学生在训练时每道复杂度题都做一次这个验证形成肌肉记忆考场上才能不慌。毕竟四行表再熟练最终目的是稳定拿分而稳定拿分的底气来自于每一道题都经得起这种最朴素方法的检验。