第1章 数据结构与算法基础理论

本章导读

本章建立数据结构与算法分析的理论基础，包括形式化定义、渐近分析理论、计算复杂度基础以及抽象数据类型理论。这些内容是理解后续章节的理论基石。

学习目标

完成本章学习后，读者将能够：

• 掌握数据结构的形式化定义与分类理论
• 理解渐近符号的严格数学定义及其性质
• 应用主定理分析递归算法复杂度
• 理解计算复杂度类（P、NP、NP完全）的基本概念
• 掌握抽象数据类型的代数规范方法
• 理解数据结构选择的理论依据

---

1.1 数据结构的形式化理论

1.1.1 数据结构的数学定义

定义 1.1（数据结构） 数据结构是一个三元组 $\mathcal{DS} = (D, R, O)$，其中：

• $D = {d_1, d_2, \ldots, d_n}$ 是数据元素的有限集合
• $R \subseteq D \times D$ 是定义在 $D$ 上的关系的有限集合
• $O = {o_1, o_2, \ldots, o_m}$ 是定义在 $D$ 上的操作集合

定义 1.2（逻辑结构） 数据的逻辑结构是数据元素之间的逻辑关系，形式化定义为有向图 $G = (V, E)$，其中 $V = D$，$E$ 由关系 $R$ 确定。

根据逻辑结构的不同，数据结构可分为：

类型	形式化定义	特征
线性结构	$\forall x \in D,	{y : (x,y) \in R}
树形结构	存在唯一根节点，其余节点有且仅有一个前驱	层次关系
图结构	无特殊限制	任意多对多关系
集合结构	$R = \emptyset$	元素无关系

1.1.2 抽象数据类型（ADT）

定义 1.3（抽象数据类型） 抽象数据类型是一个数学模型，由以下部分组成：

1. 值域 $V$：可能取值的集合
2. 操作签名：操作名称及其参数和返回类型
3. 公理：描述操作语义的逻辑公式

例 1.1（栈ADT的代数规范）

ADT Stack[T]
  Types: Stack[T]
  Operations:
    empty: → Stack[T]
    push: Stack[T] × T → Stack[T]
    pop: Stack[T] → Stack[T] ∪ {error}
    top: Stack[T] → T ∪ {error}
    isEmpty: Stack[T] → Boolean
  
  Axioms:
    ∀s: Stack[T], ∀x: T
    (A1) isEmpty(empty) = true
    (A2) isEmpty(push(s, x)) = false
    (A3) top(push(s, x)) = x
    (A4) pop(push(s, x)) = s
    (A5) pop(empty) = error
    (A6) top(empty) = error

定理 1.1 栈ADT的公理系统是一致的，即不存在从公理推导出的矛盾。

证明：通过构造模型证明。设模型为列表，empty为空列表，push为append，pop为删除最后一个元素，top为访问最后一个元素，isEmpty为判空。可以验证所有公理在该模型下成立。因此公理系统有模型，由可靠性定理知其一致。∎

1.1.3 数据结构的实现与抽象层次

抽象层次模型
┌─────────────────────────────────────────────────────────────┐
│  第4层：应用层                                               │
│  用户程序、业务逻辑                                           │
├─────────────────────────────────────────────────────────────┤
│  第3层：抽象数据类型层                                        │
│  规范定义、操作语义、公理系统                                  │
├─────────────────────────────────────────────────────────────┤
│  第2层：数据结构层                                            │
│  具体实现、算法设计、复杂度分析                                │
├─────────────────────────────────────────────────────────────┤
│  第1层：物理存储层                                            │
│  内存管理、存储分配、硬件特性                                  │
└─────────────────────────────────────────────────────────────┘

---

1.2 算法复杂度理论

1.2.1 渐近符号的形式化定义

定义 1.4（O记号） 设 $f, g: \mathbb{N} \rightarrow \mathbb{R}^+$，则：

$$f(n) = O(g(n)) \iff \exists c > 0, \exists n_0 > 0, \forall n \geq n_0: f(n) \leq c \cdot g(n)$$

定义 1.5（Ω记号）

$$f(n) = \Omega(g(n)) \iff \exists c > 0, \exists n_0 > 0, \forall n \geq n_0: f(n) \geq c \cdot g(n)$$

