复杂度分析¶

方法速览¶

任务	方法	口诀
代码段复杂度	数循环层次：乘法套乘法、内外相乘	层层相乘
循环变量翻倍/减半	单层是 \(O(\log n)\)	变量翻倍取对数
递归式	画递归树逐层求和，看顶层是否支配	逐层求和
找最大值下界	每个数都要输一次 → \(n-1\) 次比较	打擂台
同时找 max/min	两两结对：\(\lceil 3n/2\rceil - 2\)	结对省比较
Dijkstra 无堆版	每轮扫全部点找最小 + 松弛：\(\Theta(n^2)\)	无堆平方

渐近记号¶

记号	含义	类比
\(O(f)\)	上界：不超过 f 的常数倍	\(\le\)
\(\Omega(f)\)	下界	\(\ge\)
\(\Theta(f)\)	紧界（既是上界又是下界）	\(=\)

比较排序 \(O(n\log n)\) 是下界（\(\Omega\)）也是可达上界。

代码段与循环分析¶

【例】（2022 真题）

for (i = 0; i < n; i++) {
    for (j = 0; j < n; j *= 2) {
        k = k + n / 2;
    }
}

内层每次 j *= 2：从 1 到 n 翻倍 \(\log n\) 次；外层 n 次 → \(O(n\log n)\)。（考场上按“内层每次翻倍即对数”分析；若 j 真从 0 起步乘 2 恒为 0 则死循环——试卷默认按 j 从 1 计。）

常用循环对照：

循环形态	复杂度
`for i in 1..n`	\(O(n)\)
`i *= 2` / `i /= 2` 到 n	\(O(\log n)\)
`for i { for j in i..n }`	\(O(n^2)\)（等差级数和）
`for i { for j <= i * ... }` 每轮 i 次	\(O(n^2)\)
`i++ 且 j = n - i` 型收敛	看总量求和

递归式与递归树¶

【例】（2023 真题）quick_power 写成两次递归 quick_power(x, n/2) * quick_power(x, n/2)：

层	调用数	每次代价
0	1	\(O(1)\)
1	2	\(O(1)\)
…	\(2^k\)	\(O(1)\)

递归树共 \(\log n\) 层、结点总数 \(1+2+4+\cdots+2^{\log n} = 2n - 1\) → \(O(n)\)。同样的幂运算，一次递归 + 平方是 \(O(\log n)\)、两次递归是 \(O(n)\)——递归树一画就分明。

比较次数的下界¶

找最大值：每个非冠军都要至少输一场，n 个数 n−1 个非冠军 → 最坏 \(n - 1\) 次比较（打擂台恰好达到）。

同时找 max 与 min（2021 真题）：先两两结对（组内 \(\frac n2\) 次），大者只跟 max 比、小者只跟 min 比（各 \(\frac n2 - 1\) 次）：

\[\frac n2 + 2\left(\frac n2 - 1\right) = \frac{3n}2 - 2\]

两有序数组合并（2019 真题）：各长 n，最坏交错到底，最后一个元素免比较：\(2n - 1\)。

图算法复杂度速查¶

算法	复杂度	备注
Dijkstra（无堆）	\(\Theta(n^2)\)	每轮线性扫找最小点
Dijkstra（堆）	\(O((n+m)\log n)\)
Floyd	\(\Theta(n^3)\)	三重循环
Prim（邻接矩阵）	\(\Theta(n^2)\)
Kruskal	\(O(m\log m)\)	排序支配
DFS/BFS（邻接表）	\(\Theta(n+m)\)

稀疏图选型（2023 真题）：\(m = \Theta(n)\) 时代入每个选项比阶，\(O(m\sqrt{\log n\log\log n})\) 最小。

练习题目¶

练习 1 · 单层循环¶

题目

for (i = 0; i < n; i++) 的复杂度是（）

A. \(O(1)\)
B. \(O(\log n)\)
C. \(O(n)\)
D. \(O(n^2)\)

答案与解析

答案：C

执行 n 次。

练习 2 · 翻倍循环¶

题目

for (i = 1; i < n; i *= 2) 的复杂度是（）

A. \(O(n)\)
B. \(O(\sqrt n)\)
C. \(O(n\log n)\)
D. \(O(\log n)\)

答案与解析

答案：D

1、2、4、…、n 共 \(\log_2 n + 1\) 次——变量翻倍/减半都是对数。

练习 3 · 双层全循环¶

题目

两层嵌套 for i in 1..n { for j in 1..n } 的复杂度是（）

