考研408里，数据结构这一科的复杂度分析是个特别有意思的存在——它不像图算法那样有一堆步骤要背，也不像排序那样需要记住每个过程的中间状态，但几乎每一套真题都躲不开它。时间复杂度与空间复杂度的判断，散落在选择题、综合应用题甚至算法设计题的评分点里。我当年备考时最大的困惑不是"不会算"，而是"算出来不知道对不对"，因为教材给的答案往往只写一个 O(nlogn)，中间推导全跳过。这篇内容就是把我自己踩过的坑、总结出的判定套路、以及考场上真正管用的速算方法整理出来，适合刚接触408的零基础同学，也适合二刷三刷还在复杂度上反复丢分的老选手。

1. 复杂度分析在408里到底值多少分

1.1 它不是一道题，而是一种贯穿全卷的语言

很多人备考初期会把复杂度当成一个独立知识点去背，比如"快排平均 O(nlogn)、最坏 O(n²)"，背完就以为掌握了。真正做题才发现问题：算法设计题最后两行要求"说明算法的时间复杂度"，你写了 O(n²)，但如果实际是 O(nlogn) 却写了 O(n²)，直接扣分；更麻烦的是，有些题目的算法写对了，复杂度分析错了，阅卷老师会认为你对自己写的代码没有真正理解，整题的印象分都会受影响。

复杂度分析在408里的分布大致是这样的：单项选择题中通常有2到3道直接考复杂度判断，包括循环次数、递归式求解、某算法的最好/最坏情况对比；综合应用题里，如果考到树、图、排序的某个操作，经常会附带一句"分析该操作的时间复杂度"；算法设计题（通常是最后一道大题）几乎必然要求给出时间复杂度和空间复杂度，而且这句话本身就是分值的一部分。粗略估算，一整张卷子里跟复杂度直接相关的分数在15到20分之间，间接相关（需要靠复杂度判断来选择算法）的就更多了。

这就是为什么我说它是一种"语言"——你得能用它准确描述自己写的每一段代码，否则就像写作文不会断句一样，内容再好也读不通。

1.2 408对复杂度的要求边界在哪

这里必须说清楚一件事：408不考严格的数学证明。你不需要用 ε-δ 那一套去证明某个函数属于某个渐进类，也不需要背主定理的完整条件。它考的是三件事：能不能正确数出基本语句的执行次数、能不能从递推关系里解出量级、能不能区分最好情况和最坏情况。

举个具体的例子，真题里出现过这样的循环：

int i = 1; while (i <= n) { i = i * 2; }

这个循环体执行了多少次？从 i=1 开始，每次翻倍，直到超过 n，所以执行次数是 ⌊log₂n⌋+1，复杂度 O(log₂n)。408的答案通常写成 O(log₂n) 或 O(logn)，两种都算对，但有些年份的标准答案会特意标注底数，这时候写清楚更稳妥。这类题不会要你证明"存在常数c"，它就是考你有没有真正理解循环变量是怎么变化的。

再比如递归：

int f(int n) { if (n <= 1) return 1; return f(n - 1) + f(n - 2); }

这是斐波那契的朴素递归，复杂度是多少？很多人第一反应是 O(2ⁿ)，因为看起来每层分两支。严格来说调用次数是 O(1.618ⁿ)，但408的标准答案接受 O(2ⁿ)，因为大O只要求上界，2ⁿ 确实是上界。这里就能看出408的宽容度——它要的是量级判断，不是紧确界。

1.3 备考时最容易走偏的三个方向

第一个坑是死记结论不看推导。比如"堆排序时间复杂度 O(nlogn)"，背下来很容易，但题目稍微变一下——"建堆过程的时间复杂度是多少"——很多人就答不上来了。建堆是 O(n)，不是 O(nlogn)，这个结论必须靠推导才能记住：从最后一个非叶结点往前调整，每层结点数乘以调整高度求和，最终收敛到 O(n)。光背结论的人在这一步必挂。

第二个坑是忽略空间复杂度的计算口径。空间复杂度算的是"辅助空间"，不含输入数据本身占用的空间。这个定义很多人知道，但一做题就忘。比如问"归并排序的空间复杂度"，答案是 O(n)，因为需要一个和原数组等长的辅助数组；但如果问"快速排序的空间复杂度"，答案是 O(logn)，因为快排是原地排序，额外空间只来自递归调用栈的深度。这两个答案的差别不在"用了多少内存"，而在"额外"这两个字。

