408

数据结构

DS-01-03 时间复杂度与空间复杂度分析

---

一、定位信息

项目	内容
所属圈层	核心层
前置知识回顾	需先掌握DS-01-02中算法的定义、五大特性、效率度量方法及语句频度的基本概念。此外，需要了解对数的基本运算性质（$\log_2 n$ 的含义、对数函数的增长特征）
知识网络定位	本单元是第一章的核心考点，也是贯穿整个数据结构课程的分析工具。后续每个章节的具体算法（排序、查找、图算法等）都需要用时间/空间复杂度来衡量优劣
考点热度等级	H级（高频重点）——几乎每年必考，选择题2~4分，综合题中也经常需要分析算法复杂度，累计分值可达5~8分

热度说明：基于大纲权重与通用命题规律推测，待真题分析后校准。

---

二、知识点讲解

2.1 时间复杂度的定义

时间复杂度是衡量算法执行时间随问题规模 $n$ 增长趋势的度量。

设算法中所有语句的执行次数之和为 $T(n)$，则 $T(n)$ 是问题规模 $n$ 的函数。我们关注的不是 $T(n)$ 的精确值，而是当 $n \to \infty$ 时 $T(n)$ 的增长趋势（即增长率/阶数）。

为什么不需要精确值？ 因为精确值依赖于硬件、编译器等外部因素（见DS-01-02），而增长趋势只取决于算法策略本身，具有普适性。

2.2 大O记号（Big-O Notation）

定义：若存在正常数 $c$ 和 $n_0$，使得当 $n \geq n_0$ 时，有 $T(n) \leq c \cdot g(n)$，则记 $T(n) = O(g(n))$。

大O记号表示的是 $T(n)$ 的上界（最坏情况下的增长率）。

求大O记号的规则：

1. 保留最高阶项：$T(n) = 3n^2 + 5n + 100 = O(n^2)$
2. 去掉最高阶项的常数系数：$T(n) = 5n^3 = O(n^3)$
3. 加法规则：$O(f(n)) + O(g(n)) = O(\max\{f(n), g(n)\})$
4. 乘法规则：$O(f(n)) \cdot O(g(n)) = O(f(n) \cdot g(n))$

2.3 常见时间复杂度及其大小关系

从低到高排列：

$O(1) < O(\log_2 n) < O(n) < O(n \log_2 n) < O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n)$

复杂度	名称	典型算法示例
$O(1)$	常数阶	直接访问数组元素、交换两个变量
$O(\log_2 n)$	对数阶	折半查找（二分查找）
$O(n)$	线性阶	遍历数组、顺序查找
$O(n \log_2 n)$	线性对数阶	快速排序（平均情况）、归并排序、堆排序
$O(n^2)$	平方阶	冒泡排序、选择排序、插入排序（最坏情况）
$O(n^3)$	立方阶	普通矩阵乘法、Floyd最短路径
$O(2^n)$	指数阶	穷举所有子集
$O(n!)$	阶乘阶	穷举所有排列

【图示说明】：此处应展示一个坐标图，横轴为 $n$，纵轴为 $T(n)$。图中用不同颜色的曲线展示 $O(1)$（水平线）、$O(\log n)$（缓慢上升）、$O(n)$（直线）、$O(n^2)$（抛物线）、$O(2^n)$（急剧上升）的增长趋势。可以看出，当 $n$ 较大时，高阶复杂度的算法耗时远超低阶复杂度。

2.4 最好、最坏与平均时间复杂度

概念	定义	意义
最好时间复杂度 $T_{best}(n)$	在最优输入下，算法的最少执行次数	反映算法的最佳情况，实际参考价值有限
最坏时间复杂度 $T_{worst}(n)$	在最差输入下，算法的最多执行次数	实际中最重要的指标，保证算法不会比这更差
平均时间复杂度 $T_{avg}(n)$	所有可能输入下执行次数的加权平均	理论上最合理，但计算困难

408考试惯例：除非特别说明，"时间复杂度"一般指最坏时间复杂度。

2.5 分析时间复杂度的方法

方法一：直接计算语句频度

逐条统计每条语句的执行次数，求总和后取最高阶项。

// 示例：计算1+2+...+n
int sum = 0;              // 语句①：执行1次
for (int i = 1; i <= n; i++) {  // 语句②：执行n+1次
    sum += i;             // 语句③：执行n次
}
// T(n) = 1 + (n+1) + n = 2n + 2 = O(n)

方法二：递推法（适用于递归算法）

建立递推方程，求解 $T(n)$。

// 示例：递归求阶乘
int factorial(int n) {
    if (n <= 1) return 1;    // 基本情况：O(1)
    return n * factorial(n-1); // 递归：T(n) = T(n-1) + O(1)
}
// T(n) = T(n-1) + 1, T(1) = 1
// 解得 T(n) = n = O(n)

方法三：均摊分析（Amortized Analysis）