A. \(O(n^2)\)
B. \(O(n\log n)\)
C. \(O(n)\)
D. \(O(2^n)\)

答案与解析

答案：A

外层 n × 内层 n。

练习 4 · 内层依赖外层¶

题目

for i in 1..n { for j in 1..i } 的复杂度是（）

A. \(O(n)\)
B. \(O(n\log n)\)
C. \(O(n^2)\)
D. \(O(n\sqrt n)\)

答案与解析

答案：C

总次数 \(1+2+\cdots+n = \frac{n(n+1)}2\)——求和后看阶仍是平方。

练习 5 · 混合循环¶

题目

for i in 1..n { for j in 1..n step j*=2 } 的复杂度是（）

A. \(O(n^2)\)
B. \(O(n\log n)\)
C. \(O(\log^2 n)\)
D. \(O(n)\)

答案与解析

答案：B

外层 n × 内层 \(\log n\)——2022 真题的骨架。

练习 6 · 三层循环¶

题目

for i { for j in i..n { for k in j..n } }（均从 1 到 n）的复杂度是（）

A. \(O(n^2)\)
B. \(O(n^3)\)
C. \(O(n^2\log n)\)
D. \(O(n^3\log n)\)

答案与解析

答案：B

三层嵌套、每层至多 n：\(O(n^3)\)——Floyd 的形状。

练习 7 · 找最大值下界¶

题目

n 个数找最大值，最坏至少（）次比较。

A. \(n\)
B. \(\log n\)
C. \(n/2\)
D. \(n - 1\)

答案与解析

答案：D

每个非冠军至少输一场：n−1 场；打擂台恰好 n−1 次。

练习 8 · 同时找 max/min¶

题目

2n 个数同时找最大值和最小值，结对比较法最坏（）次。

A. \(3n - 2\)
B. \(4n - 2\)
C. \(2n - 1\)
D. \(3n + 1\)

答案与解析

答案：A

结内 n 次 + 大者对 max、小者对 min 各 \(n-1\) 次：\(3n - 2\)。

练习 9 · 归并比较¶

题目

长度分别为 n 与 m 的有序数组归并，最坏比较（）次。

A. \(n + m\)
B. \(n + m - 1\)
C. \(\min(n,m)\)
D. \(nm\)

答案与解析

答案：B

每比较归位一个、最后剩一个免比：\(n+m-1\)；两数组各 n 时即 \(2n-1\)。

练习 10 · 二分比较¶

题目

有序数组二分查找的复杂度（）

A. \(O(\log n)\)
B. \(O(1)\)
C. \(O(n)\)
D. \(O(n\log n)\)

答案与解析

答案：A

每次砍半。

练习 11 · 快速幂（一次递归）¶

题目

pow(x, n) = pow(x, n/2) 平方（一次递归调用） 的复杂度（）

A. \(O(1)\)
B. \(O(n)\)
C. \(O(\log n)\)
D. \(O(n/\log n)\)

答案与解析

答案：C

n 减半 \(\log n\) 层、每层 \(O(1)\)。

练习 12 · 快速幂（两次递归）¶

题目

pow(x, n) = pow(x, n/2) * pow(x, n/2) 的复杂度（）

A. \(O(\log n)\)
B. \(O(n)\)
C. \(O(n\log n)\)
D. \(O(\log^2 n)\)

答案与解析

答案：B

递归树结点 \(1+2+\cdots+2^{\log n} = 2n-1\)——2023 真题陷阱。

练习 13 · 递归式求和¶

题目

\(T(n) = T(n/2) + O(1)\) 的解是（）

A. \(O(1)\)
B. \(O(n)\)
C. \(O(\log n)\)
D. \(O(\sqrt n)\)

答案与解析

答案：C

\(\log n\) 层、每层常数。

练习 14 · 递归式（三叉分治）¶

题目

\(T(n) = 3T(n/3) + O(n)\) 的解是（）

A. \(O(n)\)
B. \(O(n\log n)\)
C. \(O(n^2)\)
D. \(O(n\log^2 n)\)

答案与解析

答案：B

每层 3 个 \(\frac n3\) 子问题、合并 \(O(n)\)——每层总量恒为 \(n\)、共 \(\log_3 n\) 层。

练习 15 · Dijkstra 无堆¶

题目

不用堆的 Dijkstra 复杂度是（）

A. \(\Theta(n^2)\)
B. \(\Theta((n+m)\log n)\)
C. \(\Theta(n^3)\)
D. \(\Theta(m\log n)\)

答案与解析

答案：A

n 轮、每轮线性扫所有点找未确定最小点并松弛。

练习 16 · Floyd¶