第三个坑是把平均情况和最坏情况混着用。题目问"快速排序的时间复杂度"，如果没特别说明，408默认回答平均情况 O(nlogn)，但只要题目里出现"最坏"两个字，就必须答 O(n²)，并且要能说清楚最坏发生在什么条件下——每次划分都选到当前区间的最大或最小元素作为枢轴，划分极度不平衡，递归深度退化为 n。

2. 时间复杂度判定的核心逻辑

2.1 大O记号到底在描述什么

用一句人话解释：大O描述的是"当输入规模越来越大时，执行时间的增长趋势像什么函数"。它故意丢掉了常数和低阶项，因为当 n 足够大时，这些都不重要。

比如 3n² + 5n + 100，当 n=1000 时是 3,005,100，其中 3n² 占了 3,000,000，5n 只占 5000，常数 100 可以忽略。所以这个式子的量级是 n²，记作 O(n²)。

这里有个细节值得说：408答题时，能写成 O(n²) 就不要写 O(3n²+5n+100)，因为后者虽然更精确，但不是标准的大O表达，有些阅卷老师会认为你没理解大O的含义。反过来说，如果你在推导过程里写"循环执行了 n(n+1)/2 次，所以复杂度是 O(n²)"，这个推导过程是加分的，因为阅卷老师能看到你的思路。

还有个常见误区：O(1) 不代表"执行一次"，而代表"执行次数是常数，与 n 无关"。一个循环跑一万次，只要这个一万是固定的、不随 n 变化，它就是 O(1)。408选择题特别喜欢在这里设陷阱，比如给出一个"循环上限是 1000 的固定常量"的代码，问你复杂度，答案是 O(1) 而不是 O(n)。

2.2 循环结构的频度计数法

这是408选择题里出现频率最高的题型。我总结了一个三步走的方法，比死算要快得多。

第一步，找循环变量的初值、终值和每次的变化量。第二步，算循环体执行的总次数。第三步，取最高阶项。

单层线性循环是最基础的：

for (int i = 0; i < n; i++) { ... }

执行 n 次，O(n)。这是送分题，但要注意边界，i < n和i <= n差一次，虽然不影响量级，但在某些"精确计算执行次数"的题目里会扣分。

单层非线性循环是选择题的重灾区，常见的有三种变形：

第三种和第四种是很多人第一次见会懵的。i = i * i这种，i 的取值序列是 2, 4, 16, 256...，每步是前一步的平方，走 k 步之后 i 约等于 2^(2^k)，要超过 n 需要 2^k > log₂n，即 k > log₂log₂n。这个结论在近十年真题里出现过两次，属于偏冷但确实考过的点。

双层嵌套循环的判定核心是看内外层是否独立。

独立的情况：

for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) ...;

外层 n 次，内层 m 次，总次数 n×m，O(nm)。如果 m 和 n 是两个独立变量，就不能合并成 O(n²)，这是常见的失分点。

相关的情况：

for (int i = 1; i <= n; i++) for (int j = 1; j <= i; j++) ...;

内层次数随外层变化，总数是 1+2+...+n = n(n+1)/2，O(n²)。这类题的关键是不能简单写成 n×n，必须做求和。

还有一种是内外层乘积关系：

for (int i = 1; i <= n; i *= 2) for (int j = 1; j <= n; j++) ...;

外层 logn 次，内层每次 n 次，总次数 nlogn，O(nlogn)。这个结构在分析某些分治算法（比如归并排序的合并阶段）时会出现。

2.3 三层以上嵌套的化简技巧

三层循环在408里出现的频率不高，但一旦出现就是拉开分差的地方。看这个：

for (int i = 1; i <= n; i++) for (int j = 1; j <= i; j++) for (int k = 1; k <= j; k++) ...;

硬算是 1 + (1+2) + (1+2+3) + ...，求和公式是三阶的，最终是 O(n³)。但更快的判断方法是：每一层都是线性递增，三层嵌套就对应三次求和，每次求和的阶提升一阶，所以是 O(n³)。

反过来，如果有一层是 log 级别的变化：

for (int i = 1; i <= n; i *= 2) for (int j = 1; j <= i; j++) ...;

