第 1 章 绪论（基本概念与算法分析）
本章地位：绪论是 408 数据结构的「语法说明书」，直接考分不多（选择题 0～2 分），但时间 / 空间复杂度分析是全卷暗线——后面每一章的算法题都要用大 O 说理由。真题最爱考两类：① 逻辑结构与存储结构的辨析（概念题）；② 给一段 C 代码分析时间复杂度（频次法）。本章把这两件事一次讲透，所有复杂度结论都配「逐代具体数值验证」。
1.1 基本概念与逻辑结构
1.1.1 逻辑结构：与实现无关的「关系图」
- 集合：元素间除「同属一个集合」外无其他关系；
- 线性结构：一对一前驱后继（线性表、栈、队列、串）；
- 树形结构：一对多（双亲与孩子）；
- 图状结构（网状）：多对多。
1.1.2 存储结构：落进内存的「实现方式」
- 顺序存储：相邻元素存放在地址连续的存储单元里（逻辑相邻 ⇒ 物理相邻）；
- 链式存储：用指针指示逻辑关系，物理位置可不相邻；
- 索引存储：附加索引表（关键字 → 地址）加速查找；
- 散列（哈希）存储：按关键字直接计算存储地址。
② 「有序表」指元素按关键字有序的线性表，仍属逻辑结构范畴（是线性表的特例），不要因「顺序」二字误判为存储结构；
③ 数据的运算：定义依赖于逻辑结构，实现依赖于存储结构——两句话方向别背反。
下列关于数据结构的叙述中，正确的是（ ）
A. 循环队列是一种逻辑结构 B. 哈希表是一种逻辑结构 C. 数据的逻辑结构独立于其存储结构 D. 数据运算的定义依赖于数据的存储结构
查看解答
C。逐项分析：
A 错：循环队列是「队列 + 顺序存储 + 取模绕回」的实现方案，属存储结构层面；队列本身才是逻辑结构。
B 错：哈希（散列）是第四种存储结构，哈希表是散列存储的产物。
C 对：逻辑结构描述元素间的关系，与怎样存进内存无关；这正是「一个队列可以分别用数组或链表实现」的原因。
D 错：说反了——运算的定义基于逻辑结构（如栈只说「先进后出」），实现才依赖存储结构。
数据结构的三要素是什么？并各举一例。
查看答案
三要素：逻辑结构（如二叉树的「一对多」关系）、存储结构（如用数组带下标 2i、2i+1 存完全二叉树）、数据的运算（如入栈、出栈的定义与实现）。
判断下列说法的正误：(1) 有序表是一种存储结构；(2) 栈、队列、串都是线性结构；(3) 顺序存储要求逻辑相邻的元素物理上也相邻。
查看答案
(1) 错：有序表是「元素按关键字有序的线性表」，属逻辑结构；顺序表才是存储结构。
(2) 对：三者元素都是一对一的线性关系（栈、队列只是运算受限的线性表）。
(3) 对：这正是顺序存储的定义；链式存储则无此要求（用指针表达逻辑相邻）。
1.2 算法与时间复杂度 高频考点
- 有穷性：有限步之后必然终止（程序可以不满足——如操作系统在无限循环中运行，程序 ≠ 算法）；
- 确定性：每条指令含义明确、无二义；
- 可行性：每步都可通过已实现的基本运算完成；
- 输入：零个或多个；
- 输出：一个或多个（至少一个，注意「零个输出」是错的）。
1.2.1 大 O 记号与推导规则
② 乘法规则：\(T_1\times T_2=O(f_1\cdot f_2)\)（嵌套执行相乘）；
③ 常数因子与低阶项直接丢弃。常用阶从小到大： \[ O(1)\lt O(\log_2 n)\lt O(n)\lt O(n\log_2 n)\lt O(n^{2})\lt O(n^{3})\lt O(2^{n})\lt O(n!) \]
② 大 O 中对数底数理论上无关（只差常数因子），但 408 习惯写 \(O(\log_2 n)\)；
③ 分析对象是基本操作的频次（深层循环体的执行次数），不是「代码行数」；外层循环变量判断要比执行体多一次（退出时的失败判断），频次统计要数准。
1.2.2 五类典型循环逐一验证
// 分析下列程序段的时间复杂度
int sum = 0; // ①
for (int i = 1; i <= n; i++) // ②
for (int j = 1; j <= n; j++) // ③
sum++; // ④查看解答
逐条统计频次：
① 执行 1 次；② 外层变量 \(i\) 从 1 递增到 \(n\)，加上退出时那次失败判断，共判断 \(n+1\) 次；③ 外层每轮中 \(j\) 都从 1 判断到 \(n+1\)（含失败），共 \(n(n+1)\) 次；④ 最内层体执行 \(n^{2}\) 次。
\[ T(n)=n^{2}+n(n+1)+(n+1)+2=2n^{2}+2n+3=O(n^{2}) \]
取最高阶项即可。频次法口诀：「外层判 \(n+1\)，内层套乘再判多一次，只留最高阶」。
// n > 1
int i = 1;
while (i <= n)
i = i * 2;查看解答
\(i\) 的取值序列：\(1,2,4,\dots,2^{t}\)。设循环体执行了 \(t+1\) 次后 \(i=2^{t+1}\gt n\) 终止，则 \(2^{t}\le n\lt 2^{t+1}\)，即 \(t=\lfloor\log_2 n\rfloor\)，循环体共执行 \(\lfloor\log_2 n\rfloor+1\) 次：
\[ T(n)=O(\log_2 n) \]数值验证（\(n=8\)）：\(i=1\to2\to4\to8\)，四次判断通过、循环体执行 4 次，第 5 次判断 \(16\gt 8\) 退出。\(\lfloor\log_2 8\rfloor+1=4\) ✓。又 \(n=10\)：\(i=1,2,4,8\) 共 4 次，\(\lfloor\log_2 10\rfloor+1=3+1=4\) ✓。
套路总结：变量每轮乘常数（或除常数）⇒ 对数阶；每轮加减常数 ⇒ 线性阶。
int sum = 0;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= i; j++)
sum++;查看解答
内层次数依赖外层变量：第 \(i\) 轮内层执行 \(i\) 次，总计
\[ \sum_{i=1}^{n}i=\frac{n(n+1)}{2}=\frac{n^{2}}{2}+\frac{n}{2}=O(n^{2}) \]数值验证（\(n=4\)）：内层次数 \(1+2+3+4=10=\frac{4\times5}{2}\) ✓。
易错：内层上界是 \(i\) 不是 \(n\)，不能直接写 \(n\times n\)；先求和再取阶。
int sum = 0;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j = j * 2)
sum++;查看解答
外层 \(n\) 轮；每轮内层是例 3 型倍增循环，执行 \(\lfloor\log_2 n\rfloor+1\) 次。由乘法规则：
\[ T(n)=n\cdot\big(\lfloor\log_2 n\rfloor+1\big)=O(n\log_2 n) \]数值验证（\(n=8\)）：外层 8 轮 × 内层 4 次 = 32 次，\(8\times(\lfloor\log_2 8\rfloor+1)=8\times4=32\) ✓。
long fib(int n) {
if (n <= 1) return n; // 基例
return fib(n - 1) + fib(n - 2); // 两次递归调用
}查看解答
每个非基例节点分裂出 2 个子调用，递归树第 \(k\) 层最多 \(2^{k}\) 个节点，深度约 \(n\)，调用总次数的量级为
\[ T(n)=O(2^{n}) \]（精确说树中节点数与斐波那契数本身同阶，约 \(O(1.618^{n})\)，408 标准答案记 \(O(2^{n})\)。）
套路总结：单分支递归（如 \(f(n)=f(n-1)+O(1)\)）画「链」→ 线性；多分支递归画「树」→ 指数。递归算法的空间复杂度还要算递归工作栈（见 1.3）。
分析下列程序段的时间复杂度：
int x = 2;
while (x < n / 2)
x = 2 * x;查看答案
每轮 \(x\) 翻倍，第 \(k\) 轮后 \(x=2^{k+1}\)，终止条件 \(2^{k+1}\ge n/2\)，即 \(k\ge\log_2(n/4)\)：
\[ T(n)=O(\log_2 n) \]（这是 2011 年真题原型的「除以 2」变式：循环变量指数增长，判断右端是常数倍 \(n\)，不改变对数阶。）
分析下列程序段的时间复杂度：
int i = 1;
while (i * i * i <= n)
i++;查看答案
循环体执行次数 \(t\) 满足 \(t^{3}\le n\lt(t+1)^{3}\)，即 \(t=\lfloor\sqrt[3]{n}\rfloor\)：
\[ T(n)=O(\sqrt[3]{n})=O(n^{1/3}) \]数值验证（\(n=27\)）：\(i=1,2,3\) 时判断通过（\(27\le27\) ✓），\(i=4\) 时 \(64\gt27\) 退出，循环体恰执行 \(3=\lfloor\sqrt[3]{27}\rfloor\) 次 ✓。
求 \(n\) 的阶乘的递归算法（\(f(0)=1\)，\(f(n)=n\times f(n-1)\)）的时间复杂度。
查看答案
单分支递归，递归深度为 \(n\)（\(f(n)\to f(n-1)\to\cdots\to f(0)\)），每层做一次乘法：
\[ T(n)=O(n) \]自检：\(f(4)\) 的调用链为 \(f(4)\to f(3)\to f(2)\to f(1)\to f(0)\)，共 5 次调用 = \(n+1\) 次 ✓。
1.3 空间复杂度
② 时间换空间、空间换时间是常见权衡（见例 7）；两者都最优通常做不到，按题意取舍。
// 将 a[0..n-1] 原地逆置？两种实现对比
void reverse1(int a[], int n) { // 实现一：辅助数组
int b[MAX];
for (int i = 0; i < n; i++)
b[n - 1 - i] = a[i]; // 倒着抄一遍
for (int i = 0; i < n; i++)
a[i] = b[i]; // 再抄回来
} // T=O(n), S=O(n)
void reverse2(int a[], int n) { // 实现二：对折交换（原地）
for (int i = 0; i < n / 2; i++) {
int t = a[i];
a[i] = a[n - 1 - i];
a[n - 1 - i] = t;
}
} // T=O(n), S=O(1)查看解答
两者时间都是 \(O(n)\)（都把每个元素碰常数次）；空间上实现一开了长度 \(n\) 的辅助数组 \(b\)，\(S(n)=O(n)\)；实现二只用临时变量 \(t\)，原地工作，\(S(n)=O(1)\)。
数值验证（\(n=5\)，下标 0～4）：对折交换执行 \(i=0,1\) 两轮，交换 \((0,4)\)、\((1,3)\)，中间 \(a[2]\) 不动——\(\lfloor 5/2\rfloor=2\) 轮，结果正确 ✓。
套路总结：「对折 / 双指针」是原地操作的标志动作；题目限内存（如嵌入式场景）优先实现二。
求 1.2 节例 5 的阶乘递归与例 6 的 fib 递归各自的空间复杂度。
查看解答
阶乘递归：调用链 \(f(n)\to f(n-1)\to\cdots\to f(0)\)，栈深 \(n+1\) 帧：
\[ S(n)=O(n) \]fib 递归：虽然调用次数是 \(O(2^{n})\)，但栈是「一条当前路径」——任意时刻活跃的调用只构成从根到某叶的一条路径，最大深度约 \(n\)：
\[ S(n)=O(n)\quad(\text{不是 }O(2^{n})!) \]易错：调用次数 ≠ 栈深度。递归树再宽，同时挂起的活动帧只等于当前递归路径长度。
判断：(1) 算法的时间复杂度与所用的计算机、编程语言有关；(2) 若算法的每层递归调用占用常数空间且递归深度为 \(\log_2 n\)，则 \(S(n)=O(\log_2 n)\)。
查看答案
(1) 错。大 O 描述渐进增长趋势，与机器速度、语言编译产物无关（那影响的是常数因子）；运行「时长」与机器有关，但「阶」无关。
(2) 对。栈深 \(\log_2 n\)、每帧常数空间，\(S(n)=O(\log_2 n)\)——这正是后面二分查找递归版的空间开销。
1.4 章末自测 真题风格
限时 45 分钟，先做后看答案。难度：★★ 基础 / ★★★ 强化 / ★★★★ 冲刺。所有复杂度结论自检：代入两三个具体的 \(n\) 数值验证次数。
算法和程序的区别之一在于算法必须具备（ ）
A. 每条指令的确定性 B. 可行性 C. 有穷性 D. 至少一个输入
查看答案
C。程序（如操作系统）可以在无限循环中永不终止，算法必须在有限步内结束——有穷性是「算法 ≠ 程序」的关键区别；A、B 算法程序都要满足，D 错在输入可以是零个（输出必须至少一个）。
下列复杂度按增长速度从小到大排列正确的是（ ）
A. \(O(\log_2 n)\lt O(\sqrt n)\lt O(n\log_2 n)\lt O(n^{3/2})\) B. \(O(\sqrt n)\lt O(\log_2 n)\lt O(n^{3/2})\lt O(n\log_2 n)\) C. \(O(\log_2 n)\lt O(n\log_2 n)\lt O(\sqrt n)\lt O(n^{3/2})\) D. \(O(n\log_2 n)\lt O(\log_2 n)\lt O(\sqrt n)\lt O(n^{3/2})\)
查看答案
A。对数慢于任何正幂次：\(\log_2 n\lt n^{\varepsilon}\)；幂次间比较指数：\(\sqrt n=n^{1/2}\lt n^{1.5}\)；而 \(n\log_2 n\) 夹在 \(n^{1}\) 与 \(n^{1+\varepsilon}\) 之间。验证 \(n=1024\)：\(\log_2 n=10\)、\(\sqrt n=32\)、\(n\log_2 n=10240\)、\(n^{3/2}=32768\)，大小关系吻合 ✓。
下列程序段的时间复杂度为（ ）
int count = 0;
for (int i = 1; i <= n; i++)
for (int j = 2 * i; j <= n; j++)
count++;A. \(O(\log_2 n)\) B. \(O(n)\) C. \(O(n\log_2 n)\) D. \(O(n^{2})\)
查看答案
D。第 \(i\) 轮内层执行 \(\max(n-2i+1,\,0)\) 次，只有 \(i\le n/2\) 时有贡献：
\[ \sum_{i=1}^{\lfloor n/2\rfloor}(n-2i+1)\approx\frac{n}{2}\cdot n-2\cdot\frac{(n/2)^{2}}{2}=\frac{n^{2}}{4}=O(n^{2}) \]
数值验证（\(n=4\)）：\(i=1\) 内层 \(j=2,3,4\) 共 3 次；\(i=2\) 内层 \(j=4\) 共 1 次；\(i=3,4\) 内层 0 次；合计 4 次 \(=n^{2}/4\) ✓。
下列程序段的时间复杂度为（ ）
int i = 1;
while (i * i <= n)
i = i + 2;A. \(O(\log_2 n)\) B. \(O(\sqrt n)\) C. \(O(n)\) D. \(O(n\log_2 n)\)
查看答案
B。\(i\) 每轮加 2 是线性增长，循环体次数 \(t\) 满足 \(t^{2}\lesssim n\)，\(t=O(\sqrt n)\)（增量 2 只差常数因子）。验证 \(n=16\)：\(i=1,3,5\) 判断通过（\(25\gt16\) 时停），执行 3 次 \(\approx\sqrt{16}/2\) ✓。
二叉树、队列、无向图的逻辑结构分别属于（ ）
A. 树形、线性、图状 B. 树形、线性、集合 C. 非线性、非线性、图状 D. 树形、非线性、图状
查看答案
A。队列是一对一的线性结构（运算受限的线性表），不要因「受限」误归为非线性；二叉树一对多，无向图多对多。
某计算机执行基本操作的速度约为 \(10^{9}\) 次 / 秒。一个 \(O(n^{2})\) 的算法要在 1 秒内完成，\(n\) 最大约为 \(\underline{\hspace{1.5cm}}\)。
查看答案
需 \(n^{2}\le 10^{9}\)，即 \(n\le\sqrt{10^{9}}\approx31623\)。精确核对边界：\(31622^{2}=999\,950\,884\le10^{9}\)，而 \(31623^{2}=1\,000\,014\,129\gt10^{9}\)，故最大 \(n=31622\)（按数量级答「约 \(3\times10^{4}\)」也对）。
同一计算机上，\(O(n\log_2 n)\) 的算法 1 秒内可处理的数据规模约为 \(\underline{\hspace{1.5cm}}\)（数量级）。
查看答案
需 \(n\log_2 n\le10^{9}\)。试 \(n=4\times10^{7}\)：\(\log_2(4\times10^{7})=2+\log_2 10^{7}\approx2+23.25=25.25\)，乘积 \(\approx1.01\times10^{9}\)，恰在边界附近。故约 \(4\times10^{7}\)（\(10^{7}\) 数量级）——可见把 \(O(n^{2})\) 优化成 \(O(n\log_2 n)\)，可处理规模从 \(3\times10^{4}\) 提升到 \(4\times10^{7}\)，提升千倍以上。
递归算法 \(\text{sum}(n)=\text{sum}(n-1)+n\)（\(\text{sum}(0)=0\)）的时间复杂度为 \(\underline{\hspace{1cm}}\)，空间复杂度为 \(\underline{\hspace{1cm}}\)。
查看答案
时间：递归深度 \(n\)、每层 \(O(1)\)，\(T(n)=O(n)\)；空间：递归工作栈深 \(n+1\) 帧，\(S(n)=O(n)\)。
写出下列程序段中语句 ①②③④ 的频次（用 \(n\) 表示），并给出总的时间复杂度。
int s = 0; // ①
for (int i = 1; i <= n; i++) { // ②
for (int j = 1; j < n; j++) // ③
s = s + a[i][j]; // ④
}查看解答
① 执行 \(1\) 次；② 外层判断 \(n+1\) 次（含退出时一次失败）；③ 外层每轮中 \(j\) 从 1 判断到 \(n\)（\(j\lt n\)，故 \(j=n\) 那次失败），共 \(n\) 次判断 → 总计 \(n\cdot n=n^{2}\) 次；④ 执行 \((n-1)\) 次每轮 → 总计 \(n(n-1)\) 次。
\[ T(n)=1+(n+1)+n^{2}+n(n-1)=2n^{2}+n+2=O(n^{2}) \]
数值验证（\(n=3\)）：③ 每轮判断 3 次 × 3 轮 = 9 = \(n^{2}\) ✓；④ 每轮 2 次 × 3 轮 = 6 = \(n(n-1)\) ✓。
易错：内层条件是 \(j\lt n\)（不带等号），每轮判断次数是 \(n\) 不是 \(n+1\)——频次题先看清循环边界开闭。
分析下列递归程序的时间复杂度与空间复杂度。
void f(int n) {
if (n <= 1) return;
f(n / 2);
f(n / 2);
}查看解答
时间：设规模 \(n\) 的调用次数为 \(T(n)\)，则 \(T(n)=2T(n/2)+O(1)\)。画递归树：第 \(k\) 层有 \(2^{k}\) 个规模 \(n/2^{k}\) 的节点，规模降为 1 时停止，即层数 \(k=\log_2 n\)，节点总数
\[ 1+2+4+\dots+2^{\log_2 n}=2^{\log_2 n+1}-1=2n-1=O(n) \]空间：两处调用是先后顺序执行（非同时挂起），任意时刻栈中只有一条「根到当前节点」的路径，最大深度 \(\log_2 n+1\)：
\[ S(n)=O(\log_2 n) \]数值验证（\(n=8\)）：调用节点 \(f(8)\) 1 个、\(f(4)\) 2 个、\(f(2)\) 4 个、\(f(1)\) 8 个，合计 \(15=2\times8-1\) ✓；最深路径 \(f(8)\to f(4)\to f(2)\to f(1)\) 共 4 帧 \(=\log_2 8+1\) ✓。
套路总结：\(T(n)=2T(n/2)+O(n)\)（如归并排序）→ \(O(n\log_2 n)\)；\(T(n)=2T(n/2)+O(1)\)（本题）→ \(O(n)\)。加法项是 \(O(1)\) 还是 \(O(n)\) 决定档位。
1.5 本章考点总结
| 考点 | 常考题型 | 热度 | 核心方法 |
|---|---|---|---|
| 逻辑结构与存储结构辨析 | 选择题 | ★★★★ 高频 | 循环队列 / 哈希表 / 顺序表 = 存储层面；栈 / 队列 / 有序表 = 逻辑层面；运算「定义看逻辑、实现看存储」 |
| 算法五大特性 | 选择题 | ★★★ | 有穷性区分算法与程序；输出至少一个；输入可零个 |
| 循环结构时间复杂度 | 选择 / 大题第一步 | ★★★★★ 每年必考 | 频次法 + 求和法；乘常数 → \(\log_2 n\)；加常数 → \(n\)；内界依赖外层 → \(\sum i\) |
| 递归复杂度 | 选择 / 解答 | ★★★★ | 单分支画链（线性），多分支画树（指数）；空间 = 递归深度 |
| 复杂度阶比较与机器速度估算 | 选择 / 填空 | ★★★ | 阶序表；\(10^{9}\) 次 / 秒 → \(O(n^{2})\) 约 \(3\times10^{4}\)，\(O(n\log_2 n)\) 约 \(4\times10^{7}\) |
| 时空权衡 | 大题设问 | ★★★ | 辅助数组换时间 or 对折双指针原地 \(O(1)\) |