题目

Floyd 全源最短路复杂度（）

A. \(O(n^2)\)
B. \(O(nm)\)
C. \(O(n^2\log n)\)
D. \(O(n^3)\)

答案与解析

答案：D

三重循环 k、i、j 各 n。

练习 17 · Kruskal¶

题目

Kruskal 的复杂度（）

A. \(O(m\log m)\)
B. \(O(n^2)\)
C. \(O(m\alpha(n))\)
D. \(O(n^3)\)

答案与解析

答案：A

排序边 \(O(m\log m)\) 支配，并查集几乎线性。

练习 18 · 稀疏图选型¶

题目

\(m = \Theta(n)\) 时，\(O(n^2)\) 与 \(O(m + n\log n)\) 的算法应选（）

A. 前者
B. 任意
C. 都不可用
D. 后者

答案与解析

答案：D

\(m = n\) 时代入：后者 \(n\log n\) 完胜 \(n^2\)。

练习 19 · Θ 的含义¶

题目

\(T(n) = \Theta(f(n))\) 表示（）

A. \(T\) 不超过 f 的常数倍
B. \(T\) 与 f 同阶（上下界都夹住）
C. \(T \ge f\)
D. \(T = f\)

答案与解析

答案：B

\(O\) 是上界、\(\Omega\) 是下界、\(\Theta\) 是紧界。

练习 20 · 常数被忽略¶

题目

\(O(2n)\) 与 \(O(n)\) 的关系（）

A. 不同
B. 相同（常数因子忽略）
C. 前者大
D. 无法比较

答案与解析

答案：B

渐近记号只看增长阶。

练习 21 · 加法规则¶

题目

一段 \(O(n^2)\) 的代码接一段 \(O(n\log n)\) 的代码，总复杂度（）

A. \(O(n^2\cdot n\log n)\)
B. \(O(n^3)\)
C. \(O(n\log n)\)
D. \(O(n^2 + n\log n) = O(n^2)\)

答案与解析

答案：D

顺序执行取最大项；相乘是嵌套的规则。

练习 22 · 嵌套 vs 顺序¶

题目

外层 \(O(n)\) 嵌套内层 \(O(n)\)，与两段各 \(O(n)\) 顺序执行，分别为（）

A. \(O(n^2)\) 与 \(O(n)\)
B. 都 \(O(n^2)\)
C. 都 \(O(n)\)
D. \(O(n)\) 与 \(O(n^2)\)

答案与解析

答案：A

嵌套相乘、顺序取大。

练习 23 · 逆序输出递归¶

题目

递归打印 n 个元素（先递归后打印），复杂度（）

A. \(O(n\log n)\)
B. \(O(\log n)\)
C. \(O(n)\)
D. \(O(n^2)\)

答案与解析

答案：C

每个元素访问一次。

练习 24 · 主定理直观¶

题目

\(T(n) = 2T(n/2) + O(n)\) 对应的经典算法是（）

A. 二分查找
B. 快速幂
C. 归并排序
D. 汉诺塔

答案与解析

答案：C

分半 + 线性合并 = \(O(n\log n)\)；A 是单分支 \(T(n/2)+O(1)\)。

练习 25 · 数据范围反推¶

题目

\(n \le 10^6\)、时限 1 秒（约 \(10^8\) 运算），可接受的复杂度是（）

A. \(O(n^2)\)
B. \(O(n\log n)\)
C. \(O(2^n)\)
D. \(O(n^3)\)

答案与解析

答案：B

\(n\log n \approx 2\times10^7\) ✓；\(n^2 = 10^{12}\) ✗。

练习 26 · 循环变量减半¶

题目

while (n > 0) { n = n / 3; } 的循环次数是（）

A. \(\log_2 n\)
B. \(\log_3 n\)
C. \(n/3\)
D. \(3n\)

答案与解析

答案：B

每次÷3 → 底数为 3 的对数；无论底数多少都是 \(O(\log n)\)。

历年真题¶

2019 年 · 第 11 题¶

题目

设 \(A\) 和 \(B\) 是两个长度为 \(n\) 的有序数组，现在需要将 \(A\) 和 \(B\) 合并成一个排序好的数组。请问任何以元素比较作为基本运算的归并算法，在最坏情况下至少要做多少次比较？（）

A. \(n^2\)
B. \(n\log n\)
C. \(2n-1\)
D. \(2n\)

答案与解析

答案：C

最坏交错到底：前 \(2n-1\) 个位置各需一次比较，最后一个免比。

2020 年 · 第 14 题¶

题目