外层 i 的取值是 1, 2, 4, ..., 2^m（2^m ≤ n），内层执行 i 次，总次数是 1+2+4+...+2^m ≈ 2^(m+1) ≈ 2n，所以复杂度是 O(n)，不是 O(nlogn)。这个结论反直觉，但用等比数列求和一算就清楚了。这种题在真题里出过一次，当年错误率很高。

提示：遇到嵌套循环不要急着相乘，先观察内层的循环上限是不是依赖外层变量。独立就相乘，依赖就求和，这是所有循环分析的总纲。

2.4 递归算法的递推式求解

递归的复杂度分析，本质是解一个递推方程。408考的递归类型不多，下面这几类涵盖了绝大多数情况。

第一类，线性递归，每次规模减一：

T(n) = T(n - 1) + O(1)

每层只做常数时间的工作，递归 n 层，答案是 O(n)。典型的例子是单链表逆序输出、求阶乘的递归版。

如果每层做的是 O(n) 的工作：

T(n) = T(n - 1) + O(n)

展开就是 n + (n-1) + ... + 1 = O(n²)，典型例子是递归版插入排序。

第二类，分治递归，每次规模减半：

T(n) = 2T(n/2) + O(n)

这是归并排序的递推式。展开的方式是画递归树：第 k 层有 2^k 个结点，每个结点的工作量是 n/2^k，该层总工作量恒为 n；树高是 logn，所以总工作量是 nlogn。

T(n) = T(n/2) + O(1)

这是二分查找的递推式，树高 logn，每层常数工作，答案 O(logn)。

T(n) = 2T(n/2) + O(1)

这是遍历二叉树的递推式，每个结点访问一次，答案 O(n)。

第三类，指数级递归，比如汉诺塔：

T(n) = 2T(n - 1) + O(1)

展开是 1+2+4+...+2^(n-1) = 2ⁿ - 1，答案 O(2ⁿ)。

这几类递推式建议直接背下来对应的结论，考场上临时推导浪费时间而且容易出错。但要记住一点：背结论的前提是你知道这个结论对应哪一类递推式，光背"归并排序 O(nlogn)"是不够的，得能写出来T(n)=2T(n/2)+O(n)这个式子，才能保证遇到变体时不慌。

2.5 均摊分析与最坏情况的取舍

408大纲里不明确考均摊分析，但相关的思想会以"连续操作的总代价"形式出现。最典型的是动态数组的扩容问题，也是顺序表插入的一个延伸。

考虑一个顺序表，初始容量为1，每次满了就扩容成原来的2倍。问连续插入 n 个元素的总时间复杂度是多少？

单次插入最坏是 O(n)（扩容时要把所有元素搬一遍），但算总代价：第1次插入后扩容0次，第2次扩容搬1个，第3次扩容搬2个，第5次搬4个，第9次搬8个……总的搬运次数是 1+2+4+...+2^k ≈ n，加上 n 次插入本身，总代价 O(n)，均摊到每次是 O(1)。

这个结论说明：不能拿单次最坏情况去回答"整体复杂度"。如果题目问"n次插入的总复杂度"，答 O(n²) 就错了；如果问"单次插入最坏复杂度"，答 O(n) 才对。看清题目问的是"总"还是"单次"，这是最容易丢分的地方。

注意：408的题干里经常出现"最坏情况下"和"平均情况下"两种表述。凡是没有特别限定的，默认回答平均情况；一旦题干明确写了"最坏"，必须切换到最坏情况的答案，两者不能混着写。

3. 空间复杂度的计算口径与实战

3.1 辅助空间才是唯一要算的东西

空间复杂度的定义是"算法在运行过程中临时占用的存储空间大小"，关键是"临时"和"占用"。输入数据本身不参与计算，程序代码本身也不参与计算（有些教材说代码空间是固定的，可以忽略）。

判断标准很简单：除了存放输入的数组、链表、树这些结构本身之外，算法额外开辟了多少空间。

举个例子对比：

// 版本一：原地交换 void reverse(int a[], int n) { for (int i = 0; i < n / 2; i++) { int t = a[i]; a[i] = a[n - 1 - i]; a[n - 1 - i] = t; } }

这个只需要一个临时变量 t，空间复杂度 O(1)。

// 版本二：借助辅助数组 void reverse(int a[], int n) { int b[n]; for (int i = 0; i < n; i++) b[i] = a[n - 1 - i]; for (int i = 0; i < n; i++) a[i] = b[i]; }

这个需要一个长度 n 的辅助数组，空间复杂度 O(n)。

