数据结构
绪论
主要内容
程序 = 数据结构 + 算法
数据结构 = 数据集 + 关系 + 操作
即数据结构是数据集合及其之间的关系和**操作（运算）**的集合。
概括地说，数据结构是一门研究“程序设计问题中计算机操作对象以及它们之间的关系和操作”的学科。
具体地说，数据结构主要研究数据之间有哪些结构关系，如何表示，如何存储，如何处理。
基本术语
数据
数据是信息在计算机程序中的表现形式或编码形式，是描述客观事物的数、字符及所有能输入到计算机中并被计算机程序处理的符号的集合。
是对计算机处理的对象的一个统称，被看作为信息的载体
大致可分为两类：
- 数值型数据：整数、实数、复数等
- 非数值型数据：字符、字符串、图像、声音等
数据元素
数据的基本单位是数据元素，它是计算机处理或访问的基本单位。
数据项
数据不可分割的最小标识单位，一个数据元素可由若干数据项组成。
| 学号 | 姓名 | 性别 | 年龄 | 专业 |
|---|---|---|---|---|
| 1001 | 张三 | 男 | 20 | 计算机 |
其中一个人的信息就是一个数据元素，而他的学号、姓名、性别、年龄、专业就是数据项。
即
| 1001 | 张三 | 男 | 20 | 计算机 |
|---|
是一个数据元素，而
1001，张三，男，20，计算机
是这个数据元素的数据项。
数据结构
数据结构是由与特定问题相关的某一数据元素的集合和该集合中数据元素之间的关系组成的。
数据对象
从狭义的观点把数据对象定义为具有一定关系的相同性质的数据元素的集合。
例如，学生的集合、教师的集合、图书的集合等。
从广义的观点把数据对象定义为一个由数据抽象和处理抽象构成的封装体，即数据对象的声明中不但要包含属性，还要包含可用的操作。
例如一个学生对象，除了包含学号、姓名、性别、年龄等属性外，还包含了增加、删除、修改、查询等操作。
数据类型
数据类型是对一类数据的描述，它定义了数据的值域（数据的取值范围）、数据的操作（可对数据执行的操作），以及数据如何存储在计算机中的方式。数据类型确定了数据的基本属性和操作规则。
抽象数据类型（ADT）
抽象数据类型（Abstract Data Type）是数据类型的一种扩展，它不仅仅关注数据本身，还定义了对数据的操作，但是不关心数据的具体实现方式。抽象数据类型强调的是“如何操作数据”，而不是“数据是如何存储的”。
数据结构的分类
分解和抽象
数据结构的核心技术是分解和抽象。
通过分解划分出数据的层次；再通过抽象舍弃数据的具体内容得到数据的逻辑结构。
逻辑结构与存储结构
逻辑结构是根据问题需要建立的数据元素和它们之间的关系，完全不考虑具体如何实现。
存储结构是逻辑结构在计算机中的存储表示，是逻辑结构在计算机中的映像。
从用户角度能看到的只能是逻辑结构，所以所称的数据结构一般指的是逻辑结构。
逻辑结构的分类
- 线性结构
- 非线性结构
存储结构的分类
- 存取方式的不同
- 直接存取结构
- 顺序存储结构
- 索引结构
- 存储方式的不同
- 顺序存储方式
- 链接存储方式
- 索引存储方式
- 散列存储方式
- 选取存储结构的依据
- 访问频率
- 修改频率
- 安全保密
定义在数据结构上的操作
- 创建
- 销毁
- 查找
- 插入
- 删除
- 排序
- …
算法和算法设计
算法的基本定义和特性
- 有输入：0个或多个输入
- 有输出：1个或多个输出
- 确定性：算法的每一步都有确定的含义
- 有穷性：算法在执行有限步之后终止
- 可行性：算法的每一步都是可行的，能够通过已经实现的基本运算执行有限次完成
算法的设计步骤
- 理解需求
- 设计思路
- 算法框架
- 程序实现
算法设计的基本方法
- 穷举法
- 迭代法
- 递推法
- 递归法
算法的评价标准
- 正确性：算法是否能解决问题
- 健壮性：在不正确的输入下，算法是否能自我保护
- 可读性：算法和程序是否容易理解
- 高效性：算法是否能在合理的时间和空间内解决问题
- 简单性：采用的数据结构和算法是否简单，越简单出错的可能性越小
- 环路复杂度：程序中判断语句和子程序调用的总数 + 1
- 软件工程要求：环路复杂度不超过10
算法的计算复杂度
- 时间复杂度
- 空间复杂度
渐近分析，大O表示法
线性表
线性表的定义
线性表为 $n$ ($n \ge 0$) 个数据元素的有限序列。记为 $$L = (a_1, a_2, \cdots, a_i, \cdots, a_n)$$
其中 $L$ 为表名，$a_i$ 为表中的元素，是不可再分的源自数据，亦称为结点或记录。 $n$ 是表中元素的个数，称为表长。当 $n=0$ 时，称为空表。
线性表中的第一个元素称为 表头（head），最后一个元素称为 表尾（tail）。
线性表的特点
- 有穷性：线性表中元素个数有限。
- 有序性：线性表中元素有序，即元素之间存在一对一的前驱后继关系。
- 表中相邻的两个元素 $a_i, a_{i+1}$ 构成序对，$a_i$ 是 $a_{i+1}$ 的直接前趋，$a_{i+1}$ 是 $a_i$ 的直接后继。
- 存在唯一的第一个元素（表头）和最后一个元素（表尾）。
- 相同性：线性表中的元素类型相同。
顺序表
- 既可以顺序访问，也可以随机访问（即通过下标访问）。
- 通过数组实现，可以是静态数组或动态数组。
- 数组的大小要大于等于线性表的长度。
- 第 $i$ 个元素存储在第 $i - 1$ 个物理位置上，即数组下标为 $i - 1$ 的位置。
设顺序表的起始存储位置为 $LOC(1)$，第 $i$ 个元素的存储位置为 $LOC(i)$，则有： $$LOC(i) = LOC(1) + (i - 1) \times sizeof(DataType)$$
顺序表的性能
| 操作 | 时间复杂度 | 空间复杂度 | 操作 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|---|---|
初始化initList |
$O(1)$ | $O(1)$ | 清空clearList |
$O(1)$ | $O(1)$ |
求长度length |
$O(1)$ | $O(1)$ | 取值getElem |
$O(1)$ | $O(1)$ |
插入insert |
$O(n)$ | $O(1)$ | 删除delete |
$O(n)$ | $O(1)$ |
查找search |
$O(n)$ | $O(1)$ | 复制copyList |
$O(n)$ | $O(n)$ |
单链表
单链表是一种链式存储结构，由一系列结点组成。每个结点包括两部分：数据域data和指针域link。数据域存储数据元素，指针域存储下一个结点的地址。
链表中的最后一个节点没有后继，其指针域为 NULL。
单链表的特点
- 表中的数据元素的逻辑顺序和物理顺序不一定相同。
- 单链表的长度可以动态变化。
- 遍历和查找只能从头指针指示的第一个结点开始，逐个结点依次查找。
- 即不能随机访问，只能顺序访问。
- 插入和删除操作只需修改指针域，不需要移动结点。
- 由于链接表的每个结点带有指针域，所以占用的存储空间比顺序表大。
头节点：链表中第一个结点称为头节点，它是头指针指向的结点。头节点不存储数据，只是为了方便操作而引入的。
尾结点：链表中最后一个结点称为尾结点，为了方便插入到尾部而建立，其指针域为 NULL
单链表的性能
| 操作 | 时间复杂度 | 空间复杂度 | 操作 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|---|---|
初始化initList |
$O(1)$ | $O(1)$ | 清空clearList |
$O(n)$ | $O(1)$ |
求长度length |
$O(n)$ | $O(1)$ | 取值getElem |
$O(n)$ | $O(1)$ |
插入insert |
$O(n)$ | $O(1)$ | 删除delete |
$O(n)$ | $O(1)$ |
查找search |
$O(n)$ | $O(1)$ | 复制copyList |
$O(n)$ | $O(n)$ |
循环链表
循环链表是一种特殊的单链表，其尾结点指向首结点，形成一个环。
可以带头结点，也可以不带头结点。 若带头结点，遍历到头节点的时候需要跳过。
双向链表
拥有两个指针域lLink和rLink，分别指向前驱和后继。
顺序表和单链表的比较
存储方面
- 顺序表的存储密度高，存储密度为 $1$，而链表的存储密度小于 $1$。
- 顺序表的存储空间是静态分配的，链表的存储空间是动态分配的。
存取方面
- 顺序表支持随机存取，时间复杂度为 $O(1)$，而链表只支持顺序存取，时间复杂度为 $O(n)$。
- 插入和删除操作，顺序表的时间复杂度为 $O(n)$，链表的时间复杂度为 $O(1)$。
安全方面
在顺序表的情形，只要知道数组的名字和下标，就可以访问任何元素。
而在单链表中如果找不到结点的地址，结点所保护的数据就是安全的。
故单链表的安全保密性比顺序表好。
栈和队列
栈
栈是只允许在表的一端进行插入和删除操作的线性表，允许插入和删除的一端称为栈顶，另一端称为栈底。栈又称为后进先出（Last In First Out）的线性表，简称LIFO结构。
主要操作为：push、pop、getTop、isEmpty、isFull。
顺序栈
顺序栈是用顺序表实现的栈，栈顶指针 top 指向栈顶元素的位置。
由于数组的下标从 $0$ 开始，所以栈顶指针 top 初始化为 $-1$，判断栈空时 top 为 $-1$，判断栈满时 top 为数组的最大下标即 maxSize - 1。
push：先将元素入栈，再将栈顶指针top加一pop：将栈顶指针top减一即可isEmpty：判断栈空时top为 $-1$isFull：判断栈满时top为maxSize - 1
双栈共享空间
一个以左端为栈底，另一个以右端为栈底，两个栈共享一个数组空间。
多栈共享空间
- 初始平均分配空间
- 若一个栈满，需要将后边的所有元素右移一位，空出空间
链式栈
链式栈是用链表实现的栈，栈顶指针 top 指向栈顶元素的位置，栈底元素的指针域为 NULL。（无头结点）
初始化时，栈顶指针 top 为 NULL，判断栈空时 top 为 NULL。
应用
- 数值转化
- 括号匹配
- 表达式求值
- 递归
队列
队列是只允许在表的一端进行插入，而在另一端进行删除的线性表。允许插入的一端称为队尾，允许删除的一端称为队头。队列又称为先进先出（First In First Out）的线性表，简称FIFO结构。
主要操作为：push、pop、getFront、isEmpty、isFull。
顺序队列
使用数组实现的队列，队头指针 front 和队尾指针 rear 分别指向队头元素和队尾（即下一个入队元素的位置）。
当 front == rear 时，队列为空
当 rear - front == maxSize 时，队列满
push：先将元素入队，再将队尾指针rear加一pop：将队头指针front加一即可isEmpty：判断队列空时front == rearisFull：判断队列满时rear - front == maxSize
循环队列
在顺序队列的基础上，将队列的头尾相连，形成一个环形结构。
为了区别队列为空和队列满的情况，需要浪费一个存储单元。于是，队列的最大长度为 maxSize - 1。
push：先将元素入队，rear = (rear + 1) % maxSizepop：front = (front + 1) % maxSizeisEmpty：front == rearisFull：(rear + 1) % maxSize == front
链式队列
不含头结点以及尾指针的链表，队头指针 front 指向队头元素，队尾指针 rear 指向队尾元素。
push：需要特判队列为空的情况，此时需要修改队头指针frontpop：需要特判队列出队后为空的情况，此时需要修改队尾指针rear
应用
- 分层遍历（滚动数组）
数组和广义表
数组
- 数组是一种存储结构，是很多语言内建的数据类型。它的操作只有按下标读写。
- 数组是一种逻辑结构。
- 一维数组属于线性结构，但是不是线性表，因为数组中的元素虽然在存储结构上连续，但是在逻辑结构上不一定连续：即数组可以是稀疏的，也不需要顺序存取。一维数组被称为向量。
- 一维数组的元素属于不可分割的原子元素是时，是线性结构。
- 当它的元素为数组时，即多维数组时，是非线性结构。
一维数组
下标从 $0$ 开始，到 $n-1$ 结束，共有 $n$ 个元素。
$$LOC(a[i]) = LOC(a[0]) + i \times \text{sizeof}(a[0])$$
多维数组
二维数组
二维数组 $a[m][n]$ 的存储结构， $m$ 行 $n$ 列：
- 行优先存储： $$LOC(a[i][j]) = LOC(a[0][0]) + (i \times n + j) \times \text{sizeof}(a[0][0])$$
- 列优先存储： $$LOC(a[i][j]) = LOC(a[0][0]) + (j \times m + i) \times \text{sizeof}(a[0][0])$$
多维数组
多维数组 $a[m_1][m_2][\cdots][m_k]$ 的存储结构：
- 行优先存储： $$LOC(a[i_1][i_2][\cdots][i_k]) = LOC(a[0][0][\cdots][0]) + \left( \sum_{j=1}^{k} \left( \prod_{l=j+1}^{k} m_l \right) \times i_j \right) \times \text{sizeof}(a[0][0][\cdots][0])$$
- 列优先存储： $$LOC(a[i_1][i_2][\cdots][i_k]) = LOC(a[0][0][\cdots][0]) + \left( \sum_{j=1}^{k} \left( \prod_{l=1}^{j-1} m_l \right) \times i_j \right) \times \text{sizeof}(a[0][0][\cdots][0])$$
压缩矩阵
对称矩阵行优先压缩存储上三角矩阵
用一维数组存储对称矩阵 $a[n][n]$ 的元素，只存储主对角线及其上方的元素。
顺序是 a[0][0]、a[0][1]、a[0][2]、$\cdots$、a[0][n-1]、a[1][1]、a[1][2]、$\cdots$、a[1][n-1]、$\cdots$、a[n-1][n-1]。
$$LOC(a[i][j]) = \begin{cases} LOC(a[0][0]) + \frac{(n + n - i - 1) \times i}{2} + j - i & i \leq j \newline LOC(a[0][0]) + \frac{(n + n - j - 1) \times j}{2} + i - j & i > j \end{cases}$$
对称矩阵列优先压缩存储下三角矩阵
用一维数组存储对称矩阵 $a[n][n]$ 的元素，只存储主对角线及其下方的元素。
顺序是 a[0][0]、a[1][0]、a[1][1]、a[2][0]、a[2][1]、a[2][2]、$\cdots$、a[n-1][0]、a[n-1][1]、$\cdots$、a[n-1][n-1]。
$$LOC(a[i][j]) = \begin{cases} LOC(a[0][0]) + \frac{i \times (i + 1)}{2} + j & i \geq j \newline LOC(a[0][0]) + \frac{j \times (j + 1)}{2} + i & i < j \end{cases}$$
三对角矩阵
用一维数组存储三对角矩阵 $a[n][n]$ 的元素，只存储主对角线及其上下相邻的两条对角线的元素。
顺序是 a[0][0]、a[0][1]、a[1][0]、a[1][1]、a[1][2]、a[2][1]、a[2][2]、$\cdots$、a[n-2][n-2]、a[n-2][n-1]、a[n-1][n-2]、a[n-1][n-1]。
主要讨论行优先存储的情况：
从矩阵到一维数组
$$LOC(a[i][j]) = (3 \times i - 1) + (j - i + 1) = 2 \ times i + j$$
从一维数组到矩阵
$$\begin{aligned}
i &= \left\lfloor \frac{k + 1}{3} \right\rfloor \newline
j &= k - 2 \times i
\end{aligned}$$
稀疏矩阵
设在一个 $m$ 行 $n$ 列的矩阵中，有 $t$ 个非零元素，定义稀疏因子： $$\delta = \frac{t}{m \times n}$$ 通常当这个值小于 $0.05$ 时，称为稀疏矩阵。
三元组表
采用三元组 $(i, j, e)$ 表示矩阵中的非零元素，其中 $i$ 为行号，$j$ 为列号，$e$ 为元素值。 在数组中按照行优先存储，即先存储第一行的元素，再存储第二行的元素，以此类推。
矩阵转置
|
|
链表表示
用链表表示稀疏矩阵，可以在运算的过程中有效地动态调整矩阵的大小。
简单链式存储
链表的每个结点是一个四元组 $(i, j, e, \text{next})$
虽然有利于插入和删除操作，但是失去了矩阵的灵活性。
行链表组
每一行用一个链表表示，链表的每个结点是一个三元组 $(j, e, \text{next})$ 共有 $m$ 个头指针，指针域指向每一行的第一个非零元素。
十字链表
每个非零元素是一个六元组 $(head, i, j, down, value, right)$ 分别记录了是否为头指针、行号、列号、在下面的第一个非零元素、元素值、在右边的第一个非零元素。
行和列共享同一个头指针结点， $right$ 表示的是第 $i$ 行的 第一个非零元素， $down$ 表示的是第 $i$ 列的第一个非零元素。
广义表
$$LS = (\alpha_1, \alpha_2, \cdots, \alpha_n)$$ $$\alpha_i = \begin{cases} (a_1, a_2, \cdots, a_m) & \text{广义表} \newline e & \text{原子元素} \end{cases}$$
广义表的定义是 递归 的。 当每个元素均为原子元素且类型相同时，广义表即为线性表。
- 表头：第一个元素，是一个原子元素或者广义表。
- 表尾：除去表头之外的部分，是一个广义表。
- 表长：广义表中最外层的元素个数。
- 深度：广义表中括号 最深 的层数。原子元素的深度为 $0$，$()$ 的深度为 $1$。
广义表的性质
- 有次序性：广义表中元素之间有次序关系。
- 有长度：广义表中元素的个数称为广义表的长度。
- 有深度：广义表中元素的嵌套层数称为广义表的深度。
- 可递归：广义表本身可以是自己的子表。
- 可共享：广义表可以被其他子表共享。
广义表的链接表示
头尾表示
广义表 = 表头 + 表尾
tag：标志域，表示当前元素是原子元素还是广义表。value：值域，存储原子元素的值。hlink，tlink：指针域，分别指向表头和表尾。
每个指针指向的都是一个广义表的头结点，即先在剩下的元素外面加上一层括号。
扩展的线性链表
和头尾表示类似，只不过原子元素也存储了 tlink 指针。
扩展的线性链表的指针直接指向下一个元素，而不是指向广义表的头结点。
层次链表
结合了上述两种表示方法，拥有头指针以及指向下一个元素的指针。
树和二叉树
树
一棵树是 $n(n \geq 0)$ 个结点的有限集合，非空树满足： $$T = {r, T_1, T_2, \cdots, T_m}$$ 其中 $r$ 为树的根结点，$T_1, T_2, \cdots, T_m$ 为 $m$ 棵互不相交的子集合，每个子集合本身又是一棵树，称为 $r$ 的子树。
$n = 0$ 时，树为空树。
基本术语
-
结点：树中的每个元素称为结点。包含一个数据元素的值和若干指向结点的指针。
-
结点的度：结点的子树个数。
-
叶结点：度为 $0$ 的结点。又称为终端结点。
-
分支结点：除叶结点外的结点。又称为非终端结点。
-
子女结点：结点的子树的根结点称为该结点的子女结点。
-
双亲结点：若结点 $y$ 是结点 $x$ 的子女结点，则结点 $x$ 是结点 $y$ 的双亲结点。
-
兄弟结点：同一双亲结点的子女结点之间互称为兄弟结点。
-
祖先结点：从根结点到该结点的路径上的所有结点。
-
子孙结点：以某结点为根的子树中除了根结点之外的所有结点。
-
结点间的路径：从一个结点到另一个结点的分支构成的序列 $v_i, v_1, v_2, \cdots, v_k, v_j$。
-
结点的深度：即结点到根结点的路径长度 + 1，根结点的深度为 $1$。
-
结点的高度：空树的高度为 $0$，叶结点的高度为 $1$，非叶结点的高度为其所有子女结点的最大高度 + 1。
-
树的深度：树中所有结点的最大深度。
-
树的高度：根结点的高度。树的高度与树的深度相等。
-
树的宽度：树中各层结点的最大个数。
-
树的度：树中结点的最大度数。
-
有序树：树中结点的各子树 $T_1, T_2, \cdots$ 有序排列。其中 $T_1$ 是第一个子树，$T_2$ 是第二个子树，$\cdots$。
-
无序树：树中结点的各子树 $T_1, T_2, \cdots$ 无序排列，各棵子树之间的顺序不重要。
-
森林：$m(m \geq 0)$ 棵互不相交的树的集合。
二叉树
二叉树是具有 $n(n \geq 0)$ 个结点的有限集合，该集合或者为空集，或者由一个根结点和两棵互不相交的、分别称为根结点的左子树和右子树的二叉树组成。 $$T = \begin{cases} \varnothing & n = 0 \newline \lbrace r, T_L, T_R \rbrace & n > 0 \end{cases}$$
tips:
- 二叉树不是树，是一种树形结构。
- 二叉树都具有左右子树，只不过有的子树为空。
二叉树的性质
- 在二叉树的第 $i$ 层上至多有 $2^{i-1}$ 个结点。
- 深度为 $k$ 的二叉树至多有 $2^k - 1$ 个结点，最少有 $k$ 个结点。
- 对于任何一棵二叉树，如果其叶结点数为 $n_0$，度为 $2$ 的结点数为 $n_2$，则 $n_0 = n_2 + 1$。
特殊二叉树
- 满二叉树：每个结点要么是叶结点，要么有两个子女结点。
- 满二叉树的叶结点数 $n_0 = n_2 + 1$。
- 满二叉树的结点总数 $n = 2^{h+1} - 1$，其中 $h$ 为树的高度。
- 完全二叉树：若设二叉树的高度为 $h$，除第 $h$ 层外，其它各层的结点数都达到最大个数，第 $h$ 层的结点都连续集中在最左边。
- 完全二叉树的高度 $h = \lceil \log_2 (n+1) \rceil$（当 $n = 0$ 时不满足式子 $h = \lfloor \log_2 n \rfloor + 1$ ）。
二叉树的存储结构
顺序存储结构
- 完全二叉树：按照层次顺序存储，从上到下，从左到右，下标从 $0$ 开始。
- 一般二叉树：按照完全二叉树的方式存储，空结点用特殊值表示。
链式存储结构
每个结点至少含有三个域：lchild、data、rchild。（此时为二叉链表）
若需要快速找到其双亲结点，可以增加一个域 parent。（此时为三叉链表）
广义表表示
A(B(D,E),C(,F)) 表示如下二叉树：
A
/ \
B C
/ \ \
D E F
二叉树的遍历
- 先序遍历：根结点 -> 左子树 -> 右子树
- 中序遍历：左子树 -> 根结点 -> 右子树
- 后序遍历：左子树 -> 右子树 -> 根结点
- 层次遍历：从上到下，从左到右
遍历的应用
- 先序遍历：复制二叉树、求二叉树的深度、输出二叉树的括号表示法、输出二叉树的前缀表达式。
- 字符串
ABD##E##C#F##表示如下二叉树：
- 字符串
A
/ \
B C
/ \ \
D E F
- 中序遍历：输出二叉树的中缀表达式。
- 后序遍历：释放二叉树的空间，输出二叉树的后缀表达式。
单纯应用先序遍历或者中序遍历可以直接确定完全二叉树的结构。
需要结合先序遍历和中序遍历或者中序遍历和后序遍历才能确定一般二叉树的结构。
先序遍历和后序遍历无法确定二叉树的结构。
以下结论也是成立的：
用二叉树的中序序列和层次序序列可以唯一确定一棵二叉树。
用二叉树的中序序列和各结点所处层次可以唯一确定一棵二叉树。
用二叉树的中序序列和各结点的左子女可以唯一确定一棵二叉树。
用二叉树的中序序列和各结点的右子女可以唯一确定一棵二叉树。
用二叉树的先序序列和各结点的右子女可以唯一确定一棵二叉树。
用二叉树的后序序列和各结点的左子女可以唯一确定一棵二叉树。
二叉树的计数
当先序遍历序列为 $1, 2, 3, \cdots, n$ 时，可以构造出多少种不同的二叉树？ $$b_n = \begin{cases} 1 & n = 0 \newline \displaystyle\sum_{i=0}^{n-1} b_i \times b_{n-1-i} & n > 0 \end{cases}$$ 卡特兰数： $$\mathcal{C}_n = \frac{1}{n+1} \binom{2n}{n}$$
线索二叉树
线索二叉树的结点会增加两个域：pred 和 succ，分别指向某个遍历次序下的前驱和后继结点。
也可以采用 ltag 和 rtag 两个域参数，分别表示左右指针是否指向子女结点还是前驱后继结点。
ltag 和 rtag 为 0 时，表示指向子女结点；为 1 时，表示指向前驱后继结点。
- 前序遍历：前驱是双亲结点，后继是右子女结点。
- 后序遍历：前驱是左子女结点，后继是双亲结点。
树与森林
三种存储结构
双亲表示法
每个结点都有一个指向双亲结点的指针域。
子女链表表示法
每个结点都存有一个链表，以第一个子女结点为头结点，其余子女结点依次排列。
子女-兄弟表示法
每个结点存储两个指针域，一个指向第一个子女结点，一个指向下一个兄弟结点。
是最省空间的存储的表示方式。
广义表表示法
R(A(D, E), B, C(F(G, H, K))) 表示如下树：
R
/|\
A B C
/ \ \
D E F
/|\
G H K
树与森林转化为二叉树
树转化为二叉树
将 “子女-兄弟表示法” 中的每个结点的子女结点看作其左子女结点，其兄弟结点看作其右子女结点。
森林转化为二叉树
将森林中树的根看作兄弟，再用树转化为二叉树的方法。
二叉树转化为树与森林
采用上述方法的逆过程。 转化成的树与森林是唯一的。
树与森林的遍历
树的遍历
- 先序遍历：根结点 -> 第一个子女结点 -> 第一个子女结点的子树 -> 第二个子女结点 -> 第二个子女结点的子树 -> $\cdots$
- 后序遍历：第一个子女结点 -> 第一个子女结点的子树 -> 第二个子女结点 -> 第二个子女结点的子树 -> $\cdots$
- 层次遍历：从上到下，从左到右
树的先序遍历与其转化成二叉树后的先序遍历是一致的。 树的后序遍历与其转化成二叉树后的中序遍历是一致的。
森林的遍历
- 先根次序遍历：对每一课树进行先序遍历。
- 中根次序遍历：对每一课树进行后序遍历。
- 层次遍历：从上到下，从左到右，不要每棵树单独解决，而是将森林看作一个树（忽略最外层的根结点）。
| 森林 | 树 | 二叉树 |
|---|---|---|
| 先根次序遍历 | 先序遍历 | 先序遍历 |
| … | 中序遍历 | … |
| 中根次序遍历 | 后序遍历 | 中序遍历 |
Huffman 树
带权路径长度
树的路径长度（Path Length）是从树的根结点到每个结点的路径长度之和。 树的带权路径长度（Weighted Path Length，WPL）是树的路径长度与结点的权值的乘积之和。即： $$WPL = \sum_{i=1}^n w_i \cdot l_i$$
扩充二叉树
给定一个具有 $n$ 个权值的集合 $W = \lbrace w_1, w_2, \cdots, w_n \rbrace$，和一棵具有 $n$ 个叶结点的二叉树，将 $w_1, w_2, \cdots, w_n$ 依次赋值给这棵二叉树的叶结点，得到的二叉树称为扩充二叉树。
带有权值的叶节点称为扩充二叉树的外结点。 其余不带权值的分支结点称为扩充二叉树的内结点。 定义：扩充二叉树的带权路径长度是从根结点到每个外结点的长度路径与该结点上的权值乘积之和。即 $$WPL = \sum_{i=1}^n w_i \cdot l_i$$
在权值为 $w_1, w_2, \cdots, w_n$ 的扩充二叉树中，其 $WPL$ 最小的二叉树称为最优二叉树或Huffman 树。
Huffman 树的构造
- 将 $n$ 个权值看作 $n$ 棵只有一个结点的二叉树。
- 选取两个根结点的权值最小的二叉树进行合并，生成一棵新的二叉树，其根结点的权值为两个根结点的权值之和。
- 删除原来的两个二叉树，将新生成的二叉树加入到二叉树集合中。
- 重复步骤 2 和 3，直到只剩下一棵二叉树为止。
Huffman 编码
Huffman 编码是一种变长编码，根据字符出现的频率来确定其编码。
左分支为 0，右分支为 1。
用平均编码长度 $\displaystyle\sum_{i=1}^n p_i \cdot l_i$ 来衡量编码的效率。
由于构造 Huffman 树的过程中，选取左右子树的顺序是任意的，所以 Huffman 编码不是唯一的。
堆
以完全二叉树的顺序存储结构来存储的一种特殊的二叉树。
- 大根堆：每个结点的值都大于或等于其左右子结点的值。
- 小根堆：每个结点的值都小于或等于其左右子结点的值。
图
图的基本概念
图的定义
图是由顶点集合及顶点之间的关系集合组成的一种数据结构： $$G=(V,E)$$ 其中，$V = \lbrace x \ | \ x \in \text{某个数据集} \rbrace$ 是有穷非空集合，叫做顶点集合；$E = \lbrace (x,y) \ | \ x,y \in V \rbrace$ 或 $E = \lbrace <x,y> \ | \ x,y \in V and Path(x, y) \rbrace$ 是顶点之间的关系的有穷集合，又叫边集合。 $Path(x, y)$ 表示从 $x$ 到 $y$ 的一条单向通路。
如果图中所有的顶点对 $<x,y>$ 是有序的，则称为有向图。对于有向边 $<x,y>$，称 $x$ 为始点，$y$ 为终点。 如果图中所有的顶点对 $(x,y)$ 是无序的，则称为无向图。
- 不考虑自环。
- 不考虑重边。
有关图的术语
- 权值：边上的数值。
- 网络：边上带有权值的图。
- 邻接顶点：与某一顶点直接相连的顶点。
- 若 $(u, v) \in E$，则称 $u$， $v$ 互为邻接顶点。
- 若 $<u, v> \in E$，则称 $u$ 邻接到 $v$，$v$ 邻接自 $u$。
- 子图：$G’ = (V’, E’)$ 是 $G = (V, E)$ 的子图，当且仅当 $V’ \subseteq V$ 且 $E’ \subseteq E$。
- 度： $deg(v)$
- 有向图：$inde(v)$ 入度，$outde(v)$ 出度，$deg(v) = inde(v) + outde(v)$
- 无向图：$deg(v)$
- $e = \frac{1}{2} \sum_{v \in V} deg(v)$
- 稠密图和稀疏图
- 稠密图：$e \ge nlog_2n$
- 稀疏图：$e < nlog_2n$
- 完全图：每两个顶点之间都有边的图。
- 路径：$v_1, v_2, \cdots, v_n$，$<v_i, v_{i+1}> \in E$
- 路径长度：
- 无权图：路径上边的条数。
- 有权图：路径上边权值之和。
- 简单路径：除了起点和终点外，其余顶点不重复。
- 回路：起点和终点相同的路径。
- 简单回路：回路是简单路径。
- 路径长度：
- 连通图：无向图中任意两个顶点之间都有路径。
- 连通分量：非连通图的极大连通子图。
- 强连通图：有向图中任意两个顶点之间都有路径。
- 强连通分量：非强连通图的极大强连通子图。
- 生成树：无向连通图的极小连通子图。
- 连通有向图可能没有生成树，但有生成森林。
图的存储结构
邻接矩阵
图 $A = (V, E)$ 包含 $n$ 个顶点，则其邻接矩阵是一个二维数组 $A.E[n][n]$，其中 $$A.E[i][j] = \begin{cases} 1 & \text{若} (v_i, v_j) \in E \text{或} <v_i, v_j> \in E \newline 0 & \text{其他} \end{cases}$$
带权图的邻接矩阵： $$A.E[i][j] = \begin{cases} 0 & \text{若} i = j \newline W(i, j) & \text{若} (v_i, v_j) \in E \text{或} <v_i, v_j> \in E \newline \infty & \text{其他} \end{cases}$$
邻接表
对于每个顶点 $v_i$，用一个链表存储一个边链表。
Vnode：data、adj，顶点结点，包含一个指向边链表首结点的指针。（即为链表的头指针）Enode：dest、link，边结点，包含一个指向下一个边结点的指针。
采用头插法，所以链表是逆序的。（链式前向星）
邻接多重表
用于无向图，每条边用一个边结点表示。
边结点存储 mark、vertex1、vertex2、path1、path2。
mark：标记是否访问过。vertex1、vertex2：两个顶点。path1、path2：两个顶点的下一个边结点。
因此最后只需要存 $e$ 个边结点。
顶点结点与邻接表相同。
十字链表
用于有向图的逆序存储。
Vnode：data、firstin、firstout，顶点结点。firstin：指向以该顶点为终点的边。firstout：指向以该顶点为始点的边。
Enode：mark、vertex1、vertex2、path1、path2，边结点。
图的遍历
- 深度优先搜索
- 广度优先搜索
联通分量
dfs 遍历图，对于每个未访问的顶点，进行一次 dfs，得到一个联通分量。
最小生成树
- 恰好用 $n-1$ 条边连接 $n$ 个顶点。
- 无向连通图的极小连通子图。
- 权值和最小的生成树。
Kruskal 算法
- 将图中所有边按权值从小到大排序。
- 从小到大选择边，若该边的两个顶点不在同一连通分量中，则选择该边。
- 直到所有顶点都在同一连通分量中。
- 若边数小于 $n-1$，则不存在最小生成树。
Prim 算法
- 任选一个顶点作为起点，将其加入生成树。
- 从生成树中的顶点出发，选择权值最小的边，将其连接的顶点加入生成树。
- 更新生成树中的最小权值边以及顶点集合。
最短路径
Dijkstra 算法
- 初始化 $dis$ 数组，$dis[i]$ 表示从起点到顶点 $i$ 的最短路径长度。
- 从起点开始，每次选择当前未访问的顶点中距离起点最近的顶点，更新其邻接顶点的最短路径长度。
- 直到所有顶点都访问过。
- 若 $dis$ 数组中有顶点的值为 $\infty$，则该顶点不可达。
Dijkstra 算法适用于权值非负的图。
Bellman-Ford 算法
- 初始化 $dis$ 数组，$dis[i]$ 表示从起点到顶点 $i$ 的最短路径长度。
- 对每条边进行松弛操作。
- 重复 $n-1$ 次。
- 若第 $n$ 次仍然有边可以松弛，则存在负权回路。
- 若 $dis$ 数组中有顶点的值为 $\infty$，则该顶点不可达。
Bellman-Ford 算法适用于权值为任意值的图。
Floyd 算法
- 初始化 $dis$ 数组，$dis[i][j]$ 表示从顶点 $i$ 到顶点 $j$ 的最短路径长度。
- 先枚举中间点，再枚举起点和终点，更新最短路径长度。
BFS
无权图的最短路径可以使用 BFS 求解。
活动网络
AOV 网络与拓扑排序
用顶点表示活动，用边表示活动之间的先后关系的有向图称为活动网络（Activity On Vertex Network，AOV 网络）。
$<v_i, v_j>$ 表示活动 $v_i$ 必须在活动 $v_j$ 之前完成。
AOV 网络中不能有回路，这种图称为有向无环图（Directed Acyclic Graph，DAG）。
使用拓扑排序解决 AOV 网络中的活动排序问题。
- 书中采用栈实现拓扑排序。
AOE 网络与关键路径
用边表示活动，用顶点表示事件的有向图称为事件网络（Activity On Edge Network，AOE 网络）。 $<v_i, v_j, w>$ 表示活动 $v_i$ 到活动 $v_j$ 需要 $w$ 的时间。
整个工程只有一个开始点（入度为 $0$），称为源点；只有一个结束点（出度为 $0$），称为汇点。
从源点到汇点的最长路径称为关键路径
- $V_e$ ：事件最早发生时间，即先序事件的最晚发生时间。
- $V_l$ ：事件最迟发生时间，即总时间减去后序事件的最早发生时间。
- $A_e$ ：活动最早开始时间，即先序活动的最晚开始时间。 $A_e(<j, k>) = V_e(j)$
- $A_l$ ：活动最迟开始时间，即后序活动的最早开始时间。 $A_l(<j, k>) = V_l(k) - w(j, k)$
关键路径上的活动有 $A_e = A_l$。
使用拓扑排序解决 AOE 网络中的关键路径问题。 $$V_e(\text{源点}) = 0, \quad V_l(\text{汇点}) = V_e(\text{汇点})$$ $$V_e(j) = \max\lbrace V_e(i) + w(i, j) \rbrace$$ $$V_l(j) = \min\lbrace V_l(k) - w(j, k) \rbrace$$
查找
查找的基本概念
- 查找：在一个数据集合中找出满足某种条件的数据元素。
- 查找表：用于查找的数据集合，由同一类型的数据元素构成。
- 静态查找表：查找表执行插入或删除操作时，查找表的结构不发生变化。
- 动态查找表：查找表执行插入或删除操作时，查找表的结构发生变化，为保持较高的查找效率，需要动态调整查找表的结构。
- 关键码：可唯一标识数据元素的数据项。
查找的性能分析
$$ASL_{\text{成功}} = \sum_{i=0}^{n-1} p_i \cdot c_i$$
顺序查找
不设监视哨： $$ASL_{\text{成功}} = \frac{n+1}{2}$$ $$ASL_{\text{不成功}} = n$$ 设置监视哨 $n$： $$ASL_{\text{成功}} = \frac{n+1}{2}$$ $$ASL_{\text{不成功}} = n+1$$
有序顺序表的顺序查找
$$ASL_{\text{成功}} = \frac{n+1}{2}$$ $$ASL_{\text{不成功}} = \frac{1}{n+1} \left(\sum_{i=0}^{n - 1}(i+1) + n\right) = \frac{n}{2} + \frac{n}{n+1}$$
折半查找
使用折半查找进行的查找次数为 $\lceil \log_2 (n+1) \rceil$。 即为 $n$ 个结点的完全二叉树的深度。
二叉查找树
二叉查找树又称二叉排序树，是一棵空树或者具有以下性质的二叉树：
- 每个节点都有一个关键码，所有节点的关键码互不相同。
- 若左子树不空，则左子树上所有节点的关键码均小于根节点的关键码。
- 若右子树不空，则右子树上所有节点的关键码均大于根节点的关键码。
- 左右子树也分别为二叉查找树。
对于二叉查找树 $T$，其中序遍历序列是一个递增序列。
二叉查找树的查找
二叉查找树的插入
二叉查找树的删除
- 有一棵子树为空，则将双亲结点链接到非空子树上。
- 两棵子树都不为空，找到右子树的最小关键码结点（即右子树的最左结点），或者左子树的最大关键码结点（即左子树的最右结点）替换被删除结点。
AVL 树
AVL 树是一种自平衡二叉查找树，任意结点的左右子树的高度差不超过 1。
平衡因子：结点的左子树的高度减去右子树的高度。
- RR 型：右子树的右子树的深度更大导致的不平衡，需要左单旋转，即将右子树的根结点作为根结点，原根结点作为右子树的左子，原右子树的左子树作为原根结点的右子树。
- LL 型：左子树的左子树的深度更大导致的不平衡，需要右单旋转，即将左子树的根结点作为根结点，原根结点作为左子树的右子树，原左子树的右子树作为原根结点的左子树。
- LR 型：左子树的右子树的深度更大导致的不平衡，需要先左后右旋转，即先对左子树进行左旋转，再对根结点进行右旋转。
- RL 型：右子树的左子树的深度更大导致的不平衡，需要先右后左旋转，即先对右子树进行右旋转，再对根结点进行左旋转。
AVL 树的插入
按照二叉查找树的插入方法插入结点，然后从插入结点到根结点的路径上，检查每个结点的平衡因子，若不平衡，则进行旋转操作。
AVL 树的删除
按照二叉查找树的删除方法删除结点（先采用中序前驱然后再采用中序后继），然后从删除结点到根结点的路径上，检查每个结点的平衡因子，若不平衡，则进行旋转操作。
B 树
索引顺序表
当数据量比较大的时候可以多开辟一个索引表，存储某个数据元素的地址。
-
稠密索引：一个索引项对应数据表中一个元素。当元素在外存中按加入顺序存放而不是按关键码值有序存放时必须采用稠密索引，这时的索引结构叫做索引非顺序结构。
-
稀疏索引：当元素在外存中有序存放时，可以把所有 $n$ 个元素分为 $b$ 个子表（块）存放，一个索引项对应数据表中一组元素（子表）。第i个索引项是第i个子表的索引项，$i=0,1,\cdots,n-1$。这种索引结构叫做索引顺序结构。
稠密索引：
| 学号 | 地址 |
|---|---|
| 1001 | 位置1 |
| 1002 | 位置2 |
| 1003 | 位置3 |
| 1004 | 位置4 |
稀疏索引：
| 学号 | 组别 | 地址 |
|---|---|---|
| 1001 | 1 | 位置1, 位置2 |
| 1002 | 1 | 位置1, 位置2 |
| 1003 | 2 | 位置3, 位置4 |
| 1004 | 2 | 位置3, 位置4 |
分块查找
分块查找是一种索引顺序表的查找方法，将数据表分为若干块，每一块中的元素可以是无序的，但是块之间是有序的。 要求 $ID[i - 1].max _- key < ID[i].min _- key$。
多级索引与 m 叉查找树
树中每一个分支结点表示一个索引块，每个索引项给出各子树结点的最大关键码值和结点的地址。
B 树
B 树（也称 B-树）是一种高度平衡的 m 叉查找树，每个结点最多有 $m$ 个子女，最少有 $\lceil m/2 \rceil$ 个子女，根节点最少有 $2$ 个子女。 结点的关键码个数为 $n-1$，关键码按照递增顺序排列。 每个关键码的左子树中的所有关键码小于该关键码，右子树中的所有关键码大于该关键码。 最后一层结点称为叶子结点，其余结点称为内部结点。 查找失败时到达的结点称作失败结点，所有的失败结点都是空结点。
B 树的查找
顺序查找或折半查找结点的关键码，若找到则返回，否则若处于两个关键码之间，则进入对应的子树继续查找。
B 树的插入
插入需要插入到叶子结点，若插入后关键码个数超过 $m-1$，则需要进行分裂操作，将中间关键码（第 $\lceil m/2 \rceil$ 个）上移，左右两部分分别作为两个新结点。
B 树的删除
类似于二叉树的删除，需要用中序前驱或者中序后继替换被删除结点，然后删除中序前驱或者中序后继。 中序前驱或者中序后继一定是叶子结点。
若删除后关键码个数小于 $\lceil m/2 \rceil - 1$，则需要进行合并操作，将两个结点合并为一个结点：
- 若兄弟结点关键码个数大于 $\lceil m/2 \rceil - 1$，则从兄弟结点借一个关键码。
- 先将二者父节点的关键码下移至当前结点，再将兄弟结点的关键码上移至父节点。
- 否则将当前结点与兄弟结点合并，二者的父节点关键码下移至合并后的结点。
B+ 树
由于 B 树顺序遍历索引时需要中序遍历整个树，因此开发了 B+ 树。
B+ 树是 B 树的一种变形，其内部结点不存储数据，只存储索引，叶子结点存储数据。
用分块索引的方式，每一层的索引块中存储的是下一层的叶子结点的最大关键码值。
与 B 树 不同的是，要求节点内存储的关键码个数为 $n$，而不是 $n-1$，因此每个节点内的关键码直接对应数据块。
在 B+ 树中，叶子结点之间通过指针相连，形成一个有序链表。
散列表
$$Address = hash(key)$$
散列函数
直接定址法
$$hash(key) = a \cdot key + b$$
会造成较多空间的浪费，在不压缩的情况下，不会产生冲突。
除留余数法
$$hash(key) = key \mod p$$ $p$ 是一个不大于散列表长度的质数。
数字分析法
均匀度： $$\lambda_k = \sum_{i=0}^{r}(a_i^k - n / r)^2$$ 选择 $\lambda_k$ 最小的几位作为散列地址。
显然，数字分析法仅适用于事先明确知道表中所有关键码每一位数值的分布情况，它完全依赖于关键码集合。如果换一个关键码集合，选择哪几位需要重新分析，寻找分布均匀的若干位作为散列地址。
平方取中法
取平方后的中间几位作为散列地址。
折叠法
先将关键码分割成位数相等的几部分，然后将这几部分叠加，取叠加后的结果的低 $r$ 位作为散列地址。
- 移位法：最右端对齐相加。
- 分界法：交替反序，最右端对齐相加。
解决冲突的开地址法
开地址法又称闭散列法，指的是当新元素与表中已有元素冲突时，可以将新元素插入到表中的其他位置。但无论怎样都只能在表内找下一个空闲位置。
线性探测法
向后探测直到找到空闲位置。 $$H_i = (H_0 + i) \mod m$$ $m$ 是散列表长度，当采用 除留余数法， $m$ 不为取的质数而为散列表长度。
线性探查方法容易产生“堆积（又称为聚集）”的问题，即不同探查序列的关键码占据了可利用的空闲地址，使得为寻找某一关键码不但需要经历同义词的探查序列，还要经历其他非同义词元素的探查序列，导致查找效率降低。
二次探测法
$$H_i = (H_0 \pm i^2) \mod m$$ $m$ 是散列表长度，它应该是一个值为 $4k+3$ 的素数。
双散列法
$$H_i = (hash(key) + i \cdot hash_-random(key)) \mod m$$ 其中 $hash_-random(key)$ 是一个与关键码 $key$ 相关的伪随机数， $gcd(hash_-random(key), m) = 1$。
$hash_-ramdom$ 的取法很多，当 $m$ 为素数时，可以取 $$hash_-ramdon(key) = \begin{cases} key \mod (m - 1) + 1 \newline\lfloor key / m \rfloor \mod (m - 2) + 1 \newline\cdots \end{cases}$$
解决冲突的链地址法
将 $hash(key)$ 相同的元素存储在同一个链表中。
散列表的性能分析
$$\alpha = \frac{\text{表中已装有的元素个数} n }{\text{表中预设的最大记录数} m}$$
$\alpha$ 称为装填因子，它反映了散列表中元素的密度。
链地址法优于开地址法，除留余数法优于其他散列函数。
排序
排序的相关概念
- 数据表：待排序的数据元素的集合。通常组织为顺序表、静态链表、动态链表等形式，也可以用完全二叉树的顺序组织。
- 排序码：数据元素中的某个数据项，作为排序依据的属性。
- 排序的确切定义：设含有含有 $n$ 个元素的序列为 $R_0, R_1, \cdots, R_{n-1}$，$R_i$ 的排序码为 $K_i$，排序的目的是使得确定 $0, 1, \cdots, n-1$ 的一个排列 $p$，使得 $$K_{p(0)} \leq K_{p(1)} \leq \cdots \leq K_{p(n-1)}$$ 或 $$K_{p(0)} \geq K_{p(1)} \geq \cdots \geq K_{p(n-1)}$$
- 原地排序：只用了规模为 $O(1)$ 的辅助空间，排序结果仍然在原来的存储空间中。
- 稳定性：排序后相同关键字的元素的相对位置不变。
- 排序方法分类
- 有序区增长：将数据表分为有序区和无序区，在排序过程中逐步扩大有序区，缩小有序区，直到整个数据表有序。
- 有序程度增长：不能明确区分有序区和无序区，而是逐步增加有序程度。
- 内排序与外排序
- 内排序：整个排序过程在内存中完成。
- 外排序：数据量太大，无法一次性装入内存，需要借助外存进行排序。
- 静态排序与动态排序
- 静态排序：数据表在排序过程中不涉及插入、删除等操作，仅交换元素位置。
- 动态排序：数据表在排序过程中可能会有插入、删除等操作。常见于动态链表和树形结构。
数据表
与本书中定义的顺序表不同，下标从 $0$ 开始，到 $n-1$ 结束，共有 $n$ 个元素。
插入排序
直接插入排序
假设 $0 \cdots i-1$ 已经有序，将 $i$ 插入到有序区间中。
|
|
直接插入排序的时间复杂度为 $O(n^2)$，空间复杂度为 $O(1)$，是稳定的排序算法。
折半插入排序
在直接插入排序的基础上，使用二分查找找到插入位置。
|
|
比较次数为 $O(n \log n)$，移动次数为 $O(n^2)$，时间复杂度为 $O(n^2)$，空间复杂度为 $O(1)$，是稳定的排序算法。
希尔排序
|
|
希尔排序的时间复杂度基于增量序列的选择。 让 $gap = 2^k - 1, 2^{k - 1} - 1, \cdots, 7, 3, 1$，在最坏情况下最好，理论上证明可达到 $O(n^{3/2})$ ，实际模拟结果可达到 $O(n^{5/4})$。
交换排序
起泡排序
|
|
起泡排序的时间复杂度为 $O(n^2)$，空间复杂度为 $O(1)$，是稳定的排序算法。
快速排序
|
|
快速排序的平均时间复杂度为 $O(n \log n)$，最坏时间复杂度为 $O(n^2)$，平均空间复杂度为 $O(\log n)$，最坏空间复杂度为 $O(n)$，是不稳定的排序算法。
优化
快速-插入排序
|
|
选基准记录的三者取中快速算法
|
|
选择排序
简单选择排序
|
|
锦标赛排序
进行 $\lceil \log_2 n \rceil$ 次比赛，每次比赛选出胜者，上升。 决出冠军后，将其置为正无穷，进行下一轮比赛。 每次比赛的时间复杂度为 $O(n)$，总的时间复杂度为 $O(n \log n)$。 空间复杂度为 $O(n \log_2 n)$，是不稳定的排序算法。
堆排序
|
|
堆排序的时间复杂度为 $O(n \log n)$，空间复杂度为 $O(1)$，是不稳定的排序算法。
归并排序
二路归并排序
|
|
归并排序的时间复杂度为 $O(n \log n)$，空间复杂度为 $O(n)$，是稳定的排序算法。
基数排序
MSD 基数排序
Most Significant Digit，从高位到低位进行排序。 所以是递归的，每次递归对某一位进行排序。
|
|
LSD 基数排序
Least Significant Digit，从低位到高位进行排序。 共进行 $d$ 轮排序，每次排序后，将链表重新连接。
|
|
基数排序的时间复杂度为 $O(d(n + radix))$，空间复杂度为 $O(n + radix)$，是稳定的排序算法。
排序的下界
比较排序的下界
判定树模型：将排序算法的比较过程抽象为一棵二叉树，树的每个非叶结点表示一次比较，每个叶结点表示一种排序结果。 共有 $n!$ 种叶节点，所以最少需要 $\lceil \log_2 n! \rceil >= (n / 2) \times ( \log_2 n - 1)$ 次比较。即比较排序的下界为 $\Omega(n \log n)$。
排序方法性能比较
数据规模较小或者较为有序时，插入排序和冒泡排序的性能较好。
- 简单排序算法：直接插入排序、折半插入排序、起泡排序、简单选择排序。
- 改进排序算法：希尔排序、堆排序、快速排序、归并排序、基数排序。
外排序
由于访问外存的速度远远低于内存，需要考虑如何使外存的访问次数尽可能少。
存储设备和缓冲区
- 磁带：顺序访问，不适合随机访问。
- 磁盘：尽量把相关信息放在同一柱面或者相邻柱面，减少寻道时间。
- 缓冲区：内存中的一块区域，用于存放外存中的数据。可以看作是一个队列，先进先出。
基于磁盘的外排序
- 建立用于外排序的内存缓冲区。将他们的大小分为若干段，使用某种内排序方法对每一段进行排序。这些经过排序的段叫做归并段或初始顺串（Run）。生成后就被写在外存中去。
- 仿照内排序种所介绍过的归并树，对这些归并段进行归并，直到得到一个有序的文件。
$$t_{ES} = m \times t_{IS} + d \times t_{IO} + S \times n \times t_{mg}$$ 分别为内排序时间、外存读写时间、归并时间。
需要减小外部读写的时间。
计算理论
计算模型
问题与决定性问题
判定性问题
只需要回答“是”或“否”的问题。
如：
- 一个图是否连通？
- 一个数是否是素数？
功能性问题
需要给出一个解决方案的问题。 如 排序，最大流，最大团等等。
本课程只讨论判定性问题。
有限自动机与正则语言
有限自动机是一个五元组$(Q, \Sigma, \delta, q_0, F)$，其中：
- $Q$ 是有限集，称为状态集。
- $\Sigma$ 是有限集，称为字母表。
- $\delta$ 是转移函数。
- $q_0 \in Q$ 是初始状态。
- $F \subseteq Q$ 是接受状态。
有限自动机计算的形式定义
设 $M = (Q, \Sigma, \delta, q_0, F)$ 是一个有限自动机，$w = w_1w_2\cdots w_n$ 是一个字符串，其中 $w_i \in \Sigma$。
若存在 $Q$ 的一个状态序列 $r_0, r_1, \cdots, r_n$，使得：
- $r_0 = q_0$。
- $r_{i+1} = \delta(r_i, w_{i+1})$，对 $i = 0, 1, \cdots, n-1$。
- $r_n \in F$。
则称 $M$ 接受字符串 $w$。 记为 $\delta(r_0, w) \in F$。
识别语言
对于一个有限自动机 $M$，若 $A = \lbrace w \in \Sigma^* | \delta(q_0, w) \in F \rbrace$，则称 $A$ 是 $M$ 的语言，记为 $L(M) = A$，也称 $M$ 识别 $A$。
$M$ 识别的语言唯一，不识别任意其他语言。
正则语言
若存在一个有限自动机 $M$，使得 $L(M) = A$，则称 $A$ 是一个正则语言。
等价
若两个有限自动机的语言相同，则称它们是等价的。
正则运算
- 并：$A \cup B = \lbrace w | w \in A \text{ 或 } w \in B \rbrace$。
- 连接：$A \circ B = \lbrace w | w = w_1w_2, w_1 \in A, w_2 \in B \rbrace$。
- 星号：$A^* = A^0 \cup A^1 \cup A^2 \cup \cdots$，其中 $A^0 = \lbrace \varepsilon \rbrace$，$A^1 = A$，$A^2 = A \circ A$。 即 $A^*=\lbrace w_1w_2\cdots w_n | n \ge 0, w_i \in A \rbrace$。
- 补：$A^c = \Sigma^* - A$。
正则语言对这四种运算封闭。 则相对补与对称差运算也是封闭的。 即 $A - B = A \cap B^c$，$A \oplus B = (A - B) \cup (B - A)$。
非确定性
当机器处于给定的状态并读入下一个输入符号时，可以知道机器的下一个状态是什么——它是确定的。因此，称这是确定型计算 $\mathrm{(deterministic computation)}$。在非确定型$\mathrm{(nondeterministic)}$机器中，在任何一点，下一个状态可能存在若干个选择。
确定型有限自动机：$\mathrm{(Deterministic Finite Automaton, DFA)}$ 非确定型有限自动机：$\mathrm{(Nondeterministic Finite Automaton, NFA)}$
非确定性是确定性的推广，因此每一台 $\mathrm{DFA}$ 自动地是一台 $\mathrm{NFA}$ 。
确定型有限自动机 (DFA)
$\delta: Q \times \Sigma \to Q$ 是一个函数，对于每一个 $q \in Q$ 和 $\sigma \in \Sigma$，$\delta(q, \sigma)$ 是唯一的。
非确定型有限自动机 (NFA)
$\delta: Q \times \Sigma_\varepsilon \to P(Q)$ 是一个函数，对于每一个 $q \in Q$ 和 $\sigma \in \Sigma_\varepsilon$，$\delta(q, \sigma)$ 是一个状态集合，可能进入多个状态。
转移箭头函数上的符号可以是 $\varepsilon$，表示可以不读入任何输入就转移。
NFA的计算方式
- 若读到输入字符 $s$，机器把自己备份 $0$ 次或多次，然后从这些备份中选择一个状态，继续读入下一个字符。
- 若读到 $\varepsilon$，机器将自己备份一次，然后继续读入下一个字符。
- 读入下一个输入符号，若该符号存在于备份状态的转移函数中，则转 $1$，否则停机。
- 机器检查是否有一个备份状态是接受状态。若存在一个副本是接受状态，则接受输入。
对于输入，$\mathrm{NFA}$ 计算的路径可能不唯一。
NFA 与 DFA 等价
对于每一个 $\mathrm{NFA}$，都存在一个等价的 $\mathrm{DFA}$。
子集构造法
$\mathrm{NFA}$：$\mathrm{N} = (Q, \Sigma, \delta, q_0, F)$ $\mathrm{DFA}$：$\mathrm{M} = (Q’, \Sigma, \delta’, q_0’, F’)$
- $Q’ = 2^Q$，即 $\mathrm{DFA}$ 的状态集是 $\mathrm{NFA}$ 的状态集的幂集。
- $E$ 表示 $\varepsilon$ 闭包，即 $E(S) = \lbrace q \ |\ q \in S \text{ 或 } q \text{ 可以通过若干个 }\varepsilon\text{ 转移到 } S \rbrace$。
- $q_0’ = E(\lbrace q_0 \rbrace)$。
- $\delta’(S, a) = E(\bigcup_{q \in S} \delta(q, a))$，其中 $S \in Q’$，$a \in \Sigma$。
- $F’ = \lbrace S \in Q’ \ |\ S \cap F \neq \varnothing \rbrace$。
正则表达式
若 $R$ 是一个正则表达式，则 $R$ 是
- $a, a \in \Sigma$。
- $\varepsilon$。
- $\varnothing$。
- $(R_1 \cup R_2)$, $R_1$ 和 $R_2$ 是正则表达式。
- $(R_1 \circ R_2)$, $R_1$ 和 $R_2$ 是正则表达式。
- $(R_1^*)$，$R_1$ 是正则表达式。
每个正则表达式 $R$ 表示一种正则语言 $L(R)$。
- $L(a) = \lbrace a \rbrace$。
- $L(\varepsilon) = \lbrace \varepsilon \rbrace$。
- $L(\varnothing) = \varnothing$。
- $L(R_1 \cup R_2) = L(R_1) \cup L(R_2)$。
- $L(R_1 \circ R_2) = L(R_1) \circ L(R_2)$。
- $L(R_1^*) = (L(R_1))^*$。
正则表达式与有限自动机等价
－个语言是正则的，当且仅当可以用正则表达式描述它。
由正则表达式构造有限自动机
由有限自动机构造正则表达式
泵引理
若 $A$ 是一个正则语言，则存在一个整数 $p$，使得对于任意 $w \in A$，若 $|w| \ge p$，则 $w$ 可以被分解为 $w = xyz$，满足：
- 对于任意 $i \ge 0$，$xy^iz \in A$。
- $|y| > 0$。
- $|xy| \le p$。
图灵机
图灵机 $\mathrm{(Turing Machine, TM)}$ 是一个七元组 $(Q, \Sigma, \Gamma, \delta, q_0, q_{\text{accept}}, q_{\text{reject}})$，其中：
- $Q$ 是有限集，称为状态集。
- $\Sigma$ 是有限集，称为输入字母表，不包含特殊空白符号 $\sqcup$。
- $\Gamma$ 是有限集，称为带子字母表，$\Sigma \subseteq \Gamma$，且 $\sqcup \in \Gamma - \Sigma$。
- $\delta: Q \times \Gamma \to Q \times \Gamma \times \lbrace L, R \rbrace$ 是转移函数。即 $\delta(q, a) = (r, b, L / R)$ 表示在状态 $q$ 读入字符 $a$ 后，将字符 $a$ 替换为字符 $b$，转移到状态 $r$，第三个参数 $L / R$ 表示下一步向左 / 向右移动。
- $q_0 \in Q$ 是初始状态。
- $q_{\text{accept}} \in Q$ 是接受状态。
- $q_{\text{reject}} \in Q$ 是拒绝状态，且 $q_{\text{reject}} \neq q_{\text{accept}}$。
图灵机的初始化
设 $M = (Q, \Sigma, \Gamma, \delta, q_0, q_{\text{accept}}, q_{\text{reject}})$ 是一个图灵机，$w = w_1w_2\cdots w_n$ 是一个字符串，其中 $w_i \in \Sigma$。
- 输入带：将 $w$ 放在最左端，其余位置填充 $\sqcup$。
- 状态：初始状态为 $q_0$。
- 读写头：指向第一个字符 $w_1$。
图灵机的格局
对于一个图灵机 $M = (Q, \Sigma, \Gamma, \delta, q_0, q_{\text{accept}}, q_{\text{reject}})$，设 $q \in Q$ ， $u, v \in \Gamma^*$， 则 格局 $uqv$ 表示：
- 状态：$q$。
- 存储带：存储带上的内容为 $uv$，其余为空白符号 $\sqcup$。
- 读写头：指向 $v$ 的第一个字符。
格局的分类
- 起始格局：$q_0w$。
- 接受格局：$uq_{\text{accept}}v$。
- 拒绝格局：$uq_{\text{reject}}v$。
- 停机格局：$uqv$，其中 $q \in \lbrace q_{\text{accept}}, q_{\text{reject}} \rbrace$。
格局的转移
- 如果 $\delta(q_i, b) = (q_j, c, L)$，则
- $u\textcolor{yellow}{aq_ib}v \to u\textcolor{orange}{q_jac}v$
- $\textcolor{yellow}{q_ib}v \to \textcolor{orange}{q_jc} v$
- 如果 $\delta(q_i, b) = (q_j, c, R)$，则
- $u\textcolor{yellow}{aq_ib}v \to u\textcolor{orange}{acq_j}v$
图灵机的计算
设 $M = (Q, \Sigma, \Gamma, \delta, q_0, q_{\text{accept}}, q_{\text{reject}})$ 是一个图灵机，$w = w_1w_2\cdots w_n$ 是一个字符串，其中 $w_i \in \Sigma$。
若存在格局序列 $C_1, C_2, \cdots, C_k$，使得
- $C_1 = q_0w$。
- 对于 $i = 1, 2, \cdots, k-1$，$C_i \to C_{i+1}$。
- $C_k$ 是停机格局。
则称 $M$ 接受字符串 $w$。
图灵机 $M$ 接受 的所有字符串的集合称为 $M$ 接受 / 识别 的语言，记为 $L(M)$。
图灵机运行的结果
- 若 $\mathrm{TM}$ 进入接受状态，则停机且接受输入。
- 若 $\mathrm{TM}$ 进入拒绝状态，则停机且拒绝输入。
- 否则，$\mathrm{TM}$ 一直运行，不停机。
若图灵机 $M$ 对所有输入都停机，则称 $M$ 是判定器。
即对于任意输入，$M$ 要么接受，要么拒绝，不会无限循环。
对于可以识别某个语言的判定器 $M$，称 $M$ 判定该语言。
语言的分类
-
图灵可识别语言：存在一个图灵机可以识别该语言。
- 也称递归可枚举语言。
- = 递归可枚举
- = 计算可枚举
- = 半可判定
- = 半可计算
- 也称递归可枚举语言。
-
图灵可判定语言：存在一个图灵机可以判定该语言。
- 也称递归语言。
- = 递归
- = 可解
- = 可行
- = 可判定
- = 可计算
- 也称递归语言。
包含关系：
graph TD
subgraph turing_recognizable["图灵可识别语言"]
subgraph turing_decidable["图灵可判定语言"]
regex_language["正则语言"]
end
end
classDef circleStyle fill:#dd1,color:black,stroke:#333,stroke-width:4px;
class turing_recognizable circleStyle;
class turing_decidable circleStyle;
class regex_language circleStyle;
图灵机的描述
- 形式水平的描述：状态图或转移函数
- 实现水平的描述：读写头的移动与读写，状态的转移
- 高水平的描述：使用日常语言描述 例如
$M$ = “对于输入串 $w$
- 若 $w$ = $\epsilon$，则接受
- 若只有一个 $0$，则接受
- 若 $0$ 的个数是奇数，则拒绝
- 从带左端隔一个 $0$ 删除一个 $0$，转移到步骤 $2$”
由定义，图灵机的输入总是字符串。
有时候要输入数，图，或图灵机等对象，要将对象编码成字符串。
记对象 O 的编码为 <O>。
特别的，图灵机是有向带权图也可以编码为字符串。
非确定性图灵机
非确定性图灵机 $\mathrm{(Nondeterministic Turing Machine, NTM)}$ 是一个七元组 $(Q, \Sigma, \Gamma, \delta, q_0, q_{\text{accept}}, q_{\text{reject}})$，它的转移函数是 $\delta: Q \times \Gamma \to P(Q \times \Gamma \times \lbrace L, R \rbrace)$。
如果计算的某个分支导致接受状态，则机器接受该输入。
称 $\mathrm{NTM}$ $M$接受 $x$ ， 若在 $x$ 上运行 $M$ 时有接受分支。
称一个 $\mathrm{NTM}$ 为判定的，若它对所有输入，所有分支都停机。
每个 $\mathrm{NTM}$ 都有等价的 $\mathrm{DTM}$
每个判定 $\mathrm{NTM}$ 都有等价的判定 $\mathrm{DTM}$
图灵可识别当且仅当可用非确定型图灵机识别。
图灵可判定当且仅当可用非确定型图灵机判定。
可计算性
可判定性
可判定性问题是指是否存在一个算法，能够判定一个给定的问题的实例是否属于问题的解集。
如果存在这样的算法，那么这个问题就是可判定的。
否则，这个问题就是不可判定的。
我们使用图灵机来
描述
可判定性问题。
如果一个语言可以被图灵机判定，那么这个语言是可判定的。否则，这个语言是不可判定的。
与正则语言相关的可判定性问题
-
$A_{\mathrm{DFA}} = \lbrace \langle B, w \rangle \ |\ B \text{ 是一个 DFA，且 } B \text{ 接受字符串 } w \rbrace$
判定 $A_{\mathrm{DFA}}$ 即判断 $w$ 是否是 $B$ 的一个接受字符串。
是可判定的。 -
$A_{\mathrm{NFA}} = \lbrace \langle B, w \rangle \ |\ B \text{ 是一个 NFA，且 } B \text{ 接受字符串 } w \rbrace$
判定 $A_{\mathrm{NFA}}$ 即判断 $w$ 是否是 $B$ 的一个接受字符串。
是可判定的。 -
$A_{\mathrm{REX}} = \lbrace \langle R, w \rangle \ |\ R \text{ 是一个正则表达式，且 } R \text{ 接受字符串 } w \rbrace$
判定 $A_{\mathrm{REX}}$ 即判断 $w$ 是否是 $R$ 的一个接受字符串。
是可判定的。 -
$E_{\mathrm{DFA}} = \lbrace \langle B \rangle \ |\ B \text{ 是一个 DFA，且 } L(B) = \varnothing \rbrace$
判定 $E_{\mathrm{DFA}}$ 即判断 $L(B) = \varnothing$。
是可判定的。 -
$EQ_{\mathrm{DFA}} = \lbrace \langle B_1, B_2 \rangle \ |\ B_1 \text{ 和 } B_2 \text{ 是 DFA，且 } L(B_1) = L(B_2)\rbrace$
判定 $EQ_{\mathrm{DFA}}$ 即判断 $L(B_1) = L(B_2)$， 即 $L(B_1) \oplus L(B_2) = \varnothing$。
是可判定的。
对角化方法
如果存在函数 $f : A \to B$，且 $f$ 是一对一映射又是满映射，则称集合 $A$ 和 $B$ 有相同规模。
如果一个集合A 是有限的或者与 $\mathbb{N}$ 有相同的规模，则称 $A$ 是可数的
如：
有理数集 $\mathbb{Q}$ 是可数的，因为可以通过一一对应的方式将有理数映射到 $\mathbb{N}$。
实数集 $\mathbb{R}$ 是不可数的，因为实数集比有理数集大。
存在不能被任何图灵机识别的语言
- 所有图灵机构成的集合是可数的
- 对任意的字母表 $\Sigma$ ，其上所有串 $\Sigma^*$ 的集合是可数的
- 所有语言构成的集合是不可数的
- 对任意的字母表 $\Sigma$ ，其上所有语言 $\mathcal{P}(\Sigma^*)$ 的集合是不可数的
规约
$P \le_m Q$ 表示 $P$ 可规约到 $Q$。
若 $P$ 是不可判定的，则 $Q$ 也是不可判定的。
若 $Q$ 是可判定的，则 $P$ 也是可判定的。
$P$ 是 $Q$ 的一个特例，$Q$ 是 $P$ 的一个一般化。
与图灵机相关的不可判定性问题
$A_{\mathrm{TM}}$
$A_{\mathrm{TM}} = \lbrace \langle M, w \rangle \ |\ M \text{ 是一个图灵机，且 } M \text{ 接受字符串 } w \rbrace$ 判定 $A_{\mathrm{TM}}$ 即判断 $w$ 是否是 $M$ 的一个接受字符串。 是不可判定的。
可识别
使用如下算法可以识别 $A_{\mathrm{TM}}$：
- 令 $U$ 是一个图灵机，对于任意输入 $\langle M, w \rangle$，$U$ 模拟 $M$ 运行 $w$。
- 若 $M$ 接受 $w$，则 $U$ 接受 $\langle M, w \rangle$。
- 若 $M$ 拒绝 $w$，则 $U$ 拒绝 $\langle M, w \rangle$。
如果 $M$ 在 $w$ 上循环，则 $U$ 也会在 $\langle M, w \rangle$ 上循环，这就是为什么 $A_{\mathrm{TM}}$ 是不可判定的。
不可判定
$HALT_{\mathrm{TM}}$
$HALT_{\mathrm{TM}} = \lbrace \langle M, w \rangle \ |\ M \text{ 是一个图灵机，且 } M \text{ 在输入 } w \text{ 上停机} \rbrace$ 可识别，但是不可判定的。 $A_{\mathrm{TM}}$ 可以规约到 $HALT_{\mathrm{TM}}$。 所以 $HALT_{\mathrm{TM}}$ 是不可判定的。 即 $A_{\mathrm{TM}} \le_m HALT_{\mathrm{TM}}$。
$E_{\mathrm{TM}}$
$E_{\mathrm{TM}} = \lbrace \langle M \rangle \ |\ M \text{ 是一个图灵机，且 } L(M) = \varnothing \rbrace$
是不可判定的。
$A_{\mathrm{TM}}$ 可以规约到 $E_{\mathrm{TM}}$。
补图灵可识别
对任意不可判定的语言 $A$，它和它的补集 $\overline{A}$ 至少有一个不是图灵可识别的。
如果一个语言是一个图灵可识别的语言的补集，那么这个语言是补图灵可识别的。
－个语言是可判定的，当且仅当它既是图灵可识别的，也是补图灵可识别的。
$\overline{A_{\mathrm{TM}}}$ 不是图灵可识别的。
可知：图灵可识别的补运算不封闭。
计算复杂性
时间复杂性
度量复杂性
时间复杂度
令 $M$ 是一个在所有输入上都停机的确定型图灵机。$M$ 的运行时间或者时间复杂度是一个函数 $f: \mathbb{N} \to \mathbb{N}$。
其中 $\mathbb{N}$ 是非负整数集合，$f(n)$ 是 $M$ 在所有长度为 $n$ 的输入上运行时所经过的最大步数。
若 $f(n)$ 是 $M$ 的运行时间，则称 $M$ 在时间 $f(n)$ 内运行，$M$ 是 $f(n)$ 时间图灵机。
通常使用 $n$ 表示输入的长度。
大 $O$ 和小 $o$ 记法
因为算法精确运行时间通常是一个复杂的表达式，所以一般只估计它的趋势和级别。
通过 渐近分析 ， 只考虑算法的时间的表达式的最高次项，忽略低次项和常数系数，可以试图了解算法在长输入上的运行时间。
- 大 $O$ 记法：
令 $f(n)$ 和 $g(n)$ 是定义在非负整数集合上的函数。
$f(n)=O(g(n))$ 当且仅当存在一个常数 $c>0$ 和一个整数 $n_0 \ge 0$，使得对于所有的 $n \ge n_0$，有 $f(n) \le cg(n)$。 - 小 $o$ 记法：
$f(n)=o(g(n))$ 当且仅当对于所有的常数 $c>0$，存在一个整数 $n_0 \ge 0$，使得对于所有的 $n \ge n_0$，有 $f(n) < cg(n)$。
或 $\lim_{n \to \infty} \frac{f(n)}{g(n)} = 0$。 $$f(n) \neq o(f(n))$$
时间复杂性类
$$\mathrm{TIME}(f(n)) = \lbrace L \ | \ \text{ 存在确定性 } O(f(n)) \text{ 时间图灵机判定 } L \ \rbrace$$
P 类
$\mathrm{P}$ 类是单带确定 $\mathrm{TM}$ 在所有可以在多项式时间内判定的问题的集合。 $$\mathrm{P} = \bigcup_{k \in \mathbb{N}} \mathrm{TIME}(n^k)$$
重要性
- 对于 所有 与单带确定 $\mathrm{TM}$ 等价的 模型，$\mathrm{P}$ 类是相同的。
- 无论你使用的是单带图灵机、多带图灵机，还是其他等价的计算模型，只要一个问题在某个模型上可以在多项式时间内判定（属于 P 类问题），那么在其他模型上也可以在多项式时间内判定。
- $\mathrm{P}$ 类大致对应于计算机上 $实际可解$ 的问题。
NP 类
$\mathrm{NP}$ 类是单带非确定 $\mathrm{TM}$ 在所有可以在多项式时间内判定的问题的集合。 $$\mathrm{NP} = \bigcup_{k \in \mathbb{N}} NTIME(n^k)$$ 其中 $NTIME(f(n))$ 是非确定性图灵机在时间 $f(n)$ 内可以接受的语言的集合。 $$NTIME(f(n)) = \lbrace L \ | \ \text{ 存在非确定性 } O(f(n)) \text{ 时间图灵机判定 } L \ \rbrace$$
非确定性图灵机中猜测的步骤不算做时间复杂度。 例如选取一个子集 / 一个路径 / 一个排列等。
$\mathrm{NP}$ 类中的问题是可以在多项式时间内验证的问题。
$$\mathrm{P} \subseteq \mathrm{NP}$$ $\mathrm{P} = \mathrm{NP} ?$ 是一个重要的未解问题。
验证机
$$A = \lbrace w \ | \ \text{存在一个证明字符串 } c \text{ 使得 } M \text{ 在输入 } \langle w, c \rangle \text{ 上接受} \rbrace$$ 称 $M$ 是 $A$ 的验证机。
判断一个问题是否属于 $\mathrm{NP}$ 类，可以通过构造 $\mathrm{NTM}$ 或者验证机来判断。
$\mathrm{CLIQUE} \in \mathrm{NP}$
$\mathrm{HP} \in \mathrm{NP}$
coNP 类
$$\mathrm{coNP} = \lbrace L \ | \ \overline{L} \in \mathrm{NP} \rbrace$$ $\mathrm{NP} =? \mathrm{coNP}$ 是一个重要的未解问题。 $$\mathrm{P} \subseteq \mathrm{NP} \cap \mathrm{coNP}$$
NP 完全问题
$\mathrm{NP}$ 中某些问题的复杂性与整个 $\mathrm{NP}$ 类的复杂性相关联，即：
若这些问题中的任一个找到 $\mathrm{P}$ 时间算法，则 $\mathrm{P} = \mathrm{NP}$。
这些问题称为 $\mathrm{NP}$ 完全问题。
$\mathrm{SAT}$ 问题
$$\mathrm{SAT} = \lbrace \phi \ | \ \phi \text{ 是一个可满足的布尔公式} \rbrace$$
理论意义
- 研究 $\mathrm{P}$ 和 $\mathrm{NP}$ 之间的关系可以只关注于一个问题的算法。
- 由此可以说明一个问题目前还没有找到 $\mathrm{P}$ 时间算法。
多项式时间归约
类似于 问题的规约 ，多项式时间规约定义了问题求解的有效性传递。
若存在多项式时间图灵机 $\mathrm{M}$ 使得在任意输入 $w$ 上， $\mathrm{M}$ 停机时，带子上显示的字符串为 $f(w)$ ，则称函数 $f: \Sigma^* \to \Sigma^*$ 为多项式时间可计算函数。
称 $A$ 可多项式时间映射规约到 $B$，记作 $A \le_p B$，若 $$\exists f:\Sigma^* \to \Sigma^* \text{ 使得 } \forall w \in \Sigma^*, \quad w \in A \Leftrightarrow f(w) \in B$$ 函数 $f$ 称为 $A$ 到 $B$ 的多项式时间归约。
即 $f$ 将 $A$ 的实例编码在多项式时间内转换为 $B$ 的实例编码。
P 类问题的多项式时间归约
若 $A \le_p B$ 且 $B \in \mathrm{P}$，则 $A \in \mathrm{P}$。 若 $A \le_p B$ 且 $B \in \mathrm{NPC}$，则 $A \in \mathrm{NPC}$。