前言

本文是 408 数据结构的一轮考点强化笔记，依托 BOK408 数据结构强化课（26 版）整理，按「时间复杂度 → 线性结构 → 非线性结构 → 查找 → 排序」五个板块推进。

与按教材章节从头捋一遍的复习不同，这里更强调考点的横向串联与易错点的集中对照：同一个知识点在选择题里怎么设干扰项、在大题里怎么出计算、哪些结论必须能现场推导而不能死记。每一部分都尽量落到「考试怎么考」这一层，便于冲刺阶段快速扫盲补漏。

笔记随课程进度持续补充，新增内容按板块顺序追加到对应章节末尾。

主要内容

本文按以下五个板块组织，各板块覆盖的核心范围如下：

  • 时间复杂度：算法效率的度量方式，大 O / Ω / Θ 记号的差别与用法，常见代码段的复杂度推导，以及递归式的求解。
  • 线性结构：顺序表与链表（单链表、双链表、循环链表、静态链表）的存储方式、基本操作与效率对比；栈、队列与数组（含特殊矩阵的压缩存储）及其典型应用。
  • 非线性结构：树与二叉树（含二叉树的遍历、线索二叉树、树 / 森林的转换与存储），哈夫曼树与并查集；图的基本概念、存储结构、遍历（DFS / BFS）与经典应用（最小生成树、最短路径、拓扑排序、关键路径）。
  • 查找：顺序查找、折半查找、分块查找，二叉排序树、平衡二叉树与红黑树，B 树与 B+ 树，散列表（散列函数、冲突处理与查找效率分析）。
  • 排序：插入排序、希尔排序、交换排序（冒泡、快速）、选择排序（简单选择、堆排序）、归并排序、基数排序，以及各算法的时间 / 空间复杂度、稳定性对比与外部排序。

一、时间复杂度

单层循环是时间复杂度里最基础、也最常考的一类。分析时可以先固化成一个三步流程：

  1. 确定基本运算：找出循环体里被反复执行的那条语句；
  2. 找出变化规律：把与循环次数相关的变量列成表，看它随执行次数 $t$ 怎么变化；
  3. 联系跳出条件：用循环的结束条件把 $t$ 和问题规模 $n$ 联系起来，得到二者的数量级关系。

题型1-单层循环

例题：【2011】

设 $n$ 是描述问题规模的非负整数，下面程序片段的时间复杂度是

x = 2;
while(x < n/2)
    x = 2 * x;

第 1 步，找出基本运算。 x = 2 * x，设其执行次数为 $t$。

第 2 步，列表找规律。 看 $t = 1, 2, 3, \dots$ 时 $x$ 的取值：

执行次数 $t$ $x$ 的取值
1 $2^2 = 4$
2 $2^3 = 8$
3 $2^4 = 16$
⋮ ⋮
$t$ $2^{t+1}$

可见 $x$ 随 $t$ 指数增长，第 $t$ 次执行后 $x = 2^{t+1}$。

第 3 步，列式子。 循环的跳出条件是 $x \ge n/2$，于是在临界处有 $2^{t+1} < n/2$，解得 $t < \log_2 n - 2$——执行次数 $t$ 与 $\log_2 n$ 同数量级，故 $T(n) = O(\log_2 n)$。

注：$2^{t+1} < n/2$ 这个式子其实并不严谨，它假设的是“第 $t$ 轮算出来的 $x$ 仍然小于 $n/2$”。不过研究时间复杂度不需要这么严谨，只要能得到 $t$ 和 $n$ 的数量级关系就够了。

简单方法：联系归并排序——每次都把长为 $n$ 的表除以 2，一共 $k$ 层，直到长度都为 1（$n / 2^k = 1$，即 $k = \log_2 n$）。本题就类似归并操作里的“合并”部分，循环次数自然是 $O(\log_2 n)$。

完整的方法流程要熟练使用：跳出条件往往是 $n$ 和 $x$ 的关系，而 $x$ 和 $t$ 之间的关系可以列表求得，两者一联立就得到 $t$ 和 $n$ 的关系，也就是执行次数与问题规模的关系。

练习：【2017】

下列函数的时间复杂度是

int func(int n){
    int i = 0, sum = 0;
    while(sum < n) sum += ++i;
    return i;
}

这道题的变量不止一个，i 和 sum 都要在表格里列出来（这里 ++i 还是 i++ 都一样）：

执行次数 $t$ $i$ $sum$
1 1 $0 + 1 = 1$
2 2 $1 + 2 = 3$
3 3 $3 + 3 = 6$
4 4 $6 + 4 = 10$
⋮ ⋮ ⋮
$t$ $t$ $1 + 2 + \dots + t = \dfrac{t(t+1)}{2}$

