第一章 绪论

1.1 数据结构的基本概念

一、核心定义

数据（Data）：信息的载体，是对客观事物符号化的表示，能够被计算机识别、存储和加工处理。

🗣️ 大白话：数据就是计算机能认识的东西。你的名字、年龄、一张照片、一段视频，只要能存进电脑里的，都叫数据。

数据元素（Data Element）：数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。一个数据元素可由若干个数据项（Data Item） 组成，数据项是构成数据元素的不可分割的最小单位。

🗣️ 大白话：好比一个学生信息表，每一行（一个学生的全部信息）就是一个数据元素，而"姓名""学号""成绩"这些列就是数据项。数据项是最小的，不能再拆了。

数据对象（Data Object）：性质相同的数据元素的集合，是数据的一个子集。

数据结构（Data Structure）：相互之间存在一种或多种特定关系的数据元素的集合。包含三个方面：

二、逻辑结构的分类

🗣️ 大白话：

• 线性结构就像排队——每个人前面最多一个人，后面也最多一个人，一条线串起来。
• 树形结构就像家族族谱——一个爷爷可以有好几个儿子，但每个人只有一个亲爹。
• 图状结构就像微信朋友圈——你认识我，我认识他，他也可能认识你，关系错综复杂。
• 集合结构就像一筐苹果——它们之间没啥特别关系，只是放在了一起。

三、存储结构的四种基本方式

🗣️ 大白话：

• 顺序存储：就像图书馆的书架，书按编号挨个排好，找第5本直接数到第5个位置。
• 链式存储：就像寻宝游戏，每本书里夹了一张纸条，告诉你下一本书在哪。
• 索引存储：就像书的目录，先查目录找到页码，再翻到那一页。
• 散列存储：就像按名字首字母分类放东西，姓"张"的放到Z区，直接去那个区找。

四、数据类型与抽象数据类型

数据类型（Data Type）：一个值的集合和定义在此集合上的一组操作的总称。

抽象数据类型（ADT, Abstract Data Type）：一个数学模型以及定义在该模型上的一组操作。ADT的定义仅取决于它的一组逻辑特性，与其在计算机内部的表示和实现无关。

🗣️ 大白话：ADT就是"你只管用，不用管我怎么做到的"。就像你用手机打电话，你只知道拨号就能打通，至于信号怎么传输的你不需要管——这就是"抽象"。

1.2 算法与算法评价

一、算法的基本概念

算法（Algorithm）：对特定问题求解步骤的一种描述，是指令的有限序列。

算法的五个重要特性：

⚠️ 考研高频考点：算法与程序的区别——算法必须是有穷的，而程序可以是无穷的（如操作系统是一直运行的程序）。

"好"算法的评价标准：

1. 正确性：能正确解决问题
2. 可读性：易于阅读理解
3. 健壮性：能对非法输入做出适当反应
4. 效率与低存储量：时间复杂度低、空间复杂度低

二、时间复杂度

定义：算法中基本操作的执行次数 $T(n)$ 是问题规模 $n$ 的函数，取 $T(n)$ 的数量级（最高阶项），记作：

$T(n) = O(f(n))$

表示当 $n$ 趋于无穷大时，$T(n)$ 的增长率与 $f(n)$ 的增长率相同。

常见时间复杂度排序（从低到高）：

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

📝 记忆口诀："常对根线，线对平立，指阶阶阶"——常数、对数、根号、线性、线性对数、平方、立方、指数、阶乘。简化记为"常对幂指阶"（常数 < 对数 < 幂函数 < 指数函数 < 阶乘）。

⚠️ 注意 $O(\sqrt{n}) = O(n^{0.5})$ 介于 $O(\log n)$ 和 $O(n)$ 之间，考研真题偶尔出现。

🗣️ 大白话：时间复杂度就是衡量"当数据量变大时，算法变慢的速度"。$O(1)$ 意味着不管数据多少，速度都一样快（比如查数组的第k个元素）；$O(n)$ 意味着数据翻倍，时间也翻倍（比如遍历数组）；$O(n^2)$ 意味着数据翻倍，时间变4倍（比如冒泡排序）。