定义 1.6（Θ记号）

$$f(n) = \Theta(g(n)) \iff f(n) = O(g(n)) \land f(n) = \Omega(g(n))$$

定义 1.7（o记号）

$$f(n) = o(g(n)) \iff \forall c > 0, \exists n_0 > 0, \forall n \geq n_0: f(n) < c \cdot g(n)$$

定义 1.8（ω记号）

$$f(n) = \omega(g(n)) \iff \forall c > 0, \exists n_0 > 0, \forall n \geq n_0: f(n) > c \cdot g(n)$$

定理 1.2（传递性） 若 $f(n) = O(g(n))$ 且 $g(n) = O(h(n))$，则 $f(n) = O(h(n))$。

证明：由定义，存在 $c_1, n_1$ 使得 $f(n) \leq c_1 g(n)$ 对所有 $n \geq n_1$ 成立；存在 $c_2, n_2$ 使得 $g(n) \leq c_2 h(n)$ 对所有 $n \geq n_2$ 成立。取 $c = c_1 c_2$，$n_0 = \max(n_1, n_2)$，则对所有 $n \geq n_0$：

$$f(n) \leq c_1 g(n) \leq c_1 c_2 h(n) = c \cdot h(n)$$

故 $f(n) = O(h(n))$。∎

1.2.2 渐近符号的性质

定理 1.3（加法规则） 若 $f_1(n) = O(g_1(n))$，$f_2(n) = O(g_2(n))$，则：

$$f_1(n) + f_2(n) = O(\max(g_1(n), g_2(n)))$$

定理 1.4（乘法规则） 若 $f_1(n) = O(g_1(n))$，$f_2(n) = O(g_2(n))$，则：

$$f_1(n) \cdot f_2(n) = O(g_1(n) \cdot g_2(n))$$

定理 1.5（L'Hôpital规则在渐近分析中的应用） 设 $f, g$ 为可微函数，若 $\lim_{n \to \infty} f(n) = \lim_{n \to \infty} g(n) = \infty$，则：

$$\lim_{n \to \infty} \frac{f(n)}{g(n)} = \lim_{n \to \infty} \frac{f'(n)}{g'(n)}$$

1.2.3 主定理

定理 1.6（主定理） 设递归式 $T(n) = aT(n/b) + f(n)$，其中 $a \geq 1$，$b > 1$。令 $c_{crit} = \log_b a$。则：

1. 若 $f(n) = O(n^{c_{crit} - \varepsilon})$ 对某个 $\varepsilon > 0$，则 $T(n) = \Theta(n^{c_{crit}})$
2. 若 $f(n) = \Theta(n^{c_{crit}} \log^k n)$ 对某个 $k \geq 0$，则 $T(n) = \Theta(n^{c_{crit}} \log^{k+1} n)$
3. 若 $f(n) = \Omega(n^{c_{crit} + \varepsilon})$ 对某个 $\varepsilon > 0$，且满足正则条件 $af(n/b) \leq cf(n)$ 对某个 $c < 1$，则 $T(n) = \Theta(f(n))$

例 1.2 分析归并排序的复杂度 $T(n) = 2T(n/2) + \Theta(n)$。

解：$a = 2$，$b = 2$，$f(n) = n$，$c_{crit} = \log_2 2 = 1$。

$f(n) = n = \Theta(n^1 \log^0 n) = \Theta(n^{c_{crit}})$，属于情况2。

因此 $T(n) = \Theta(n \log n)$。∎

例 1.3 分析二分查找的复杂度 $T(n) = T(n/2) + O(1)$。

解：$a = 1$，$b = 2$，$f(n) = 1$，$c_{crit} = \log_2 1 = 0$。

$f(n) = 1 = \Theta(n^0 \log^0 n) = \Theta(n^{c_{crit}})$，属于情况2。

因此 $T(n) = \Theta(\log n)$。∎

---

1.3 计算复杂度理论基础

1.3.1 计算模型

定义 1.9（图灵机） 图灵机是一个七元组 $M = (Q, \Sigma, \Gamma, \delta, q_0, q_{accept}, q_{reject})$，其中：