适用于某些操作偶尔很慢但整体平均较快的情况。408范围内较少直接考查，但理解有助于分析动态数组等结构。

2.6 常见递推方程与解

递推方程	解	对应算法示例
$T(n) = T(n-1) + O(1)$	$O(n)$	递归遍历数组
$T(n) = T(n/2) + O(1)$	$O(\log n)$	折半查找
$T(n) = 2T(n/2) + O(n)$	$O(n \log n)$	归并排序
$T(n) = 2T(n/2) + O(1)$	$O(n)$	二叉树遍历
$T(n) = T(n-1) + O(n)$	$O(n^2)$	冒泡排序（递归版）

2.7 空间复杂度

空间复杂度是衡量算法所需额外存储空间随问题规模 $n$ 增长趋势的度量，记为 $S(n)$。

$S(n) = O(g(n))$

空间复杂度关注的是辅助空间（额外开辟的空间），不包括输入数据本身占用的空间。

空间复杂度	典型算法示例
$O(1)$	冒泡排序、插入排序、选择排序（原地排序算法）
$O(\log n)$	快速排序（递归栈空间，平均情况）
$O(n)$	归并排序（需要辅助数组）、计数排序
$O(n^2)$	存储 $n \times n$ 矩阵

关键区分：原地排序算法的空间复杂度为 $O(1)$，因为只需要常数个额外变量；归并排序需要 $O(n)$ 的辅助数组，不是原地排序。

2.8 加法规则与乘法规则的直觉理解

• 加法规则（顺序结构）：多个顺序执行的代码段，总复杂度取最大值。直觉：先做A再做B，总时间 = A的时间 + B的时间，取较大的那个代表增长趋势。

$O(n) + O(n^2) = O(n^2)$

• 乘法规则（嵌套结构）：嵌套循环的复杂度等于各层复杂度的乘积。直觉：外层执行 $n$ 次，每次内层执行 $n$ 次，总共 $n \times n$ 次。

$O(n) \cdot O(n) = O(n^2)$

---

三、记忆与理解辅助

技巧1：常见复杂度排序口诀

"常对线线方立指阶"——$O(1)$、$O(\log n)$、$O(n)$、$O(n\log n)$、$O(n^2)$、$O(n^3)$、$O(2^n)$、$O(n!)$

或用谐音记为：

"一对情侣两立方，指数阶乘排排站"

技巧2：循环层数与复杂度对应表

循环嵌套层数	典型复杂度	示例
单层循环 $i=1$ 到 $n$	$O(n)$	遍历数组
双层嵌套循环，各 $1$ 到 $n$	$O(n^2)$	冒泡排序的内层
三层嵌套循环，各 $1$ 到 $n$	$O(n^3)$	普通矩阵乘法
单层循环，每次 $i$ 翻倍	$O(\log n)$	折半查找
双层循环，外层 $1$ 到 $n$，内层每次翻倍	$O(n \log n)$	类似归并排序的分治结构

注意：以上是简化对应关系，实际分析时必须具体问题具体分析，不能机械套用。

技巧3：三种复杂度对比表

维度	最好情况	最坏情况	平均情况
定义	最优输入下的执行次数	最差输入下的执行次数	所有输入的加权平均
实用性	参考价值低	最重要	理论最合理但难计算
408考查	偶尔考查	重点考查	偶尔考查
示例（顺序查找）	$O(1)$（第一个就找到）	$O(n)$（最后一个或找不到）	$O(n/2) = O(n)$

技巧4：大O记号的本质

大O记号只关心增长趋势，不关心常数因子和低阶项。所以 $O(5n^2 + 100n + 1000)$ 就是 $O(n^2)$——当 $n$ 足够大时，$n^2$ 项完全"碾压"其他项。

---

四、例题与精解

例题1（基础）

题目：求以下算法的时间复杂度。

void fun(int n) {
    int i, j;
    for (i = 1; i <= n; i++)       // 外层循环
        for (j = 1; j <= i; j++)   // 内层循环
            printf("*");            // 基本操作
}

命题意图：考查嵌套循环的时间复杂度分析能力。

解答：

审题分析：外层循环变量 $i$ 从1到 $n$，内层循环变量 $j$ 从1到 $i$，需要统计 printf 的总执行次数。

解题思路：基本操作 printf 的执行次数 = 外层每次循环时内层的执行次数之和。

完整步骤：

• 当 $i=1$ 时，内层执行1次
• 当 $i=2$ 时，内层执行2次
• ...
• 当 $i=n$ 时，内层执行 $n$ 次

总执行次数：

$T(n) = \sum_{i=1}^{n} i = \frac{n(n+1)}{2} = \frac{n^2}{2} + \frac{n}{2}$

取最高阶项并去掉常数系数：

$T(n) = O(n^2)$

方法反思：当内层循环的范围依赖于外层循环变量时（j <= i），需要求和。记住常见求和公式：$\sum_{i=1}^{n} i = \frac{n(n+1)}{2} = O(n^2)$。