三种复杂度：

• 最坏时间复杂度：最不利情况下的时间复杂度（考研默认分析这个）
• 平均时间复杂度：所有可能输入的平均时间
• 最好时间复杂度：最理想情况下的时间复杂度（一般不讨论）

常见代码的时间复杂度分析方法：

// O(1) —— 常数阶
int x = 1;
int y = x + 1;

// O(n) —— 线性阶
for (int i = 0; i < n; i++)
    x++;

// O(n²) —— 平方阶
for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++)
        x++;

// O(log₂n) —— 对数阶
while (n > 1)
    n = n / 2;

// O(n·log₂n) —— 线性对数阶
for (int i = 0; i < n; i++)
    for (int j = 1; j < n; j = j * 2)
        x++;

// O(1) —— 常数阶
int x = 1;
int y = x + 1;

// O(n) —— 线性阶
for (int i = 0; i < n; i++)
    x++;

// O(n²) —— 平方阶
for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++)
        x++;

// O(log₂n) —— 对数阶
while (n > 1)
    n = n / 2;

// O(n·log₂n) —— 线性对数阶
for (int i = 0; i < n; i++)
    for (int j = 1; j < n; j = j * 2)
        x++;

三、空间复杂度

定义：算法所需存储空间 $S(n)$ 关于问题规模 $n$ 的数量级，记作：

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

⚠️ 注意：空间复杂度只计算算法额外使用的辅助空间，不包括输入数据本身占用的空间。

算法原地工作：指算法所需的辅助空间为常量，即 $S(n) = O(1)$。

🗣️ 大白话：空间复杂度就是你算法运行时"额外"需要多少空间。就像你收拾房间，你已有的东西不算，你额外需要买几个收纳箱——那就是空间复杂度。如果不需要额外买箱子就能搞定（原地工作），那就是 $O(1)$。

📝 真题剖析

【2011年408真题】 设 $n$ 是描述问题规模的非负整数，下面程序段的时间复杂度是（）。

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

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

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

解题方法：

设循环执行 $t$ 次。每次 $x$ 变为 $2x$，初始 $x=2$。

• 第1次后：$x = 2 \times 2 = 4 = 2^2$
• 第2次后：$x = 2 \times 4 = 8 = 2^3$
• 第 $t$ 次后：$x = 2^{t+1}$

循环结束条件：$2^{t+1} \geq n/2$，即 $t+1 \geq \log_2(n/2) = \log_2 n - 1$

所以 $t = O(\log_2 n)$。答案选A。

💡 解题套路：看到变量成倍增长（$x = 2x$）或成倍缩减（$n = n/2$），八成就是 $O(\log n)$ 级别。

【2012年408真题】 求 $n!$ 的递归算法（fact(n)），其时间复杂度为（）。

int fact(int n) {
    if (n <= 1) return 1;
    return n * fact(n - 1);
}

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

解：递推关系 $T(n) = T(n-1) + O(1)$（$n>1$），$T(1) = O(1)$。展开得 $T(n) = O(n)$。答案选B。

💡 递归时间复杂度分析套路：列出递推关系式，展开或用主定理求解。每层递归只做 $O(1)$ 工作、递归 $n$ 层 → $O(n)$。

【递归复杂度分析利器——主定理（Master Theorem）简化版】

对于形如 $T(n) = aT(n/b) + O(n^d)$ 的递推关系（$a \geq 1, b > 1, d \geq 0$）：

常考实例：

⚠️ 注意：主定理仅适用于"规模缩小为 $n/b$"的递推关系。如 $T(n) = T(n-1) + O(n)$（如选择排序的递归版）属于递减型递推，需直接展开：$T(n) = n + (n-1) + \cdots + 1 = O(n^2)$。

【摊还分析（Amortized Analysis）——高级复杂度分析】

某些操作的单次最坏代价很高，但连续多次操作的平均代价很低。摊还分析给出的是操作序列的平均上界，比最坏情况分析更精确。