循环的跳出条件是 $sum \ge n$，即 $\dfrac{t(t+1)}{2} \ge n$，也就是 $t \approx \sqrt{2n}$。所以 $T(n) = O(\sqrt n)$。

小结：单层循环怎么分析

单层循环的复杂度分析，本质上只有一句话——数清循环体到底执行了多少次。落到流程上：

  1. 锁定基本运算，设执行次数为 $t$；
  2. 把循环变量的取值随 $t$ 列成表（变量多就都列上），归纳出“第 $t$ 次时它等于什么”；
  3. 代入跳出条件，解出 $t$ 与 $n$ 的关系，取数量级即得时间复杂度。

难点基本都在第 2 步，按变量每次的变化方式分三类：

变量每次的变化 典型写法 $t$ 与 $n$ 的关系 复杂度
乘 / 除一个常数 x = 2 * x $t \approx \log_2 n$ $O(\log n)$
加一个常数 i++ $t \approx n$ $O(n)$
累加自身 sum += ++i $t \approx \sqrt{2n}$ $O(\sqrt n)$

题型2-递归

递归类题目也是看两个量，乘起来就是总时间：

  1. 每次调用执行了多少次基本语句——通常是一个常数，即 $O(1)$；
  2. 一共调用了多少次——也就是递归的调用次数。

$$T(n) = \text{每次调用的基本语句次数} \times \text{调用次数}$$

例题：【2012】

求整数 $n$（$n \ge 0$）阶乘的算法如下，其时间复杂度是

int fact(int n){
    if(n <= 1) return 1;
    return n * fact(n - 1); }
  1. 每次调用执行基本语句的次数：一次比较 + 一次乘法，即 $O(1)$；
  2. 调用次数：每次把 $n$ 减 1，从 $n$ 一路递归到 1，易知调用次数为 $n$；
  3. 相乘：$1 \times n = n$，所以 $T(n) = O(n)$。

通用方法：怎么数递归的调用次数

调用次数本身就是一个递归结构。设 $C(n)$ 表示“执行 $f(n)$ 一共会发生多少次调用（含 $f(n)$ 自己这一次）”，则

$$C(n) = 1 + \sum_i C(n_i)$$

其中 $n_i$ 是每次递归进去的子问题规模，边界取 $C(\text{基例}) = 1$。这个式子数出来的正好是递归调用树的结点总数——所以数调用次数就是数这棵树有多少个结点，关键是两个量：每层有几个结点（由分支数决定）和一共有几层（由规模衰减的速度决定）。

按结构分几类就很清楚了（例子统一取 $n = 8$）：

递归结构 调用次数递推式 调用次数 典型例子（以 $n = 8$ 计）
单分支，规模每次减 1 $C(n) = C(n-1) + 1$ $O(n)$ 阶乘 fact(8) → 8 次
单分支，规模每次减半 $C(n) = C(n/2) + 1$ $O(\log n)$ 折半查找 $8 \to 4 \to 2 \to 1$ → 4 次
双分支，规模减常数 $C(n) = C(n-1) + C(n-2) + 1$ $O(2^n)$ 朴素斐波那契 fib(8) → 67 次
双分支，规模减半 $C(n) = 2C(n/2) + 1$ $O(n)$ 归并排序 $n = 8$ → 15 次

两条要点：

  • 单分支时“调用次数 = 递归深度”：规模每次减 1 → 深度 $n$；规模每次折半 → 深度 $\log_2 n$。
  • 多分支时不能只看深度，还要乘上每层的结点数：斐波那契每减一层就多一个分叉，结点数指数膨胀；归并排序虽然也是两个分支，但规模同时减半，从根往下每层结点数翻倍、层数只有 $\log n$，累计仍是 $O(n)$。

更一般地，凡是能写成 $T(n) = aT(n/b) + f(n)$ 的递归（把“每次调用的基本语句次数”也并进 $f(n)$），都可以直接用主定理定出数量级——这也是大题里推导分治算法复杂度的标准工具。

题型3-for循环嵌套

层层无关

【2014】下列程序段的时间复杂度是

count = 0;
for(k = 1; k <= n; k *= 2)
    for(j = 1; j <= n; j++)
        count++;

直接两层的循环次数相乘。此处 for 的循环条件又可以联系到题型1——这里最外层的 for 就是题型1里那个「类归并合并」的算法，是 $O(\log_2 n)$；内层 for 从 1 累加到 $n$、每次加 1，是 $O(n)$。两层相乘即 $O(n \log n)$。

参考来源