408 高频考点精讲:复杂度分析(Time and Space Complexity Analysis)¶
模块归属:数据结构 · 绪论及基本概念
考点层级:微观细分考点(近十年考查 \(\ge 3\) 次)
适用对象:408 计算机考研备考学生
一、 考情档案¶
- 近十年考查频次:5 次(2016~2025 年:2016#7、2017#1、2019#1、2022#1、2025#1)
- 历年总考查频次:9 次(含 2009#1、2011#1、2012#1、2014#1 等)
- 出题形式:单项选择题(分值 2 分),常年固定置于全卷首题(第 1 题),亦结合图遍历、拓扑排序算法综合考查。
- 命题特点:
- 试卷门面基石:近十年中有 4 次直接作为全卷第 1 题呈现,重点检验考生的程序阅读、循环边界敏锐度以及离散数学基础。
- 题型演进鲜明:早期题目多考查简单单重循环或固定倍减循环;近十年来命题重点全面转向非线性步长更新(如平方关系判断 \(i \times i < n\)$ \text{)、累加变量边界约束(如} $\(sum += ++i\))以及外层指数递增引发的等比级数依赖循环。
- 考查重点高度聚焦:考查重点集中在最坏情况时间复杂度的渐近表示,要求考生摒弃“直觉相乘”的粗糙估算,掌握基于离散求和、设参换元以及主定理的精确推导方法。
近十年考查年份分布:
2016 2017 2018 2019 2020 2021 2022 2023 2024 2025
+ + - + - - + - - +
(#7) (#1) (#1) (#1) (#1)
二、 具体考察内容¶
1. 渐近符号体系及数学定义¶
算法的计算复杂度关注当问题规模 \(n\)$ \text{趋近于无穷大(} $\(n \to \infty\))时,算法资源开销(时间或空间)的增长率阶数,忽略常数因子与低阶次项。
(1) 渐近上界:大 O 符号(Big-O)¶
- 定义:设 \(T(n)\)$ \text{与} $\(f(n)\)$ \text{是定义在正整数集上的非负函数。若存在正常数} $\(c > 0\)$ \text{和整数} $\(n_0 \ge 1\)$ \text{,使得对任意} $\(n \ge n_0\),恒有: $\(0 \le T(n) \le c \cdot f(n)\)$ 则记作 \(T(n) = O(f(n))\)。
- 物理意义:\(f(n)\)$ \text{是} $\(T(n)\)$ \text{的渐近上界。在算法分析中,通常用大} $\(O\) 符号表征算法在最坏情况下的时间开销上界,且要求给出尽可能紧确(Tight)的函数。
(2) 渐近下界:大 \(\Omega\) 符号(Big-Omega)¶
- 定义:设 \(T(n)\)$ \text{与} $\(g(n)\)$ \text{是非负函数。若存在正常数} $\(c > 0\)$ \text{和整数} $\(n_0 \ge 1\)$ \text{,使得对任意} $\(n \ge n_0\),恒有: $\(0 \le c \cdot g(n) \le T(n)\)$ 则记作 \(T(n) = \Omega(g(n))\)。
- 物理意义:\(g(n)\)$ \text{是} $\(T(n)\) 的渐近下界,反映了算法解决该类问题至少需要的计算代价。
(3) 紧确渐近界:大 \(\Theta\) 符号(Big-Theta)¶
- 定义:设 \(T(n)\)$ \text{与} $\(h(n)\)$ \text{是非负函数。若存在正常数} $\(c_1, c_2 > 0\)$ \text{和整数} $\(n_0 \ge 1\)$ \text{,使得对任意} $\(n \ge n_0\),恒有: $\(0 \le c_1 \cdot h(n) \le T(n) \le c_2 \cdot h(n)\)$ 则记作 \(T(n) = \Theta(h(n))\)。
- 充要条件: $$ T(n) = \Theta(h(n)) \iff \text{T(n) = O(h(n)) \quad \text{且} \quad T(n) = \Omega(h(n))} $$
(4) 极限判定法¶
设极限 \(\lim_{n \to \infty} \frac{T(n)}{f(n)} = L\),则: * 若 \(L = 0\)$ \text{,说明} $\(T(n)\)$ \text{的增长阶数严格低于} $\(f(n)\)$ \text{,记作} $\(T(n) = o(f(n))\); * 若 \(0 < L < +\infty\)$ \text{,说明} $\(T(n)\)$ \text{与} $\(f(n)\)$ \text{同阶,即} $\(T(n) = \Theta(f(n))\); * 若 \(L = +\infty\)$ \text{,说明} $\(T(n)\)$ \text{的增长阶数严格高于} $\(f(n)\)$ \text{,记作} $\(T(n) = \omega(f(n))\)。
(5) 常见渐近复杂度阶的层次序列¶
在考研数据结构范畴内,常见时间复杂度增长率由慢至快的严格偏序关系为: $\(O(1) < O(\log_2 n) < O(n^{\alpha}) \, (0 < \alpha < 1) < O(n) < O(n \log_2 n) < O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n)\)$
(6) 渐近运算法则¶
- 加法法则(并列结构/顺序执行): 若算法由两个独立的顺序步骤构成,复杂度分别为 \(T_1(n) = O(f(n))\)$ \text{和} $\(T_2(n) = O(g(n))\),则: $\(T(n) = T_1(n) + T_2(n) = O(\max(f(n), g(n)))\)$
- 乘法法则(独立嵌套结构): 若循环外层执行次数为 \(T_1(n) = O(f(n))\)$ \text{,且对于每次外层迭代,内层独立执行} $\(T_2(n) = O(g(n))\) 次,则: $\(T(n) = T_1(n) \times T_2(n) = O(f(n) \times g(n))\)$ 注:若内层执行次数与外层变量存在数值依赖关系,则乘法法则失效,必须采用级数求和法。
2. 非递归循环结构的时间复杂度分析法则¶
在代码执行中,基本操作语句的频度计数是复杂度分析的核心。
(1) 单重循环分析范式¶
- 固定步长线性型:
for (int i = 0; i < n; i += c):循环体执行 \(\lceil n/c \rceil\)$ \text{次,时间复杂度为} $\(O(n)\)。 - 几何倍增/倍减型(对数阶):
for (int i = 1; i < n; i *= a)(\(a > 1\) 为常数): 设执行次数为 \(k\)$ \text{。第} $\(k\)$ \text{次循环时,变量} $\(i = a^k\)$ \text{。由退出条件} $\(a^k \ge n\)$ \text{解得} $\(k = \lceil \log_a n \rceil\)$ \text{,时间复杂度为} $\(O(\log n)\)。 - 设参换元法(代数状态方程模型): 当控制变量呈非线性增长,或者循环终止条件依赖于累加变量时,应使用设参换元法: 设循环体共执行 \(k\)$ \text{次,求出第} $\(k\)$ \text{次执行完毕时控制变量关于} $\(k\)$ \text{的函数表达式} $\(V(k)\)$ \text{,令} $\(V(k)\)$ \text{达到或突破边界值,解出} $\(k\)。
- 范式一:等差累加条件型(如
while (sum < n) sum += ++i;)
初始 \(i=0, sum=0\)。
第 \(k\)$ \text{次执行后,} $\(i = k\),\(sum = \sum_{m=1}^k m = \frac{k(k+1)}{2}\)。
终止条件为 \(\frac{k(k+1)}{2} \ge n \implies k^2 + k \ge 2n \implies k \approx \sqrt{2n} \implies k = \Theta(\sqrt{n}) = O(n^{1/2})\)。 - 范式二:非线性开方条件型(如
while (n >= (x + 1) * (x + 1)) x++;)
第 \(k\)$ \text{次执行后,} $\(x = k\)。
终止条件为 \((k+1)^2 > n \implies k > \sqrt{n} - 1 \implies k = \Theta(\sqrt{n}) = O(n^{1/2})\)。
(2) 多重依赖循环与级数求和法¶
当内层循环的终止边界取决于外层循环变量时,必须采用离散数学求和符号表达: $\(T(n) = \sum_{i} T_{\text{inner}}(i)\)$
- 模型 A:外层非线性增长,内层线性依赖(算术级数型)
典型代码结构(2025 年真题原型): - 外层循环边界由 \(i^2 < n\)$ \text{决定,变量} $\(i\)$ \text{取值范围为} $\(0, 1, 2, \dots, M\)$ \text{,其中} $\(M = \lfloor\sqrt{n}\rfloor\)。
- 对于外层给定的 \(i\)$ \text{,内层执行} $\(i\) 次。
- 总执行次数为: $\(T(n) = \sum_{i=0}^{\lfloor\sqrt{n}\rfloor} i = \frac{\lfloor\sqrt{n}\rfloor(\lfloor\sqrt{n}\rfloor + 1)}{2} = \frac{1}{2} (\sqrt{n})^2 + O(\sqrt{n}) = \Theta(n)\)$
-
核心辨析:尽管外层只循环了 \(\sqrt{n}\)$ \text{轮,但内层单次最大执行次数为} $\(\sqrt{n}\)$ \text{,求和后最终阶数为} $\(O(n)\)。
-
模型 B:外层对数增长,内层指数依赖(几何级数型)
典型代码结构(2022 年真题原型): - 外层循环变量 \(i\)$ \text{呈几何级数翻倍增长:} $\(i \in \{2^0, 2^1, 2^2, \dots, 2^{m-1}\}\)$ \text{,其中} $\(2^{m-1} < n \le 2^m\)$ \text{,即迭代次数} $\(m = \lceil \log_2 n \rceil\)。
- 对于每个特定的 \(i = 2^t\)(\(0 \le t \le m-1\)$ \text{),内层循环执行} $\(2^t\) 次。
-
总执行次数利用等比数列求和公式: $$T(n) = \sum_{t=0}^{m-1} 2^t = \frac{1 \cdot (1
-
2^m)}{1
-
2} = 2^m
-
1$$
- 由 \(n \le 2^m < 2n\),可得: $\(n - 1 \le T(n) < 2n - 1 \implies T(n) = \Theta(n)\)$
-
核心辨析:不可粗暴使用外层循环次数 \(\log_2 n\)$ \text{乘以内层最大次数} $\(n\)$ \text{得出} $\(O(n \log_2 n)\)$ \text{。内层次数在前面对数轮中极其微小,几何求和由最后一项直接主导,总代价为线性阶} $\(O(n)\)。
-
模型 C:调和级数型
典型代码结构: - 外层 \(i\)$ \text{取} $\(1, 2, \dots, n\)$ \text{;内层执行} $\(\lfloor n/i \rfloor\) 次。
- 总次数: $\(T(n) = \sum_{i=1}^n \left\lfloor \frac{n}{i} \right\rfloor \approx n \sum_{i=1}^n \frac{1}{i} = n (\ln n + \gamma + O(1/n)) = \Theta(n \log n)\)$
3. 递归算法时间复杂度分析法则¶
(1) 递归树展开模型¶
递归算法的执行过程可抽象为一棵递归调用树。树中的每个节点表示一次递归调用,节点的值代表该次调用中除子调用外所消耗的本层开销。 总时间复杂度等于递归树所有节点开销之和: $$ \text{T(n) = \sum_{\text{深度 } d} (\text{第 } d \text{ 层节点数} \times \text{单节点处理代价})} $$
(2) 主定理(Master Theorem)¶
主定理为分析分治递归算法时间复杂度提供了通用数学工具。 对于形如以下形式的分治递推关系式: $\(T(n) = a T\left(\frac{n}{b}\right) + f(n)\)$ 其中常数 \(a \ge 1\)$ \text{表示子问题数量,} $\(b > 1\)$ \text{表示子问题规模缩减比例,} $\(f(n)\) 为划分与合并操作的耗时。 将 \(f(n)\)$ \text{与临界项} $\(n^{\log_b a}\)(代表递归树底层叶节点的渐近代价)进行比较,分为三种情形:
-
情形 1:叶节点代价主导(多项式弱于临界项)
若存在常数 \(\epsilon > 0\),使得: $\(f(n) = O\left(n^{\log_b a - \epsilon}\right)\)$ 则总时间复杂度由叶节点决定: $\(T(n) = \Theta\left(n^{\log_b a}\right)\)$ -
情形 2:各层代价平衡(与临界项同阶,含对数因子)
若存在常数 \(k \ge 0\),使得: $\(f(n) = \Theta\left(n^{\log_b a} \log^k n\right)\)$ 则总时间复杂度为: $\(T(n) = \Theta\left(n^{\log_b a} \log^{k+1} n\right)\)$ 特别地,当 \(k=0\)$ \text{,即} $\(f(n) = \Theta\left(n^{\log_b a}\right)\)$ \text{时,有} $\(T(n) = \Theta\left(n^{\log_b a} \log n\right)\)。 -
情形 3:根节点代价主导(多项式强于临界项)
若存在常数 \(\epsilon > 0\),使得: $\(f(n) = \Omega\left(n^{\log_b a + \epsilon}\right)\)$ 且满足正则性条件:存在常数 \(c < 1\)$ \text{与充分大的} $\(n\)$ \text{,使得} $\(a f(n/b) \le c f(n)\),则总时间复杂度由根节点划分合并代价决定: $\(T(n) = \Theta(f(n))\)$
(3) 考研高频经典分治递归方程对照表¶
| 经典算法与场景 | 递归方程 | 参数解析 | 临界项 \(n^{\log_b a}\) | 适用情形 | 最终渐近复杂度 |
|---|---|---|---|---|---|
| 二分查找 | \(T(n) = T(n/2) + O(1)\) | \(a=1, b=2, f(n)=1\) | \(n^{\log_2 1} = n^0 = 1\)$ \text{ | 情形 2 (} $\(k=0\)) | \(\Theta(\log n)\) |
| 归并排序 | \(T(n) = 2T(n/2) + O(n)\) | \(a=2, b=2, f(n)=n\) | \(n^{\log_2 2} = n^1 = n\)$ \text{ | 情形 2 (} $\(k=0\)) | \(\Theta(n \log n)\) |
| 快速排序(平衡划分) | \(T(n) = 2T(n/2) + O(n)\) | \(a=2, b=2, f(n)=n\) | \(n^1 = n\)$ \text{ | 情形 2 (} $\(k=0\)) | \(\Theta(n \log n)\) |
| Karatsuba 大整数乘法 | \(T(n) = 3T(n/2) + O(n)\) | \(a=3, b=2, f(n)=n\) | \(n^{\log_2 3} \approx n^{1.585}\)$ \text{ | 情形 1 | } $\(\Theta(n^{\log_2 3})\) |
| Strassen 矩阵乘法 | \(T(n) = 7T(n/2) + O(n^2)\) | \(a=7, b=2, f(n)=n^2\) | \(n^{\log_2 7} \approx n^{2.807}\)$ \text{ | 情形 1 | } $\(\Theta(n^{\log_2 7})\) |
4. 空间复杂度判定及原地工作属性¶
- 空间复杂度定义:衡量算法在运行过程中临时占用的存储空间大小度量,记为 \(S(n)\)。不包含输入数据本身所占用的物理存储空间。
- 原地工作(In-place)严格界定: 若算法运行所需的额外辅助存储空间不随问题规模 \(n\) 的增大而增大,即辅助空间复杂度满足: $\(S(n) = O(1)\)$ 则称该算法为原地工作(In-place)。 辨析:原地工作并不等同于绝对不使用任何辅助空间,而是仅允许使用常数阶辅助变量。
- 递归栈空间开销模型: 递归程序每进行一级调用,均需在运行时栈中分配一个活动记录(栈帧)。递归调用的空间复杂度直接取决于递归调用树的最大深度: $$ \text{S(n) = O(\text{递归树的最大深度})} $$
- 单链式退化递归(如单向累加、快速排序最坏划分):树深为 \(n\),\(S(n) = O(n)\);
- 平衡二分式递归(如二分查找、快速排序最优划分):树深为 \(\lfloor \log_2 n \rfloor + 1\),\(S(n) = O(\log n)\);
- 树的深度优先遍历(DFS):空间复杂度取决于树的高度 \(h\)$ \text{。对于含} $\(n\)$ \text{个节点的二叉树,最好情况为满二叉树} $\(h = O(\log n)\)$ \text{,最坏情况为单支树} $\(h = O(n)\)。
5. 存储结构对图及特定算法复杂度的制约机理¶
算法的时间复杂度高度依赖于底层数据结构的物理存储方式。以考研常考的图算法为例: * 拓扑排序(AOV 网)复杂度对比: - 邻接表存储: 1. 统计各顶点的入度:遍历全部顶点的出边表,弧被扫描的总次数为 \(e\)$ \text{,时间为} $\(O(n + e)\); 2. 入度为 0 的顶点入栈/入队:时间为 \(O(n)\); 3. 拓扑排序主循环:每个顶点出栈一次(共 \(n\)$ \text{次),每条出边被访问并减少对应终点入度一次(共} $\(e\)$ \text{次),主循环耗时} $\(O(n + e)\)。 4. 综上,基于邻接表实现的拓扑排序时间复杂度为: $\(T(n) = O(n + e)\)$ - 邻接矩阵存储: 1. 统计顶点入度:扫描整个矩阵中每一列的所有元素,时间为 \(O(n^2)\); 2. 主循环中,每次弹出一个顶点后,需遍历矩阵该顶点对应行的 \(n\)$ \text{个元素以删除其出边,时间为} $\(n \times O(n) = O(n^2)\)。 3. 综上,基于邻接矩阵实现的拓扑排序时间复杂度为: $\(T(n) = O(n^2)\)$ * 图的遍历(BFS / DFS)复杂度对比: - 邻接表:每个顶点访问一次,每条边或弧被检查两次或一次,复杂度为 \(O(n + e)\); - 邻接矩阵:寻找每个顶点的所有邻接点均需扫描整行,复杂度恒为 \(O(n^2)\)。
三、 近十年真题精讲(2016~2025)¶
【真题 1】2025 年 408 第 1 题 · 依赖平方条件的外层双重循环¶
题目
以下 C 代码的时间复杂度是( )。
【解析】¶
- 外层循环取值范围: 外层循环控制条件为 \(i \times i < n\)$ \text{,即} $\(i < \sqrt{n}\)。 变量 \(i\) 从 0 开始,依次自增 1,其离散取值为: $$ \text{i \in {0, 1, 2, \dots, M}, \quad \text{其中 } M = \lfloor\sqrt{n - 1}\rfloor \approx \sqrt{n}} $$
- 内层循环执行频度:
对于外层给定的每一个 \(i\)$ \text{,内层循环
for (int j = 0; j < i; j++)执行} $\(i\) 次。 - 构建离散级数并求和:
基本操作
count++的总执行次数为等差数列求和: $\(T(n) = \sum_{i=0}^{M} i = \frac{M(M + 1)}{2}\)$ 将 \(M \approx \sqrt{n}\) 代入: $\(T(n) = \frac{\sqrt{n}(\sqrt{n} + 1)}{2} = \frac{n + \sqrt{n}}{2} = \Theta(n)\)$ - 选项逐项辨析:
- A 项错误:若内层与外层均为对数次迭代方可得出,此处包含求和累加项,远高于对数阶。
- B 项正确:总执行步数与 \(n\)$ \text{呈严格线性关系,渐近复杂度为} $\(O(n)\)。
- C 项错误:典型混淆选项,若错误地将外层当成 \(O(n)\) 且内层当成对数阶才会误选。
- D 项错误:若误忽视外层平方限制(误当作 \(i < n\)$ \text{),则会算出} $\(\sum_{i=0}^n i = O(n^2)\)。
正确答案:B
【真题 2】2022 年 408 第 1 题 · 外层指数递增内层依赖循环¶
题目
下列程序段的时间复杂度是( )。
【解析】¶
- 外层循环离散取值分析: 外层循环初始 \(i = 1\)$ \text{,每次迭代乘 2(} $\(i *= 2\))。 设外层循环执行了 \(m\)$ \text{次,变量} $\(i\) 依次取值为: $\(i \in \{1, 2, 4, 8, \dots, 2^{m-1}\} = \{2^0, 2^1, 2^2, \dots, 2^{m-1}\}\)$ 由循环退出条件 \(i \ge n\)$ \text{,即} $\(2^m \ge n\)$ \text{且} $\(2^{m-1} < n\)$ \text{,得出} $\(m = \lceil \log_2 n \rceil\)。
-
内层循环累计频度分析: 对于每一个固定的 \(i\)$ \text{,内层循环
for (int j = 0; j < i; j++)执行} $\(i\) 次。 故总执行次数为等比数列求和: $$T(n) = \sum_{t=0}^{m-1} 2^t = \frac{1 -
2^m}{1
-
2} = 2^m
-
1$$
- 渐近阶数紧确放缩: 由于 \(2^{m-1} < n \le 2^m\),可得: $\(n \le 2^m < 2n\)$ 代入求和结果: $\(n - 1 \le T(n) < 2n - 1\)$ 依据大 \(O\)$ \text{与大} $\(\Theta\)$ \text{的数学定义,存在常数} $\(c_1 = 1, c_2 = 2\)$ \text{,使得当} $\(n \ge 2\)$ \text{时,恒有} $\(c_1 n \le T(n) \le c_2 n\)。因此: $\(T(n) = \Theta(n) \implies T(n) = O(n)\)$
- 选项逐项辨析:
- A 项错误:仅计算了外层循环的迭代轮数 \(\log_2 n\),完全遗漏了内层循环的开销。
- B 项正确:等比级数累加和受最高次项主导,整体呈线性阶 \(O(n)\)。
- C 项错误:这是极具迷惑性的典型错误选项!考生往往盲目使用乘法法则:误认为“外层执行 \(\log_2 n\)$ \text{次,内层最大执行} $\(n\)$ \text{次,故总时间为} $\(O(n \log_2 n)\)”。乘法法则仅在内外层相互独立时成立,此处内层上限严格受控于外层变量,必须使用级数求和。
- D 项错误:高估了内层与外层的增长规模。
正确答案:B
【真题 3】2019 年 408 第 1 题 · 非线性开方条件的单重循环¶
题目
设 n 是描述问题规模的非负整数,下列程序段的时间复杂度是( )。
【解析】¶
- 设参换元建立状态方程:
设该
while循环体共执行了 \(k\) 次。 - 初始状态(第 0 次):\(x_0 = 0\);
- 第 1 次执行后:\(x_1 = 1\);
- 第 2 次执行后:\(x_2 = 2\);
- \(\dots\)
- 第 \(k\)$ \text{次执行后:} $\(x_k = k\)。
- 临界终止条件判定: 循环继续的条件是 \(n \ge (x + 1)^2\)。 循环终止于第 \(k\) 次执行完毕后,控制条件首次不成立,即: $\((x_k + 1)^2 > n \iff (k + 1)^2 > n\)$ 同时在第 \(k-1\) 次时条件依然满足: $\(k^2 \le n\)$
- 求解执行次数 \(k\): 对不等式开平方: $\(\sqrt{n} - 1 < k \le \sqrt{n}\)$ 故循环执行次数为: $\(k = \lfloor \sqrt{n} \rfloor = \Theta(\sqrt{n}) = O(n^{1/2})\)$
- 选项逐项辨析:
- A 项错误:对数阶通常对应乘除倍增步长,此处 \(x\) 仅为线性递增,但因平方判断导致循环次数落在根号量级。
- B 项正确:\(k \approx \sqrt{n} = n^{1/2}\)。
- C 项及 D 项错误:均严重高估了循环执行的频度。
正确答案:B
【真题 4】2017 年 408 第 1 题 · 累加和边界判定的单重循环¶
题目
下列函数的时间复杂度是( )。
【解析】¶
- 设参换元与离散状态追踪:
设该循环体共迭代执行了 \(k\) 次。
注意语句
sum += ++i;的执行语义:变量 \(i\) 先自增 1,随后累加到sum中。 - 初始状态:\(i = 0, sum = 0\);
- 第 1 次迭代:\(i = 1, sum = 0 + 1 = 1\);
- 第 2 次迭代:\(i = 2, sum = 1 + 2 = 3\);
- 第 3 次迭代:\(i = 3, sum = 1 + 2 + 3 = 6\);
- \(\dots\)
- 第 \(k\)$ \text{次迭代:} $\(i = k, sum = \sum_{m=1}^k m = \frac{k(k + 1)}{2}\)。
- 临界终止不等式建立:
循环退出当且仅当
sum >= n,即: $\(\frac{k(k + 1)}{2} \ge n \iff k^2 + k - 2n \ge 0\)$ - 求解执行次数 \(k\) 的渐近阶: 求解一元二次方程正根: $\(k = \frac{-1 + \sqrt{1 + 8n}}{2} = \sqrt{2n + \frac{1}{4}} - \frac{1}{2} = \Theta(\sqrt{n}) = O(n^{1/2})\)$
- 选项逐项辨析:
- A 项错误:
sum呈二次方级数增长而非指数增长,故执行步数开平方而非取对数。 - B 项正确:渐近复杂度为 \(O(n^{1/2})\)。
- C 项及 D 项错误:未考虑循环步长 \(i\)$ \text{自身在不断递增导致
sum加速逼近上限} $\(n\)。
正确答案:B
【真题 5】2016 年 408 第 7 题 · 邻接表存储的拓扑排序算法复杂度¶
题目
若将 \(n\)$ \text{个顶点} $\(e\) 条弧的有向图采用邻接表存储,则拓扑排序算法的时间复杂度是( )。
A. \(O(n)\) B. \(O(n + e)\) C. \(O(n^2)\) D. \(O(n \cdot e)\)
【解析】¶
- 拓扑排序算法标准执行流程分解(Kahn 算法):
- 阶段一:入度统计
为了获取所有顶点的初始入度,算法需要扫描邻接表中所有顶点引出的所有边链表节点。全图共有 \(e\)$ \text{条弧,因此扫描全部弧节点的操作耗时为} $\(O(e)\)$ \text{。初始化数组耗时} $\(O(n)\)$ \text{,该阶段总耗时为} $\(O(n + e)\)。 - 阶段二:零入度顶点初始化
遍历所有顶点入度数组,将入度为 0 的顶点压入辅助栈(或队列)。共有 \(n\)$ \text{个顶点,耗时为} $\(O(n)\)。 - 阶段三:主循环拓扑输出及弧删除
- 每次从栈顶弹出一个顶点并输出:所有顶点最多入栈和出栈各 1 次,顶点处理的总耗时为 \(O(n)\);
- 遍历该顶点的出边链表,将对应终点的入度减 1:全过程中,每条弧恰好被遍历一次,入度扣减操作累计执行 \(e\)$ \text{次,该部分总耗时为} $\(O(e)\)。
- 总时间复杂度综合推导: 应用渐近加法法则,合并三个阶段的耗时: $\(T(n, e) = O(n + e) + O(n) + O(n + e) = O(n + e)\)$
- 选项逐项辨析:
- A 项错误:遗漏了遍历邻接边表以更新终点入度的开销 \(O(e)\)。
- B 项正确:邻接表存储下,拓扑排序的时间复杂度为 \(O(n + e)\)。
- C 项错误:\(O(n^2)\)$ \text{是基于“邻接矩阵”存储时的拓扑排序时间复杂度。在邻接矩阵中,查找零入度顶点与查找出边均需扫描矩阵的整行或整列,耗时} $\(O(n^2)\)。
- D 项错误:各顶点的边链表总长度为 \(e\)$ \text{而非} $\(n \cdot e\)$ \text{,不存在对每条边重复扫描} $\(n\) 次的操作。
正确答案:B
四、 核心解题套路及易错陷阱¶
1. 嵌套循环的“直觉相乘”陷阱(乘法法则盲目套用)¶
- 陷阱表象: 在分析形如下列代码的双重循环时: 考生极易产生直觉误区:“外层循环 \(i\)$ \text{翻倍,执行} $\(\log_2 n\)$ \text{次;内层循环上限是} $\(i\)$ \text{,最坏能达到} $\(n\)$ \text{次;因此总复杂度为} $\(O(n \log_2 n)\)。”
- 本质剖析: 乘法法则 \(T(n) = T_1(n) \times T_2(n)\)$ \text{成立的严格数学前提是:内层循环的执行次数与外层循环变量完全独立。一旦内层边界是外层变量(如} $\(j < i\)$ \text{),内层实际迭代次数在前期非常小(} $\(1, 2, 4, \dots\)$ \text{),仅在最后一轮才接近} $\(n\)。
- 破局法则(级数求和法): 凡是遇到内层依赖外层的代码,坚决禁止直觉相乘,必须严格书写离散级数 \(\sum\): $\(T(n) = \sum_{t=0}^{\lfloor \log_2 n \rfloor} 2^t = 2^{\lfloor \log_2 n \rfloor + 1} - 1 = \Theta(n)\)$ 等比级数的总和由其最后一项决定,整体为线性阶 \(O(n)\)。
2. 非线性步长及累加条件(“设参换元建立状态方程”解题法)¶
- 陷阱表象:
当循环条件出现
sum < n且sum += i,或者(x+1)*(x+1) <= n时,变量变化是非线性的,无法直接一眼看出迭代次数。 - 破局三步法:
- 第一步(设参数):设循环共迭代执行了 \(k\) 次;
- 第二步(表状态):求出第 \(k\)$ \text{次迭代结束时,控制变量的值关于} $\(k\)$ \text{的表达式} $\(V(k)\);
- 第三步(解方程):令 \(V(k)\)$ \text{满足跳出循环的临界关系式,解出一元方程中的} $\(k\),并提取最高阶项。
3. 脱离底层存储结构分析算法复杂度¶
- 陷阱表象: 题目询问“拓扑排序的时间复杂度”或“图遍历的时间复杂度”,考生不看前提条件直接死记硬背。
- 破局对比速查:
- 邻接表(顶点表与边表分离): 顶点扫描 \(O(V)\)$ \text{,边链表扫描累计} $\(O(E)\)$ \text{,算法复杂度大多表现为} $\(O(V + E)\)(如 BFS、DFS、拓扑排序)。
- 邻接矩阵(二维数组连续分布): 无论边数多少,遍历顶点的邻接点必须扫描整行 \(V\)$ \text{个元素,总复杂度恒为} $\(O(V^2)\)。
五、 考点速记清单¶
- 渐近阶次序列: $\(O(1) < O(\log_2 n) < O(\sqrt{n}) < O(n) < O(n \log_2 n) < O(n^2) < O(2^n) < O(n!)\)$
- 两类经典循环特征:
- 等差累加型(
sum += i或 \(i \times i < n\)$ \text{):变量呈二次方演变,循环次数必为开方阶} $\(O(\sqrt{n}) = O(n^{1/2})\)。 - 外倍增内依赖型(外层 \(i *= 2\)$ \text{,内层} $\(j < i\)$ \text{):等比级数累加,公比} $\(q=2\)$ \text{,总和由末项主导,复杂度恒为线性阶} $\(O(n)\)。
- 主定理三步速判(比较 \(f(n)\)$ \text{与} $\(n^{\log_b a}\)):
- \(f(n)\)$ \text{多项式小于临界项} $\(\implies T(n) = \Theta(n^{\log_b a})\);
- \(f(n)\)$ \text{与临界项同阶} $\(\implies T(n) = \Theta(n^{\log_b a} \log n)\);
- \(f(n)\)$ \text{多项式大于临界项} $\(\implies T(n) = \Theta(f(n))\)。
- 空间复杂度准则:
- 原地工作:辅助空间 \(S(n) = O(1)\)(允许常数个辅助变量,非零存储)。
- 递归开销:空间复杂度取决于递归调用树的最大调用深度(树高)。