对一个 \(n\) 个顶点、\(m\) 条边的带权有向简单图用 Dijkstra 算法计算单源最短路时，如果不使用堆或其它优先队列进行优化，则其时间复杂度为（）。

A. \(\Theta((m+n^2)\log n)\)
B. \(\Theta(mn+n^3)\)
C. \(\Theta((m+n)\log n)\)
D. \(\Theta(n^2)\)

答案与解析

答案：D

无堆版每轮线性扫找最小：\(n\) 轮 \(\times\) \(O(n)\) = \(\Theta(n^2)\)。

2021 年 · 第 5 题¶

题目

以比较为基本运算，对于 \(2n\) 个数，同时找到最大值和最小值，最坏情况下需要的最少比较次数为（）。

A. \(4n-2\)
B. \(3n+1\)
C. \(3n-2\)
D. \(2n+1\)

答案与解析

答案：C

两两结对：结内 \(n\) 次 + 大者对 max、小者对 min 各 \(n-1\) 次 = \(3n-2\)（推导见教学节）。

2022 年 · 第 13 题¶

题目

对于给定的 \(n\)，分析以下代码段对应的时间复杂度，其中最为准确的时间复杂度为（）。

int i, j, k = 0;
for (i = 0; i < n; i++) {
    for (j = 0; j < n; j *= 2) {
        k = k + n / 2;
    }
}

A. \(O(n)\)
B. \(O(n\log n)\)
C. \(O(n\sqrt{n})\)
D. \(O(n^2)\)

答案与解析

答案：B

内层翻倍 \(\log n\) 次 × 外层 \(n\) 次。（注：j 严格从 0 起乘 2 恒为 0，卷面按内层对数循环的意图分析。）

2022 年 · 第 14 题¶

题目

以比较为基本运算，在 \(n\) 个数的数组中找最大的数，在最坏情况下至少要做（）次运算。

A. \(\frac{n}{2}\)
B. \(n-1\)
C. \(n\)
D. \(n+1\)

答案与解析

答案：B

非冠军都要输一场：\(n-1\)（打擂台达到下界）。

2023 年 · 第 15 题¶

题目

现在用如下代码来计算 \(x^n\)，其时间复杂度为（）。

double quick_power(double x, unsigned n) {
    if (n == 0) return 1;
    if (n == 1) return x;
    return quick_power(x, n / 2)
        * quick_power(x, n / 2)
        * ((n & 1) ? x : 1);
}

A. \(O(n)\)
B. \(O(1)\)
C. \(O(\log n)\)
D. \(O(n\log n)\)

答案与解析

答案：A

两次递归调用使递归树结点 \(2n-1\) 个——\(O(n)\)；只写一次递归（平方复用）才是 \(O(\log n)\)。

2024 年 · 第 2 题¶

题目

假设一个长度为 \(n\) 的整数数组中每个元素值互不相同，且这个数组是无序的。要找到这个数组中最大元素的时间复杂度是多少？（）

A. \(O(n)\)
B. \(O(\log n)\)
C. \(O(n \log n)\)
D. \(O(1)\)

答案与解析

答案：A

无序必须逐个看：\(O(n)\)。

2025 年 · 第 11 题¶

题目

递归关系式 \(T(n) = 2T(n/2) + O(n^2)\) 描述了某个分治算法的时间复杂度。请问该算法的时间复杂度是多少？

A. \(O(n)\)
B. \(O(n \log n)\)
C. \(O(n^2)\)
D. \(O(n^2 \log n)\)

答案与解析

答案：C

逐层求和 \(n^2(1+\frac12+\frac14+\cdots) < 2n^2\)——几何级数收敛，顶层支配（别急着套 \(n\log n\)，那要合并代价是 \(O(n)\)）。

易错小结¶

循环看变量变化方式：+1 线性、×2/÷2 对数；嵌套相乘、顺序取大；
快速幂“一次递归 \(O(\log n)\)、两次递归 \(O(n)\)”（2023 真题陷阱）；
\(T(n)=2T(n/2)+O(n^2)\) = \(O(n^2)\)（几何收敛），\(+O(n)\) 才是 \(O(n\log n)\)；
找最大 \(n-1\)；同时找 max/min 结对 \(3n-2\)；两长度 n 数组归并 \(2n-1\)；
无堆 Dijkstra \(\Theta(n^2)\)、Floyd \(n^3\)、Kruskal \(m\log m\)、邻接表遍历 \(n+m\)；
稀疏题代入 \(m=\Theta(n)\) 逐项比阶；
数据范围反推：1 秒约 \(10^8\) 次运算。