• $Q$：有限状态集
• $\Sigma$：输入字母表（不含空白符）
• $\Gamma$：带字母表，$\Sigma \subseteq \Gamma$，空白符 $\sqcup \in \Gamma$
• $\delta: Q \times \Gamma \rightarrow Q \times \Gamma \times {L, R}$：转移函数
• $q_0 \in Q$：初始状态
• $q_{accept} \in Q$：接受状态
• $q_{reject} \in Q$：拒绝状态

定义 1.10（时间复杂度） 图灵机 $M$ 在输入 $w$ 上的运行时间是 $M$ 在处理 $w$ 时执行的步数。

1.3.2 复杂度类

定义 1.11（P类） $P = \bigcup_{k \geq 1} TIME(n^k)$，即确定性图灵机在多项式时间内可判定的问题类。

定义 1.12（NP类） $NP$ 是非确定性图灵机在多项式时间内可判定的问题类。等价地，$NP$ 是具有多项式长度证书且可在多项式时间内验证的问题类。

定义 1.13（NP完全） 语言 $L$ 是NP完全的，若：

1. $L \in NP$
2. 对所有 $L' \in NP$，$L' \leq_p L$（$L'$ 可多项式时间归约到 $L$）

定理 1.7（Cook-Levin定理） 布尔可满足性问题（SAT）是NP完全的。

1.3.3 数据结构问题的复杂度下界

定理 1.8（比较排序下界） 任何基于比较的排序算法在最坏情况下需要 $\Omega(n \log n)$ 次比较。

证明：排序问题的决策树是一棵二叉树，每个内部节点表示一次比较，叶子节点表示排序结果。$n$ 个元素有 $n!$ 种排列，因此决策树至少有 $n!$ 个叶子。高度为 $h$ 的二叉树至多有 $2^h$ 个叶子，故：

$$2^h \geq n! \implies h \geq \log_2(n!) = \Omega(n \log n)$$

由Stirling公式：$n! \approx \sqrt{2\pi n}(n/e)^n$，故 $\log(n!) = \Theta(n \log n)$。∎

定理 1.9（查找下界） 在无序数组中查找特定元素，任何确定性算法需要 $\Omega(n)$ 时间。

---

1.4 均摊分析理论

1.4.1 均摊分析的定义

定义 1.14（均摊复杂度） 设数据结构支持操作序列 $O_1, O_2, \ldots, O_m$，第 $i$ 个操作的实际代价为 $c_i$。则操作的均摊代价 $\hat{c}_i$ 满足：

$$\sum_{i=1}^{m} \hat{c}i \geq \sum^{m} c_i$$

总均摊代价给出了总实际代价的上界。

1.4.2 均摊分析方法

聚合分析（Aggregate Analysis）

证明对所有 $n$，$m$ 个操作序列的最坏情况代价为 $T(n, m)$，则每个操作的均摊代价为 $T(n, m)/m$。

例 1.4 动态数组的 $m$ 次 append 操作。

设初始容量为1，每次扩容倍增。第 $i$ 次扩容发生在 $n = 2^i$ 时，代价为 $2^i$。总扩容代价：

$$\sum_{i=0}^{\lfloor \log m \rfloor} 2^i = 2^{\lfloor \log m \rfloor + 1} - 1 \leq 2m - 1 = O(m)$$

因此均摊代价为 $O(1)$。∎

核算方法（Accounting Method）

为每个操作分配均摊代价，部分作为"存款"用于支付未来操作的代价。

势能方法（Potential Method）

定义势能函数 $\Phi: D \rightarrow \mathbb{R}^+$，其中 $D$ 是数据结构的状态空间。均摊代价定义为：

$$\hat{c}i = c_i + \Phi(D_i) - \Phi(D)$$

定理 1.10 若 $\Phi(D_i) \geq \Phi(D_0)$ 对所有 $i$ 成立，则：

$$\sum_{i=1}^{m} \hat{c}i \geq \sum^{m} c_i$$

例 1.5 用势能方法分析动态数组。

定义势能函数 $\Phi(D) = 2n - capacity$，其中 $n$ 是元素数，$capacity$ 是容量。

• 普通插入：$c_i = 1$，$\Phi$ 增加2，$\hat{c}_i = 1 + 2 = 3$
• 扩容插入：$c_i = n + 1$（复制 $n$ 个元素加插入），$\Phi$ 从 $n$ 变为 $2$，$\hat{c}_i = n + 1 + 2 - n = 3$