---

例题2（中等）

题目：求以下算法的时间复杂度。

void fun(int n) {
    int i = 0, s = 0;
    while (s < n) {
        i++;
        s = s + i;
    }
}

命题意图：考查非标准循环（循环变量不直接以1递增）的时间复杂度分析能力。

解答：

审题分析：循环变量 $s$ 不是每次加1，而是累加 $1+2+3+\cdots$，需要找出循环终止的条件。

解题思路：追踪 $s$ 的变化规律，找到循环终止时 $i$ 与 $n$ 的关系。

完整步骤：

• 初始：$i = 0, s = 0$
• 第1次循环后：$i = 1, s = 1$
• 第2次循环后：$i = 2, s = 3$
• 第3次循环后：$i = 3, s = 6$
• ...
• 第 $k$ 次循环后：$i = k, s = 1 + 2 + \cdots + k = \frac{k(k+1)}{2}$

循环终止条件为 $s \geq n$，即：

$\frac{k(k+1)}{2} \geq n$

$k^2 + k \geq 2n$

当 $n$ 较大时，$k^2 \approx 2n$，所以 $k \approx \sqrt{2n} = O(\sqrt{n})$。

循环体执行了 $k = O(\sqrt{n})$ 次。

$T(n) = O(\sqrt{n})$

方法反思：当循环变量不是简单地每次加1时，需要分析循环变量的累积规律，建立方程求解循环次数与 $n$ 的关系。本题的关键是识别出 $s$ 是前 $k$ 个自然数之和。

---

五、考情分析

分析维度	说明
近5年考查频次	几乎每年必考，5年内出现≥4次
常见题型	选择题（给代码求复杂度）、综合题（分析所设计算法的复杂度）
分值占比	选择题2~4分；综合题中分析复杂度部分约占3~5分
命题趋势	近年命题难度有所提升：①从简单的循环嵌套分析转向递归算法的复杂度分析；②从单纯的求复杂度转向结合具体算法（如排序、查找）考查；③偶尔考查最好/最坏/平均情况的区分

基于大纲与命题规律推测，待真题分析后校准。

---

六、易错点提醒

易错点1

• 错误表现：分析嵌套循环时，将内层循环次数误算为 $n$ 次（当内层依赖外层变量时）
• 错误原因：看到 for (j = 1; j <= i; ...) 就直接认为内层执行 $n$ 次，忽略了 $j$ 的上限 $i$ 是变化的
• 正确做法：内层循环次数依赖于外层变量时，必须逐层求和。例如外层 $i$ 从1到 $n$，内层 $j$ 从1到 $i$，总次数为 $\sum_{i=1}^{n} i = O(n^2)$，而非 $n \times n = O(n^2)$（虽然结果碰巧一样，但当内层为 $j$ 从1到 $i^2$ 时，结果就不同了）

易错点2

• 错误表现：将递归算法的时间复杂度简单地等同于递归深度
• 错误原因：忽略了每次递归调用中除了递归本身外还有其他操作
• 正确做法：递归算法的时间复杂度 = 递归次数 × 每次递归中的工作量。例如归并排序：$T(n) = 2T(n/2) + O(n)$，其中 $O(n)$ 是合并操作的工作量，不能忽略

易错点3

• 错误表现：将空间复杂度等同于所有变量占用的空间
• 错误原因：没有区分"输入数据占用的空间"和"辅助空间"
• 正确做法：空间复杂度只计算辅助空间（算法执行过程中额外开辟的空间），不包括输入数据本身。例如，冒泡排序虽然操作了 $n$ 个元素，但只用了 $O(1)$ 的辅助空间

易错点4

• 错误表现：认为 $O(n \log n)$ 比 $O(n^2)$ 快，所以所有情况下归并排序都比冒泡排序快
• 错误原因：将时间复杂度的比较绝对化
• 正确做法：时间复杂度描述的是 $n$ 趋于无穷大时的增长趋势。当 $n$ 很小时，高阶算法可能比低阶算法快（因为常数因子的影响）。但在408考试中，通常假设 $n$ 足够大，直接按阶数比较即可

易错点5

• 错误表现：混淆 $O(\log n)$ 中的对数底数
• 错误原因：不确定是 $\log_2 n$、$\log_{10} n$ 还是 $\ln n$
• 正确做法：在大O记号中，不同底数的对数只差一个常数倍（$\log_a n = \frac{\log_b n}{\log_b a}$），所以 $O(\log_2 n) = O(\log_{10} n) = O(\ln n)$，底数可以省略不写，统一写 $O(\log n)$

---

七、来源标注

• 依据2026考研统考大纲（408计算机学科专业基础综合·数据结构部分）
• 依据《数据结构（C语言版）》严蔚敏版第一章算法时间复杂度与空间复杂度分析
• 依据《算法导论》（CLRS）第三章函数的增长
• 依据大学本科经典教材共识