建立数据结构、抽象数据类型与算法分析的统一框架，掌握逻辑结构、存储结构，以及时间复杂度和空间复杂度的基本分析方法。

# 一、数据结构的基本概念

# 1. 数据、数据元素与数据项

• 数据：能够被计算机识别、存储和处理的符号集合。
• 数据元素：数据的基本单位，通常作为整体参与处理；也称记录、结点等。
• 数据项：构成数据元素的不可分割的最小单位。例如学生记录中的学号、姓名、成绩都是数据项。
• 数据对象：性质相同的数据元素的集合，是数据的一个子集。

例如，学生信息管理系统中，“全体学生记录” 是数据对象；一条学生记录是数据元素；其中的学号是数据项。不要把 “数据项” 和 “数据元素” 混为一谈。

# 2. 数据结构

数据结构是相互之间存在一种或多种特定关系的数据元素的集合。它研究的不是单独的数据值，而是：

1. 数据元素之间有什么关系；
2. 这些关系如何存入计算机；
3. 在这些数据上允许并应如何实现哪些操作。

可以概括为：

$$\boxed{\text{数据结构}=\text{逻辑结构}+\text{存储结构}+\text{数据运算}}.$$

1
2
3
4
5
6
7

flowchart TB
    A[数据对象] --> B[逻辑结构<br/>元素之间的抽象关系]
    A --> C[存储结构<br/>关系在计算机中的表示]
    B --> D[线性、树形、图状、集合]
    C --> E[顺序、链式、索引、散列]
    B --> F[定义允许的数据运算]
    C --> G[决定操作的具体实现与代价]

# 逻辑结构

逻辑结构只描述元素间的逻辑关系，与计算机内存中的具体摆放位置无关。

从后续章节的视角，可把常见结构进一步对应为：

# 存储结构

存储结构也称物理结构，描述逻辑关系在计算机中的表示方式。

顺序存储与链式存储是本章线性表的两种重点实现。它们只规定存储组织方式，不规定对象一定在栈、堆或静态区：数组和结点实际位于何处取决于它们是局部对象、静态对象还是动态分配对象。

# 3. 数据类型与抽象数据类型

数据类型规定值的集合以及可施加于这些值上的操作集合，例如 C 语言中的 int、char。

抽象数据类型（Abstract Data Type, ADT）从用户视角定义数据对象、关系和操作，而不暴露具体存储实现。可以把线性表抽象地写为：

$$\operatorname{ADT\ List}= \left\{ \begin{array}{l} D=\{a_i\mid a_i\in\operatorname{ElemType},\ 1\le i\le n,\ n\ge0\},\\ R=\{\langle a_i,a_{i+1}\rangle\mid 1\le i<n\},\\ P=\{\operatorname{InitList},\operatorname{ListInsert},\operatorname{ListDelete},\ldots\}. \end{array} \right.$$

同一个 ADT 可以有多种实现。例如线性表既可由数组实现，也可由链表实现；用户调用的操作语义相同，时间和空间代价却可能不同。

数据结构提供组织数据的 “容器”，算法提供在该容器上解决问题的 “方法”。两者必须配合：例如数组实现栈能常数时间访问栈顶，链表实现队列并维护队尾指针可使入队、出队均为常数时间，堆可实现优先队列，图配合广度优先搜索可处理最短路径问题。

# 二、算法及其特性

# 1. 算法的定义

算法是为解决特定问题而规定的一组有限、明确、可执行的步骤。程序是算法在某种程序设计语言中的实现；同一算法可以有多种程序实现。

一个算法通常具有下列特性：

1. 有穷性：执行有限步后必须终止。
2. 确定性：每一步含义明确；给定相同输入时，执行路径和结果应确定。
3. 可行性：每一步都能在有限时间内由基本操作完成。
4. 有输入：可以有零个或多个输入。
5. 有输出：至少有一个输出。
6. 独立性：算法的思想不依赖某一种特定编程语言或机器。

# 2. 评价算法的标准

考研分析中最核心的是正确性、可读性、健壮性、时间效率和空间效率。

• 正确性：对所有合法输入都产生满足规格的输出。
• 可读性：结构清晰，便于理解、验证和维护。
• 健壮性：面对非法输入或边界条件时能作出合理处理。
• 高效率与低存储量：用时间复杂度、空间复杂度描述随输入规模增长的代价。

# 三、时间复杂度

# 1. 基本思想

设输入规模为 $n$，算法执行基本操作的次数为 $T(n)$。时间复杂度关注 $n$ 充分大时 $T(n)$ 的增长量级，而非某台机器上的秒数。

若存在正常数 $c,n_0$，使得对任意 $n\ge n_0$ 都有

$$0\le T(n)\le c f(n),$$

则记为

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

实际分析中通常执行三步：

1. 确定输入规模 $n$ 与基本操作；
2. 写出基本操作的执行次数 $T(n)$；
3. 忽略常数系数和低阶项，只保留最高阶增长量级。

例如 $T(n)=3n^2+10n+7$，则 $T(n)=O(n^2)$。

# 2. 常见数量级

从增长较慢到较快，常见量级为：

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

# 3. 循环与递归的分析

1
2
3
4
5
6
7
8
9
10

int sum_pair(int a[], int n) {
    int ans = 0;
    for (int i = 0; i < n; i++) {
        ans += a[i];
    }
    for (int j = 0; j < n; j++) {
        ans += a[j] * a[j];
    }
    return ans;
}

两段循环依次执行，基本操作次数为 $an+b n+c$，故时间复杂度是 $O(n)$。

1
2
3
4
5
6
7
8
9

int count_pairs(int n) {
    int cnt = 0;
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            cnt++;
        }
    }
    return cnt;
}