两个版本功能完全一样，时间复杂度也都是 O(n)，但空间复杂度差一个量级。408算法设计题里，"要求空间复杂度为 O(1)"是一个明确的限制条件，如果你写了一个借助辅助数组的方案，即使功能正确也会被扣分。这个要求在链表题里尤其常见，因为链表题的出题人特别喜欢考"原地逆置"、"原地删除"这类操作。

3.2 递归栈空间到底算多少

递归算法的空间复杂度，等于递归调用栈的最大深度乘以每层占用的空间。大多数情况下每层只是保存几个局部变量和返回地址，可以看成常数，所以空间复杂度就是 O(递归深度)。

几种常见情形：

二分查找的递归版，递归深度是 logn，空间 O(logn)。注意同样功能的迭代版，只用几个变量循环，空间是 O(1)。这两个版本在408选择题里经常被拿来对比，问"哪种实现的空间复杂度更低"，答案永远是迭代版。

归并排序的空间复杂度，很多人的答案是 O(nlogn)，理由是递归深度 logn，每层要开辟长度 n 的辅助数组。这个答案是错的。归并排序的辅助数组可以在递归外层只开辟一次，所有层共用，所以空间是 O(n) + O(logn) = O(n)。这个结论很多教材写得含糊，408的标准答案是 O(n)，因为 n 的阶高于 logn，取最高阶。

快速排序的空间复杂度，递归深度是 logn（平均情况），每层常数空间，所以是 O(logn)。但如果是最坏情况，递归深度退化为 n，空间就变成 O(n)。这就是为什么快排要优化枢轴的选择——随机化或者三数取中，目的不只是提高平均性能，也是为了控制递归深度，避免栈溢出。

树的前序、中序、后序遍历的递归版，空间 O(h)，h 是树高。如果是平衡树，h=logn；如果退化成链，h=n。层序遍历用队列实现，空间 O(w)，w 是树的最大宽度。

提示：递归空间复杂度的判断口诀是"只看深度不看次数"。同一个函数递归调用十次但都是顺序调用（不是嵌套），栈的深度只有一层，空间是 O(1)；嵌套递归哪怕只嵌套两层，空间也是 O(2) 即 O(1)，但如果嵌套深度随 n 变化，就必须按深度算。

3.3 原地算法的判定与常见手法

"原地"这个词在408里出现得不少，它的含义是：算法只使用常数级别的额外空间，不随输入规模增长。

实现原地操作的常见手法有三种，掌握了这三种，绝大多数"要求 O(1) 空间"的题目都能应付。

第一种，双指针。链表的原地逆置就是典型：用三个指针分别记录当前、前驱、后继，边走边改指针方向，最后把头的 next 置空。整个过程只用了三个指针变量，空间 O(1)；顺序表的原地逆置用两个指针从两端往中间走，空间也是 O(1)。

第二种，就地交换与覆盖。数组的原地删除（删除所有值为 x 的元素）用一个写指针和一个读指针，读指针扫一遍，遇到不等于 x 的就写到写指针位置。空间 O(1)，时间 O(n)。

第三种，利用数组下标作为标记。比如"找出数组中所有重复出现的数字"这类题，如果数值范围在 1 到 n 之间，可以把数字放到它该在的位置上（即下标为 a[i]-1 的位置），通过交换实现原地标记，不需要额外的哈希表。

这三种手法的共同特征是：不用新建容器，所有操作都在原结构上完成。写算法设计题时，如果题目限制了空间复杂度，第一反应应该是"我能不能用指针在原结构上做文章"，而不是"我能不能建个辅助数组"。

4. 408高频结构的复杂度速查与推导

4.1 线性表与字符串的复杂度画像

顺序表的核心操作里，按位查找是 O(1)，这是它最大的优势，因为可以直接通过下标算出地址；插入和删除是 O(n)，因为需要移动元素，平均移动 n/2 个。链表正好反过来：按位查找是 O(n)，因为必须从头遍历；插入和删除是 O(1)，前提是你已经拿到了目标位置的前驱指针。这个"前提"很关键，很多题目问"在单链表中删除某个结点的时间复杂度"，如果没给前驱，那还得先找，总代价还是 O(n)。

