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，上限含外层变量 i | f(i) = i |
| 第3行 | T(n) = 1 + 2 + ... + n | 等差数列 |
| 第4行 | T(n) = n(n+1)/2，最高阶 n²/2 | O(n²) |
这套流程的关键在于第2行。内层循环的次数公式里有没有外层变量 i，决定了这道题是"直接相乘"还是"必须求和"。如果内层次数完全不含 i，比如内层固定是j < n，那么 T(n) = 外层次数 × 内层次数，一步乘法就结束了。一旦含 i，就必须老老实实走完第3行的求和过程。四行表的存在，就是强迫你在第2行把依赖关系看清楚，而不是跳过去直接写答案。
2.2 为什么这个套路能稳定"秒杀"
可能有人觉得，四行表不过就是"先写外层再写内层再求和"嘛，这有什么稀奇的。确实，任何一本算法书都会告诉你循环复杂度等于求和，但实际做题时大家的操作往往非常随意：有人直接盯着循环体数几个例子，有人凭经验猜，有人算到一半忘了外层变量的取值范围。四行表的优势在于每一步都有明确产物，而且可以逐格核验。
我自己的体会是，四行表真正解决的是"卡住了不知道卡在哪"的问题。学生拿着题来问我，说"老师我觉得这题不是O(n²)但不知道是哪"，我让他把四行表填出来，十有八九是第2行写错了——内层次数公式没写对，后面自然全错。只要能正确填出第2行，第3行不过是套求和公式，第4行是机械化简，几乎不存在失分的可能。
还有一个容易被忽略的好处：四行表产出的第3行精确表达式，正好对应考研选择题里那种"该算法执行次数与以下哪个表达式最接近"的考法。只写个O(n²)在这种题面前是不够的，你要能写出 n(n+1)/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) 从 i=1 到 n | T(n)= n(n+1)/2 |
| 第4行 | 最高阶是 n²/2，去掉系数 | O(n²) |
计算细节：T(n) = 1 + 2 + 3 + ... + n = n(n+1)/2。这里用的是等差数列求和公式，首项1、末项n、项数n，直接套公式就行。
这道题最值得注意的地方是：有人图快直接写"外层n次 × 内层n次 = n²"，写完发现答案碰巧也是O(n²)，于是觉得自己会了。可一旦选择题问的是"执行次数最接近下面哪个表达式"，选项里同时出现 n²/2 和 n² 时，这种偷懒的理解就会翻车。内层次数从1递增到n，平均是 (n+1)/2，外层n轮，精确总数是 n(n+1)/2，这些细节必须能算出来。
顺带说一个常见变体：把内层改成for (int j = i; j <= n; j++)，此时 f(i) = n-i+1，求和得到 n + (n-1) + ... + 1 = n(n+1)/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^k | T(n) = 2^(k+1) - 1 |
| 第4行 | 2^(k+1) ≤ 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^(k+1)，即 k = ⌊log₂n⌋。外层依次取 1, 2, 4, ..., 2^k，对应内层执行 1, 2, 4, ..., 2^k 次。等比数列求和：
T(n) = 1 + 2 + 4 + ... + 2^k = 2^(k+1) - 1
因为 2^k ≤ n，所以 2^(k+1) ≤ 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⌉ 从 i=1 到 n | 分奇偶讨论 |
| 第4行 | T(n) ≈ n²/4，最高阶去系数 | O(n²) |
难点在第2行的取整符号。内层 j 取 1, 3, 5, ...，当 i=5 时执行 3 次，i=6 时也执行 3 次，i=7 时执行 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(k+1) ≈ n²/4； 若 n = 2k+1，则 T(n) = 2(1 + 2 + ... + k) + (k+1) = (k+1)² ≈ 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) 从 i=1 到 n | n·H_n |
| 第4行 | H_n ≈ ln n + γ | O(n log n) |
这道题是四道题里最难的，也是不少自命题学校的保留题型。内层循环 j 的步长是外层变量 i，意味着当 i 越大，内层跳得越远，执行次数越少。当 i=1 时，j 走遍 1 到 n，执行 n 次；当 i=2 时，j 只取 1, 3, 5, ...，约 n/2 次；当 i=n 时，j 取 1 和 1+n 两个值，约 n/n = 1 次。所以第2行写 f(i) ≈ n/i。
精确一点，内层次数是 ⌊(n-1)/i⌋ + 1，当 n 比较大时约等于 n/i。于是：
T(n) ≈ Σ(n/i) 从 i=1 到 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行的计算依赖三类公式：等差、等比、调和。考前值得专门默写一遍：
- 等差：Σ_{i=1}^{n} i = n(n+1)/2
- 平方和：Σ_{i=1}^{n} i² = n(n+1)(2n+1)/6，三重循环里可能用到
- 等比：Σ_{i=0}^{k} 2^i = 2^(k+1) - 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(n+1)/2 的最高阶是 n²/2，不是 n/2；n·H_n 的增长项是 n ln n，不是 n。千万别写成 O(2n) 或者 O(n(n+1)/2) 这种带系数还带括号的形式，那不是大O记号的最终表达。
5.3 一个能救分的验算小技巧
最后分享一个我用了很多年的检查习惯：代入一个具体的小 n 手工数次数。比如做完一道题，取 n=8，在草稿纸上把双重循环的实际执行次数逐个数出来，和四行表第3行的表达式对比。对上了，基本稳了；对不上，说明第2行或第3行有问题，马上回头检查。
这个方法在考场上的性价比很高。取一个具体的 n 数循环次数，熟练的话三十秒内能完成，但能确认整个分析过程没有低级错误。到了冲刺阶段，我要求学生在训练时每道复杂度题都做一次这个验证，形成肌肉记忆，考场上才能不慌。毕竟，四行表再熟练，最终目的是稳定拿分，而稳定拿分的底气，来自于每一道题都经得起这种最朴素方法的检验。