因此每次插入的均摊代价为 $O(1)$。∎

---

1.5 Python数据结构实现原理

1.5.1 Python对象模型

Python中所有数据都是对象，其内存布局如下：

PyObject 结构（所有Python对象的基础）
┌─────────────────────────────────────┐
│  ob_refcnt  │ 引用计数（用于GC）      │
├─────────────────────────────────────┤
│  ob_type    │ 类型对象指针            │
├─────────────────────────────────────┤
│  ...        │ 类型特定数据            │
└─────────────────────────────────────┘

1.5.2 列表的CPython实现

# CPython中PyListObject的简化定义
class PyListObject:
    ob_refcnt: int      # 引用计数
    ob_type: type       # 类型指针
    ob_size: int        # 当前元素数
    allocated: int      # 已分配容量
    ob_item: list       # 元素指针数组

扩容策略分析

CPython采用以下扩容公式：

$$new_allocated = (newsize + (newsize >> 3) + 6) \land \sim 3$$

这约等于 $1.125$ 倍增长，比典型的 $2$ 倍增长更节省内存。

1.5.3 字典的CPython实现

Python 3.7+采用紧凑字典（Compact Dict）：

紧凑字典结构
┌─────────────────────────────────────────────────────┐
│  PyDictObject                                        │
├─────────────────────────────────────────────────────┤
│  ma_keys    ────────┐                               │
│  ma_values  ────┐   │                               │
└─────────────────│───│───────────────────────────────┘
                  │   │
                  ▼   ▼
         ┌───────────────────────────────────┐
         │  PyDictKeysObject                  │
         ├───────────────────────────────────┤
         │  dk_indices: 哈希索引数组          │
         │  dk_entries: 键值条目数组          │
         └───────────────────────────────────┘

---

1.6 本章小结

1.6.1 核心概念总结

概念	形式化定义	应用
数据结构	$\mathcal{DS} = (D, R, O)$	问题建模
ADT	值域 + 操作 + 公理	接口设计
渐近复杂度	$O, \Omega, \Theta$	算法分析
均摊复杂度	势能函数法	数据结构分析
计算复杂度类	P, NP, NP完全	问题分类

1.6.2 重要定理

1. 主定理：递归算法复杂度分析的通用方法
2. 比较排序下界：$\Omega(n \log n)$
3. Cook-Levin定理：SAT是NP完全的

1.6.3 学习路线

第1章 理论基础 ← 当前位置
    ↓
第2-6章 Python内置数据结构
    ↓
第7-10章 线性数据结构
    ↓
第11-14章 树形数据结构
    ↓
第15-18章 图与哈希
    ↓
第19-26章 算法设计与分析

---

1.7 习题

理论题

1. 证明：若 $f(n) = O(g(n))$ 且 $g(n) = O(h(n))$，则 $f(n) + g(n) = O(h(n))$。

2. 证明：$\log(n!) = \Theta(n \log n)$。

3. 使用主定理分析 $T(n) = 3T(n/4) + n \log n$。

4. 证明任何基于比较的查找算法在最坏情况下需要 $\Omega(\log n)$ 次比较。

设计题

5. 设计一个势能函数，证明双端队列的 $m$ 次 push/pop 操作均摊代价为 $O(1)$。

6. 给出优先队列ADT的代数规范，并证明其公理系统的一致性。

研究题

7. 讨论 $P = NP$ 问题对数据结构研究的影响。

8. 调研并总结近年来数据结构领域的重大突破（如跳表、布隆过滤器、LSM树等）。

---

1.8 参考文献

1. Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2022). Introduction to Algorithms (4th ed.). MIT Press.

2. Knuth, D. E. (1997). The Art of Computer Programming, Volume 1: Fundamental Algorithms (3rd ed.). Addison-Wesley.

3. Aho, A. V., Hopcroft, J. E., & Ullman, J. D. (1983). Data Structures and Algorithms. Addison-Wesley.

4. Tarjan, R. E. (1983). Data Structures and Network Algorithms. SIAM.

5. Sipser, M. (2012). Introduction to the Theory of Computation (3rd ed.). Cengage Learning.

---

下一章：第2章 列表与动态数组