这里有个常考细节：单链表删除给定结点 p。如果只给 p 不给前驱，标准做法是把 p 的后继结点 q 的值复制到 p，然后删掉 q。这个技巧让删除变成了 O(1)，但它有个前提——p 不是尾结点。如果 p 是最后一个结点，就没法用这个办法。408选择题喜欢在这里挖坑，问"该操作在什么情况下失效"。

字符串的模式匹配也是重点。朴素匹配（BF算法）最坏时间复杂度 O(nm)，n 是主串长度，m 是模式串长度。KMP 算法的时间复杂度是 O(n+m)，这个结论必须记住。KMP 的空间复杂度是 O(m)，因为要多开一个 next 数组（或者叫部分匹配表）。这两组数字在真题里反复出现。

KMP 的复杂度为什么是 O(n+m) 而不是 O(nm)？因为主串指针 i 从不回溯，每次比较要么匹配成功 i 前进，要么失配时模式串指针 j 根据 next 数组回退，而 j 的回退总次数不超过 j 的递增总次数，所以整体是线性的。这个分析思路在综合题里可能会被要求写出来。

4.2 树与二叉树的复杂度分层

二叉树的操作复杂度跟树高 h 直接相关，这是贯穿整章的主线。

二叉排序树的查找、插入、删除都是 O(h)，平均 h=logn，最坏 h=n（退化成单支树）。这个"最坏"是引入平衡树的原因，408考 AVL 树的旋转时，经常顺带问一句"引入平衡的动机是什么"，答"把最坏情况从 O(n) 压到 O(logn)"就够了。

完全二叉树有几个特殊的复杂度结论值得记：高度是 ⌊log₂n⌋+1；第 i 个结点的左孩子是 2i，右孩子是 2i+1（从1开始编号）；最后一个非叶结点是 ⌊n/2⌋。这几个公式在建堆、堆排序、完全二叉树的性质题里都要用。

哈夫曼树的构造，n 个叶子的哈夫曼树需要合并 n-1 次，如果每次从集合里找最小的两个用堆实现，总复杂度是 O(nlogn)。如果每次线性扫描找最小两个，是 O(n²)。408通常默认考的是前者的结论，但偶尔会问"如果朴素实现呢"，这时候要能切换。

4.3 图算法的复杂度过关清单

图的复杂度分析必须区分存储方式，这是所有易错点里最要命的一个。邻接矩阵和邻接表的复杂度完全不同，答错存储方式等于全错。

这里 n 是顶点数，e 是边数。

Prim 和 Kruskal 的选择是个经典考点。稠密图（e 接近 n²）用 Prim，因为 O(n²) 和邻接矩阵的遍历代价匹配；稀疏图（e 远小于 n²）用 Kruskal，因为 O(eloge) 在 e 小的时候更优。这个选择题几乎每年都有，答"稠密 Prim、稀疏 Kruskal"就对了。

Dijkstra 的复杂度，教材上写的 O(n²) 是不带堆优化的版本，每次要线性扫描找最小值。如果用优先队列（堆）优化，可以做到 O((n+e)logn) 或者 O(elogn)。408 主要考不带堆的经典版本，O(n²)，但如果题目里有"用堆优化"的字样，就要切换到优化后的答案。

Floyd 三重循环，O(n³)，空间 O(n²)（要存距离矩阵）。它的代码特别短，因此很多人会低估它的复杂度，实际上三层循环每层都跑 n 次，实打实的立方级。

拓扑排序，如果用邻接表加一个入度数组，每个顶点入队一次出队一次，每条边被访问一次，总复杂度 O(n+e)；如果用邻接矩阵，每次找入度为0的顶点要扫一行，总复杂度 O(n²)。

4.4 排序算法的复杂度全景对比

这张表是408最高频的记忆内容，但很多人只背了平均时间复杂度，忽略了稳定性和空间，结果综合题一问就露馅。

这张表里有几个点值得单独拎出来说。

第一，直接插入排序的最好情况是 O(n)，发生在原序列已经有序的时候，每次插入只需比较一次不移动。这个特性是"自适应"的体现，也是它比简单选择排序优秀的地方——简单选择排序无论输入什么都是 O(n²)，因为它每趟都要完整扫描找最小值。

第二，希尔排序的时间复杂度和增量序列有关，教材给的 O(n^1.3) 是 Hibbard 增量下的经验值，实际上是个未完全解决的问题。408一般不会深究，但会考"希尔排序是否稳定"，答案是不稳定，因为相同元素可能被分到不同组里交换位置。

