跳转至

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 年真题原型):
    for (int i = 0; i * i < n; i++)
        for (int j = 0; j < i; j++)
            count++;
    
  • 外层循环边界由 \(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 年真题原型):

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

  • 外层循环变量 \(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:调和级数型
    典型代码结构:

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

  • 外层 \(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. 情形 1:叶节点代价主导(多项式弱于临界项)
    若存在常数 \(\epsilon > 0\),使得: $\(f(n) = O\left(n^{\log_b a - \epsilon}\right)\)$ 则总时间复杂度由叶节点决定: $\(T(n) = \Theta\left(n^{\log_b a}\right)\)$

  2. 情形 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. 情形 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 代码的时间复杂度是( )。

int count = 0;
for (int i = 0; i * i < n; i++)
    for (int j = 0; j < i; j++)
        count++;
A. \(O(\log_2 n)\)          B. \(O(n)\)          C. \(O(n \log_2 n)\)          D. \(O(n^2)\)

【解析】

  1. 外层循环取值范围: 外层循环控制条件为 \(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}} $$
  2. 内层循环执行频度: 对于外层给定的每一个 \(i\)$ \text{,内层循环 for (int j = 0; j < i; j++) 执行} $\(i\) 次。
  3. 构建离散级数并求和: 基本操作 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)\)$
  4. 选项逐项辨析:
  5. A 项错误:若内层与外层均为对数次迭代方可得出,此处包含求和累加项,远高于对数阶。
  6. B 项正确:总执行步数与 \(n\)$ \text{呈严格线性关系,渐近复杂度为} $\(O(n)\)。
  7. C 项错误:典型混淆选项,若错误地将外层当成 \(O(n)\) 且内层当成对数阶才会误选。
  8. D 项错误:若误忽视外层平方限制(误当作 \(i < n\)$ \text{),则会算出} $\(\sum_{i=0}^n i = O(n^2)\)。

正确答案:B


【真题 2】2022 年 408 第 1 题 · 外层指数递增内层依赖循环

题目
下列程序段的时间复杂度是( )。

int sum = 0;
for (int i = 1; i < n; i *= 2)
    for (int j = 0; j < i; j++)
        sum++;
A. \(O(\log_2 n)\)          B. \(O(n)\)          C. \(O(n \log_2 n)\)          D. \(O(n^2)\)

【解析】

  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\)。
  2. 内层循环累计频度分析: 对于每一个固定的 \(i\)$ \text{,内层循环 for (int j = 0; j < i; j++) 执行} $\(i\) 次。 故总执行次数为等比数列求和: $$T(n) = \sum_{t=0}^{m-1} 2^t = \frac{1

  3. 2^m}{1

  4. 2} = 2^m

  5. 1$$

  6. 渐近阶数紧确放缩: 由于 \(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)\)$
  7. 选项逐项辨析:
  8. A 项错误:仅计算了外层循环的迭代轮数 \(\log_2 n\),完全遗漏了内层循环的开销。
  9. B 项正确:等比级数累加和受最高次项主导,整体呈线性阶 \(O(n)\)。
  10. C 项错误:这是极具迷惑性的典型错误选项!考生往往盲目使用乘法法则:误认为“外层执行 \(\log_2 n\)$ \text{次,内层最大执行} $\(n\)$ \text{次,故总时间为} $\(O(n \log_2 n)\)”。乘法法则仅在内外层相互独立时成立,此处内层上限严格受控于外层变量,必须使用级数求和。
  11. D 项错误:高估了内层与外层的增长规模。

正确答案:B


【真题 3】2019 年 408 第 1 题 · 非线性开方条件的单重循环

题目
设 n 是描述问题规模的非负整数,下列程序段的时间复杂度是( )。

x = 0;
while (n >= (x + 1) * (x + 1))
    x = x + 1;
A. \(O(\log n)\)          B. \(O(n^{1/2})\)          C. \(O(n)\)          D. \(O(n^2)\)

【解析】

  1. 设参换元建立状态方程: 设该 while 循环体共执行了 \(k\) 次。
  2. 初始状态(第 0 次):\(x_0 = 0\);
  3. 第 1 次执行后:\(x_1 = 1\);
  4. 第 2 次执行后:\(x_2 = 2\);
  5. \(\dots\)
  6. 第 \(k\)$ \text{次执行后:} $\(x_k = k\)。
  7. 临界终止条件判定: 循环继续的条件是 \(n \ge (x + 1)^2\)。 循环终止于第 \(k\) 次执行完毕后,控制条件首次不成立,即: $\((x_k + 1)^2 > n \iff (k + 1)^2 > n\)$ 同时在第 \(k-1\) 次时条件依然满足: $\(k^2 \le n\)$
  8. 求解执行次数 \(k\): 对不等式开平方: $\(\sqrt{n} - 1 < k \le \sqrt{n}\)$ 故循环执行次数为: $\(k = \lfloor \sqrt{n} \rfloor = \Theta(\sqrt{n}) = O(n^{1/2})\)$
  9. 选项逐项辨析:
  10. A 项错误:对数阶通常对应乘除倍增步长,此处 \(x\) 仅为线性递增,但因平方判断导致循环次数落在根号量级。
  11. B 项正确:\(k \approx \sqrt{n} = n^{1/2}\)。
  12. C 项及 D 项错误:均严重高估了循环执行的频度。

正确答案:B


【真题 4】2017 年 408 第 1 题 · 累加和边界判定的单重循环

题目
下列函数的时间复杂度是( )。