🗣️ 大白话：就像你每月存100块钱，到年底一次性花1200修车。每次花钱看起来很"便宜"（月均100），但修车那次本身花了1200。摊还分析就是把1200分摊到12个月来看。

典型例子——动态数组扩容：顺序表满了就翻倍扩容，扩容时复制所有元素代价为 $O(n)$。但从空开始连续插入 $n$ 个元素，扩容总代价为 $1+2+4+\cdots+n = O(n)$。因此每次插入的摊还代价为 $O(1)$，而非最坏的 $O(n)$。

考试关键：并查集使用按秩合并 + 路径压缩后，$m$ 次操作的总代价为 $O(m \cdot \alpha(n))$，其中 $\alpha(n)$ 是反阿克曼函数（增长极慢，对所有实际情况 $\alpha(n) \leq 4$）。因此单次操作的摊还代价近似 $O(1)$。

【2017年408真题】 下面程序段的时间复杂度是（）。

int sum = 0, i = 1;
while (sum < n)
    sum += ++i;

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

解：设循环执行 $t$ 次，则 $sum = 2+3+\cdots+(t+1) = \frac{(t+1)(t+2)}{2} - 1$。当 $sum \geq n$ 时结束，即 $t^2/2 \approx n$，解得 $t \approx \sqrt{2n}$。答案选B。

💡 解题套路：当累加和与 $n$ 比较时，累加量递增形成等差数列求和 → $O(\sqrt{n})$。

【2025年408真题】 下面程序段的时间复杂度是（）。

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

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

解：外层循环 $i$ 从1到 $\sqrt{n}$，内层循环 $j$ 从1到 $i$。总执行次数 $T(n) = \sum_{i=1}^{\sqrt{n}} i = \frac{\sqrt{n}(\sqrt{n}+1)}{2} \approx \frac{n}{2}$。答案选B，$O(n)$。

⚠️ $\sqrt{n}$ 相关的时间复杂度是近年真题高频考点！ 常见模式：

• 循环条件含 i*i<=n 或 sum<n（sum等差递增）→ $O(\sqrt{n})$ 或 $O(n)$
• 2019真题：条件 n>=(x+1)*(x+1) 同理 → $O(\sqrt{n})$

【2014年408真题】 下面程序段的时间复杂度是（）。

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

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

解：外层 $k$ 每次乘2，执行 $\log_2 n$ 次；内层 $j$ 每次执行 $n$ 次。总次数 $= n \cdot \log_2 n$。答案选B。

💡 解题套路：外层"乘2"→ $\log n$ 次；内层"加1"→ $n$ 次。相乘即得 $O(n\log n)$。

【2019年408真题】 下面程序段的时间复杂度是（）。

int x = 0;
while (n >= (x + 1) * (x + 1))
    x++;

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

解：循环执行 $t$ 次后 $x = t$，退出条件 $n < (t+1)^2$，即 $t \geq \lfloor\sqrt{n}\rfloor$，所以 $T(n) = O(\sqrt{n})$。答案选B。

💡 解题套路：循环条件含 $(x+1)^2 \leq n$，等价于 $x$ 从0增长到 $\sqrt{n}$，时间复杂度为 $O(\sqrt{n})$。

【2022年408真题】 下面程序段的时间复杂度是（）。

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

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

解：外层 $i = 1, 2, 4, \ldots, 2^k$（其中 $2^k \leq n$），内层执行 $i$ 次。总次数：

$T(n) = 1 + 2 + 4 + \cdots + 2^k = 2^{k+1} - 1 \approx 2n - 1$

这是等比数列求和，结果为 $O(n)$。答案选B。

⚠️ 易错点：不要想当然地认为"外层 $\log n$ × 内层 $n$"就是 $O(n\log n)$。内层循环次数随外层变化（$j \leq i$，不是 $j \leq n$），必须用等比求和精确计算。这是区分 $O(n)$ 和 $O(n\log n)$ 的高频陷阱！

📌 第一章总结