第三，堆排序的建堆过程是 O(n)，这个前面提过，容易单独出题。整个堆排序是"建堆 O(n) + n 次调整每次 O(logn)" = O(nlogn)。空间 O(1) 是因为在原数组上操作，不用额外数组，但递归实现的调整函数会有栈空间，迭代实现才是严格 O(1)。

第四，基数排序的复杂度 O(d(n+r))，d 是位数，r 是基数。它不基于比较，所以不受 Ω(nlogn) 下界的约束，但需要额外空间 O(n+r)。

5. 常见错题类型与排查方法

5.1 循环分析里最容易翻车的四种写法

我在整理错题时发现，循环复杂度的错误高度集中在四类，几乎能覆盖我踩过的所有坑。

第一类，忘记循环变量的变化不是加一。前面提过i=i*2和i=i*i，这里再补一个更隐蔽的：

for (int i = 0; i < n; i++) for (int j = 0; j < n; j += i) ...;

当 i=0 时，内层j += i会导致死循环，这题本身就是错题。但如果改成j += i+1，内层次数是 n/(i+1)，总次数是 n×(1+1/2+1/3+...+1/n)，这是调和级数，量级是 nlogn。这个结论相当偏，但它说明一个道理：内层的步长依赖外层变量时，一定要写出求和式，不能凭感觉。

第二类，把 while 循环当 for 循环看。

int i = n; while (i > 1) { i = i / 2; }

这个执行 ⌊log₂n⌋ 次，O(logn)。有人会误以为是 n 次，因为看到 i 从 n 开始。关键看的是变化方式，不是起始值。

第三类，忽略循环体内的常数级大循环。

for (int i = 0; i < n; i++) { for (int j = 0; j < 1000; j++) { ...; } }

内层固定 1000 次，与 n 无关，所以整体是 O(n)，不是 O(1000n) 更不是 O(n²)。1000 作为常数被吸收掉。这类题的迷惑性在于内层看起来是双层结构，实际上第二层不随 n 增长。

第四类，break 语句的影响。

for (int i = 0; i < n; i++) { if (a[i] == x) break; }

这个循环的复杂度取决于 x 在数组中的位置。最好情况 O(1)（第一个就是），最坏 O(n)（最后或者不存在），平均 O(n)。如果题目问"时间复杂度"，默认答 O(n)；如果问"最好情况"，答 O(1)。这种题的失分点在于：有人答 O(1) 因为"找到就停了"，忽略了大O描述的是最坏或平均的量级。

5.2 递归复杂度计算的三个高频误区

递归的坑比循环更深，因为看不到显式的循环次数，只能靠递推式。

误区一，把递归树的高度当成复杂度。归并排序的递归树高是 logn，但复杂度不是 O(logn)，而是 O(nlogn)，因为每一层的工作量是 n。正确的做法是把每层的工作量加起来，而不是只数层数。

误区二，忽略递归调用出现在循环里的情况。

void f(int n) { if (n <= 0) return; for (int i = 0; i < n; i++) f(n / 2); }

这个递推式是 T(n) = n×T(n/2) + O(n)，展开后是 O(n^log₂n)，量级相当大。很多人一看是 n/2 就下意识写 O(nlogn)，忽略了循环把递归调用放大了 n 倍。判断方法很简单：看递归调用语句在不在循环体内，在的话就要乘以循环次数。

误区三，分不清递归式和递推式。严格说这两个词在408语境下可以混用，但解题时的思路不同。递归式是从代码直接读出来的关系（比如T(n)=T(n-1)+1），递推式是展开后得到的通项。考试时要先写出递归式，再展开，两步都写在答题纸上，这样即使最后答案算错，过程分也能拿到。

5.3 答题规范与踩分点

算法设计题的复杂度分析部分，虽然只有一两行，但踩分点很明确。

第一，必须写大O记号，不能只写"执行了n次"。标准写法是"时间复杂度为 O(n)"，如果只写"n次"，阅卷老师可能不认。

第二，最好附上一句简短的推导。比如"外层循环执行 n 次，内层循环平均执行 n/2 次，总次数 O(n²)"。这句话不占地方，但能证明你不是蒙的。

第三，空间复杂度要明确说明是"辅助空间"。有些同学写"空间复杂度 O(n)，因为数组占了 n 个位置"，这是错的，数组是输入，不算辅助空间。正确的写法是"除输入数组外，仅使用常数个临时变量，空间复杂度 O(1)"。