int func(int n) {
    int i = 0, sum = 0;
    while (sum < n)
        sum += ++i;
    return i;
}
A. \(O(\log_2 n)\)          B. \(O(n^{1/2})\)          C. \(O(n)\)          D. \(O(n \log_2 n)\)

【解析】

  1. 设参换元与离散状态追踪: 设该循环体共迭代执行了 \(k\) 次。 注意语句 sum += ++i; 的执行语义:变量 \(i\) 先自增 1,随后累加到 sum 中。
  2. 初始状态:\(i = 0, sum = 0\);
  3. 第 1 次迭代:\(i = 1, sum = 0 + 1 = 1\);
  4. 第 2 次迭代:\(i = 2, sum = 1 + 2 = 3\);
  5. 第 3 次迭代:\(i = 3, sum = 1 + 2 + 3 = 6\);
  6. \(\dots\)
  7. 第 \(k\)$ \text{次迭代:} $\(i = k, sum = \sum_{m=1}^k m = \frac{k(k + 1)}{2}\)。
  8. 临界终止不等式建立: 循环退出当且仅当 sum >= n,即: $\(\frac{k(k + 1)}{2} \ge n \iff k^2 + k - 2n \ge 0\)$
  9. 求解执行次数 \(k\) 的渐近阶: 求解一元二次方程正根: $\(k = \frac{-1 + \sqrt{1 + 8n}}{2} = \sqrt{2n + \frac{1}{4}} - \frac{1}{2} = \Theta(\sqrt{n}) = O(n^{1/2})\)$
  10. 选项逐项辨析:
  11. A 项错误:sum 呈二次方级数增长而非指数增长,故执行步数开平方而非取对数。
  12. B 项正确:渐近复杂度为 \(O(n^{1/2})\)。
  13. 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)\)

【解析】

  1. 拓扑排序算法标准执行流程分解(Kahn 算法):
  2. 阶段一:入度统计
    为了获取所有顶点的初始入度,算法需要扫描邻接表中所有顶点引出的所有边链表节点。全图共有 \(e\)$ \text{条弧,因此扫描全部弧节点的操作耗时为} $\(O(e)\)$ \text{。初始化数组耗时} $\(O(n)\)$ \text{,该阶段总耗时为} $\(O(n + e)\)。
  3. 阶段二:零入度顶点初始化
    遍历所有顶点入度数组,将入度为 0 的顶点压入辅助栈(或队列)。共有 \(n\)$ \text{个顶点,耗时为} $\(O(n)\)。
  4. 阶段三:主循环拓扑输出及弧删除
    • 每次从栈顶弹出一个顶点并输出:所有顶点最多入栈和出栈各 1 次,顶点处理的总耗时为 \(O(n)\);
    • 遍历该顶点的出边链表,将对应终点的入度减 1:全过程中,每条弧恰好被遍历一次,入度扣减操作累计执行 \(e\)$ \text{次,该部分总耗时为} $\(O(e)\)。
  5. 总时间复杂度综合推导: 应用渐近加法法则,合并三个阶段的耗时: $\(T(n, e) = O(n + e) + O(n) + O(n + e) = O(n + e)\)$
  6. 选项逐项辨析:
  7. A 项错误:遗漏了遍历邻接边表以更新终点入度的开销 \(O(e)\)。
  8. B 项正确:邻接表存储下,拓扑排序的时间复杂度为 \(O(n + e)\)。
  9. C 项错误:\(O(n^2)\)$ \text{是基于“邻接矩阵”存储时的拓扑排序时间复杂度。在邻接矩阵中,查找零入度顶点与查找出边均需扫描矩阵的整行或整列,耗时} $\(O(n^2)\)。
  10. D 项错误:各顶点的边链表总长度为 \(e\)$ \text{而非} $\(n \cdot e\)$ \text{,不存在对每条边重复扫描} $\(n\) 次的操作。

正确答案:B


四、 核心解题套路及易错陷阱

1. 嵌套循环的“直觉相乘”陷阱(乘法法则盲目套用)

  • 陷阱表象: 在分析形如下列代码的双重循环时:
    for (int i = 1; i < n; i *= 2)
        for (int j = 0; j < i; j++)
            // 基本操作
    
    考生极易产生直觉误区:“外层循环 \(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)\)。

五、 考点速记清单

  1. 渐近阶次序列: $\(O(1) < O(\log_2 n) < O(\sqrt{n}) < O(n) < O(n \log_2 n) < O(n^2) < O(2^n) < O(n!)\)$
  2. 两类经典循环特征:
  3. 等差累加型(sum += i 或 \(i \times i < n\)$ \text{):变量呈二次方演变,循环次数必为开方阶} $\(O(\sqrt{n}) = O(n^{1/2})\)。
  4. 外倍增内依赖型(外层 \(i *= 2\)$ \text{,内层} $\(j < i\)$ \text{):等比级数累加,公比} $\(q=2\)$ \text{,总和由末项主导,复杂度恒为线性阶} $\(O(n)\)。
  5. 主定理三步速判(比较 \(f(n)\)$ \text{与} $\(n^{\log_b a}\)):
  6. \(f(n)\)$ \text{多项式小于临界项} $\(\implies T(n) = \Theta(n^{\log_b a})\);
  7. \(f(n)\)$ \text{与临界项同阶} $\(\implies T(n) = \Theta(n^{\log_b a} \log n)\);
  8. \(f(n)\)$ \text{多项式大于临界项} $\(\implies T(n) = \Theta(f(n))\)。
  9. 空间复杂度准则:
  10. 原地工作:辅助空间 \(S(n) = O(1)\)(允许常数个辅助变量,非零存储)。
  11. 递归开销:空间复杂度取决于递归调用树的最大调用深度(树高)。