内层循环总次数为

$$(n-1)+(n-2)+\cdots+1=\frac{n(n-1)}2,$$

故时间复杂度为 $O(n^2)$。

对于递归，除循环次数外还要写出递推式。例如二分查找满足

$$T(n)=T(\lfloor n/2\rfloor)+O(1)=O(\log n).$$

而每次只减少一个元素的递归满足

$$T(n)=T(n-1)+O(1)=O(n).$$

1
2
3
4
5
6
7
8
9

int f(int n) {
    int cnt = 0;
    for (int i = 1; i < n; i *= 2) {
        for (int j = 0; j < n; j++) {
            cnt++;
        }
    }
    return cnt;
}

# 4. 最好、最坏与平均情况

对输入规模相同的不同实例，基本操作次数可能不同。

• 最好情况时间复杂度：所有规模为 $n$ 的输入中，执行次数的下界。
• 最坏情况时间复杂度：所有规模为 $n$ 的输入中，执行次数的上界；题目未特别说明时通常按最坏情况分析。
• 平均情况时间复杂度：在给定输入概率分布下的期望执行次数，必须说明概率模型。

例如顺序查找目标值：首元素命中是 $O(1)$，末元素命中或不存在是 $O(n)$；在等概率成功查找模型下，平均比较次数约为 $(n+1)/2$，量级仍为 $O(n)$。

# 四、空间复杂度

空间复杂度 $S(n)$ 描述算法运行过程中所需额外存储空间随 $n$ 的增长量级。讨论题目时应先说明口径：有些教材把输入数据本身也计入总空间；算法分析中更常考察辅助空间。

从组成上看，空间可分为与 $n$ 无关的固定部分（程序代码、常量和有限个简单变量等）以及随输入规模变化的可变部分（输入数据、辅助数组、栈、队列和递归调用栈等）。取渐近量级时只保留增长最快的部分。

递归调用栈不能遗漏。例如递归二分查找每层只保存常数个变量，但递归深度为 $O(\log n)$，故辅助空间为 $O(\log n)$；改写为迭代版本后可降为 $O(1)$。

# 五、考场检查清单

1. 先分清逻辑结构与存储结构，不能把 “连续地址” 误当作 “线性结构”。
2. 写复杂度时先找规模 $n$ 与基本操作，再数执行次数。
3. 多段顺序代码取相加后的最高阶；嵌套结构再考虑相乘或求和。
4. 递归题同时写时间递推式和递归深度，后者决定调用栈空间。
5. $O(\cdot)$ 描述增长上界；比较算法时必须在相同规模和相同代价模型下进行。