第四，如果算法有多种实现，要说明你选的是哪一种以及为什么。比如"采用迭代方式实现，相比递归版本节省了 O(logn) 的栈空间"，这一句能体现你对自己的方案有清醒认识。

注意：408的算法题一般要求用 C 或 C++ 描述，伪代码也可以，但复杂度分析必须写在算法之后，位置不能乱。有些同学习惯把分析写在注释里，虽然不算错，但阅卷时不显眼，容易漏看。老老实实单独起一行写。

6. 训练方法与考场策略

6.1 手推加代码验证的双轨训练

复杂度分析光看书是学不会的，必须动手。我的方法是"手推一遍，代码验一遍"。

手推就是拿纸笔，看到一段代码，先自己估一个复杂度，然后把循环次数真正算出来，对照一下。比如看到双层循环，先估 O(n²)，然后具体算 1+2+...+n，确认是 n(n+1)/2，量级对得上。

代码验证更直接：写个小程序，在循环体里放一个计数器，跑 n=10、100、1000 三组数据，看计数器的增长倍数。如果 n 扩大10倍，计数器扩大约100倍，那就是 O(n²)；扩大约10倍，是 O(n)；扩大约 3.3 倍（log₁₀1000/log₁₀100 ≈ 1.5，实际是 log 关系），是 O(logn)。这个方法对判断那些拿不准的循环特别有效。

举个我自己的例子。第一次遇到i = i * i的循环，我推了半天不确定是 logn 还是 loglogn，写了个小程序跑了一下：n=10 时循环 3 次左右，n=100 时 4 次，n=10000 时 5 次。n 从 10 涨到 10000 涨了 1000 倍，次数只从 3 涨到 5，明显是 loglogn 级别。这个验证过程比看十遍书都管用。

6.2 错题本的正确建法

复杂度这块的错题本，不要只抄题目和答案，要抄"我当时的错误思路"和"正确的判定路径"。

我的格式是这样的：左边写题目代码，中间写我的答案和错因，右边写正确推导。比如那道i=i*2外层、内层j<=i的题，我的错因是"看到双层嵌套直接写了 O(nlogn)，没有注意到内层上限依赖外层"。正确推导是"外层 logn 次，内层依次是 1,2,4,...,总量是等比数列求和，O(n)"。

错因分类很重要。我把错因归成四类：忘记循环变量非线性变化、混淆最坏和平均、空间复杂度口径错误、递归式写错。每类积累到五道题以上，就能看出自己的薄弱环节在哪。这个方法比刷一百道题不做归纳要有效得多。

6.3 考场上的时间分配与检查顺序

408考试时间 180 分钟，复杂度分析相关的题目分散在各处，不可能单独留出大块时间。我的策略是"选择题快速过，算法题留足推导时间"。

选择题里的复杂度题，如果 30 秒内没有思路，直接跳过，标记一下回头再看。这类题的特点是"会的人一眼出答案，不会的人想十分钟也想不出来"，卡住就是浪费时间。回头再看的时候，往往换个角度就想通了。

算法设计题写到复杂度分析那一步，至少留 3 分钟。这 3 分钟不是用来重新推导的，而是用来"复核"：我写的时间复杂度跟我实际的代码逻辑对不对得上？如果代码里嵌套了两层循环，我写的 O(nlogn) 是不是有问题？空间复杂度我算的是辅助空间还是总空间？这三个问题过一遍，能拦下大部分低级错误。

最后交卷前，专门花两分钟扫一遍所有涉及复杂度的空和答题区域，看有没有漏写单位、漏写 O、把 logn 写成 n 之类的问题。这类错误一旦发生，扣分是实打实的，而检查成本极低，属于性价比最高的检查项。

我个人在实际备考中的体会是，复杂度分析这东西前期靠理解，后期靠熟练。理解阶段要把每个结论的来历搞清楚，比如为什么建堆是 O(n)、为什么快排最坏是 O(n²)；熟练阶段要形成条件反射，看到双层嵌套先判断内外层关系，看到递归先写递推式。这两个阶段不能颠倒，跳过理解直接刷题，遇到变体就废；只理解不刷题，考场上算得慢还容易慌。找个本子，把每次算错的循环和递归都抄下来，隔一周重算一遍，算对三次以上的划掉，剩下的就是真正的硬骨头。