• 从数据结构来看，栈和队列也是线性表，但其基本操作是线性表 操作的子集
• 从数据类型来看，栈和队列是和线性表不同的抽象数据类型

Stack

栈：限定在表尾/栈顶进行插入和删除、操作受限的线性表

• top：栈顶，表尾端
• bottom：栈底，表头端

• 栈的修改是按照LIFO的方式运转，又称后进先出的线性表

  • 入栈：插入元素
  • 出栈：删除栈顶元素

• last in first out/栈应用广泛，对实现递归操作必不可少

顺序存储结构

顺序栈

顺序栈：顺序映像存储栈底到栈顶的数据元素，同时附设指针指示 栈顶元素在顺序栈帧中的位置

1
2
3
4
5

typedef struct{
	SElemType * base;
	SElemType *top;
	int stacksize;
}SqStack;

• base永远指向栈底，top指向栈顶元素下个位置

  • base==NULL：栈不存在
  • top==base：表示空栈

• 栈在使用过程中所需最大空间难以估计，因此一般初始化设空栈 时不应限定栈的最大容量，应分配基本容量，逐渐增加

链式存储结构

Queue

队列：限定在表尾/队尾进行插入、在表头/队头进行删除的 受限线性表

• rear：队尾，允许插入的一端
• front：队头，允许删除的一端

• 队列是一种FIFO的线性表
• 队列在程序设计中经常出现
  • 操作系统作业排队
  • 图的广度优先遍历

链式存储结构

链队列

链队列：使用链表表示的队列

1
2
3
4
5
6
7
8

typedef struct QNode{
	QElemType data;
	struct QNode  * next;
}QNode, *QueuePtr;
typedef struct{
	QueuePtr front;
	QueuePtr rear;
}LinkQueue;

• front：头指针
• rear：尾指针

• 为方便同样给链队列添加头结点，令头指针指向头结点，此时 空队列判断条件为头、尾指针均指向头结点
• 链队列的操作即为单链表插入、删除操作的特殊情况的，需要 同时修改头、尾指针

顺序存储结构

循环队列

循环队列：使用顺序结构存储队列元素，附设两个指针分别指示对头 、队尾的位置

• 为充分利用数组空间，将数组视为环状空间

1
2
3
4
5

typedef struct{
	QElemType * base;
	int front;
	int rear;
}

• front：头指针
• rear：尾指针
• 循环队列时，无法通过rear==front判断队列空、满，可以在 环上、环外设置标志位判断

• C语言中无法用动态分配的一维数组实现循环队列，必须设置 最大队列长度，如果无法确定，应该使用链队列

Deque

双端队列：限定删除、插入操作在表两端进行的线性表

• 输出受限双端队列：一个端点允许删除、插入，另一个端点只 允许插入
• 输入受限双端队列：一个端点允许删除、插入，另一个端点只 允许删除
• 栈底邻接的两个栈：限定某个端点插入元素只能从该端点删除

• 看起了灵活，但是实际应用不多

Priority Queue优先队列

• 用于从一个动态改变的候选集合中选择一个优先级高的元素
• 主要操作
  • 查找、删除最大元素
  • 插入元素
• 实现
  • 可以基于数组、有序数组实现
  • 基于heap的优先队列实现更好

综述

串/字符串：零个或多个字符组成的有限序列

• 文本串：字母、数字、特殊符号构成
• 位串：0、1构成
• 基因序列：可以使用字符串模型表示，其字母表只包括4个 字母{A, C, G, T}

• $s$：串名，其后单引号括起是串的值
• $a_i$：字母、数字等字符
• $n$：串中字符的数目，串长度，零个字符的串称为空串

• 串的逻辑结构和线性表相似，只是串的数据对象约束为字符集
• 串的基本操作和线性表有很大差别
  • 线性表基本操作大多以“单个元素”作为操作对象
  • 串的基本操作通常以“串的整体”作为操作对象

串的存储表示

• 串只作为输入、输出常量出现，则只需要存储串的串值字符序列
• 在非数值处理中，串也以变量形式出现

定长顺序存储

• 类似线性表的顺序存储结构
• 按照预定义大小，为每个定义的串变量分配固定长度的存储区， 存储字符序列

1

typedef unsigned char SString[MAXSTRLEN+1]

• 串实际长度在预定义范围内随意，超过预定义长度的串值则被 舍去（截断）
• 串实际长度存储方式
  • 以下标为0的数组分量存放：Pascal
  • 在串值后面加入不计串长的结束标记字符：C以\0标记， 此时串长为隐含值，不利于某些操作
• 串操作的原操作为“字符序列的复制”，操作的时间复杂度基于 复制的字符序列长度

堆分配存储

• 仍然以地址连续的存储单元存储串字符序列，但存储空间是在 程序执行过程中动态分配得到

1
2
3
4

typdef struct{
	char *ch;
	int length;
}

• length：串长

• 既有顺序存储结构的特点，处理方便，对串长又没有任何限制
• 此存储结构的串操作仍是基于“字符序列的复制”进行

块链存储

• 使用链表的方式存储串值
• 但是串结构特殊的，需要设置节点大小

1
2
3
4
5
6
7
8

typedef struct Chunk{
	char ch[CHUNKSIZE];
	struct CHUNK * next;
}Chunk;
typedef struct{
	Chunk *head, *tail;
	int curlen;
}

• CHUNKSIZE：节点大小，每个节点中最大存储字符数量
• curlen：当前串长度

• 节点大小不为1时，链表最后一个节点不一定全被串值占满， 此时通常补上非串值字符
• 一般情况下，对串进行操作时，只需要从头到尾扫描即可
  • 对串值不必简历双向链表
  • 设尾指针是为了方便进行联结操作（联结操作需要注意 串尾无效字符）
• 节点大小选择影响串处理效率
  • 存储效率 = 串值所占存储位/实际分配存储位
  • 存储密度小，运算处理方便，存储量占用大
• 块链结构对某些串操作有一定方便，但是总的来说不如另外两种 存储结构灵活，存储量大、操作复杂

串的模式匹配

模式匹配：子串定位操作

总述

处理类似于点、线、多面体这样的几何对象

最近对问题

给定平面上的n个点中，距离最近的两个点

• 点数量n不大3时，可以通过蛮力算法求解的
• 假设集合中每个点均不相同、点按其x坐标升序排列
• 另外使用算法得到点按照y坐标升序排列的列表Q

蛮力算法

算法

1
2
3
4
5
6
7
8
9

BruteForceClosestPoints(p)
	// 蛮力算法求平面中距离最近的点
	// 输入：n个点的列表p；p_i = (x_i, y_i)
	// 输出：两个最近点的距离
	d = \infty
	for i = 1 to n -1 do
		for j = i+1 to n do
			d = min(d, sqrt((x_i - x_j)^2 + (y_i - y_j)^2))
	return d

改进

• 忽略平方根函数，只比较平方

分治法

• 在点集在x轴方向中位数m作垂线，将点集分成大小为 $\lceiling n/2 \rceiling, \lfloor n/2 \rfloor$两个子集 $P_l, P_r$，然后递归求解子问题$P_l, P_r$得到最近点问题解

• 定义$d=min{d_l, d_r}$

  • d不一定是所有点对最小距离
  • 最小距离点对可能分别位于分界线两侧，在合并子问题的 解时需要考虑

• 只需要考虑关于m对称的2d垂直带中的点，记S为来自Q、位于 分隔带中的点列表

  • S同样升序排列
  • 扫描S，遇到距离更近的点对时更新最小距离$d_{min}=d$
  • 对于S中点P，只需考虑在其后、y坐标差小于$d_min$ 的矩形范围内点（因为S有序，P前的点已经考虑过）
  • 该矩形范围内点数目不超过6个（包括P），所以考虑下个点 前，至多考虑5个点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

EfficientClosestPair(P, Q)
	// 分治法解决最近点问题
	// 输入：P存储平面上n个点，按x轴坐标升序排列
			Q存储和P相同的n个点，按y坐标升序排列
	/// 输出：最近点直接欧几里得距离
	if n <= 3
		return 蛮力法最小距离
	else
		将P前ceiling(n/2)个点复制到P_l
		将Q相应的ceiling(n/2)点复制到Q_l
		将P余下floor(n/2)个点复制到P_r
		将Q余下floor(n/2)个点复制到Q_r

		d_l = EfficientClosestPair(P_l, Q_l)
		d_r = EfficientClosestPair(P_r, Q_r)
		d = min{d_l, d_r}

		m = P[ceiling(n/2) - 1].x
		将Q中所有|x-m|<d的点复制到数组S[0..num-1]

		dminsq = d^2
		for i=0 to num-2 do
			k = i+1
			while k <= num-1 and (S[k].y - S[i].y)^2 < dminsq
				dminsq = min((S[k].x - S[i].x)^2 + (S[k].y - S[i].y)^2, dminsq)
				k = k+1
	return sqrt(dminsq)

算法特点

• 算法时间效率

  • 将问题划分为规模相同子问题、合并子问题解，算法都只 需要线性时间
  • 运行时间递推式$T(n) = 2T(n/2) + f(n)$，其中 $f(n) \in \Theta(n)$，则$T(n) \in \Theta(nlogn)$
  • 已经证明在对算法可以执行的操作没有特殊假设情况下， 这是可能得到的最好效率

应用

• 聚类分析

凸包问题

寻找能把给定集合中所有点都包含在里面的最小凸多边形

• 设集合S中点按照x坐标升序排列，存储在列表P中 （x坐标相同，按y坐标升序）

蛮力算法

算法

• 对于n个点集中两个点$p_i$、$p_j$，当且仅当集合中其他点 都位于穿过这两点的直线同侧时，其连线是该集合凸包边界 一部分
• 检验每对点，满足条件的点即构成凸包边界

特点

• 算法时间效率为$O(n^3)$

快包算法（分治法）

算法

• $p_1、$p_n$显然是凸包顶点，且$\overrightarrow{p_1p_n}$ 将点集分为左右两部分$S_1$、$S_2$

  • 其上的点不是凸包顶点，之后不必考虑
  • S的凸包也被划分为upper hull、lower hull，可以使用 相同的方法构造

• 若$S1$为空，则上包就是线段$p_1p_n$；否则寻找距离 $p_1p_n$最大点$p{max}$，若有多个，则选择使得夹角 $\angle p_{max}p_1p_n$最大点

  • $p_max$是上包顶点
  • 包含在$\triangle p1p{max}p_2$中的点不是上包顶点， 之后不必考虑
  • 不存在同时位于$\overrightarrow{p1p{max}}$、 $\overrightarrow{p_{max}p_n}$左侧的点

• 对$\overrightarrow{p1p{max}}$及其左侧点构成的集合 $S{1,1}$、$\overrightarrow{p{max}pn}$及其左侧的点构成 集合$S{1,2}$，重复以上即可继续得到上包顶点

• 类似的可以对$S_2$寻找下包顶点

向量左侧、距离计算参考线代

算法特点

快包和快排很类似

• 最差效率$\Theta(n)$，平均效率好得多
• 也一般会把问题平均的分成两个较小子问题，提高效率
• 对于均匀分布在某些凸区域（园、矩形）的点，快包平均效率 可以达到线性

应用

• 计算机动画中使用凸包替换物体本身，加快碰撞检测速度
• 车辆路径规划
• 地理信息系统中根据卫星图像计算accessibility map
• 数理统计中用于进行异常值检测
• 计算点集直径的高效算法中需要用到

欧几里得最小生成树问题

给定平面上n个点，构造顶点为这n个点的总长度最小的树

参考

二维散点

Convex Hull

凸包：包含点集S的最小凸集合

• 离散点集：包含所有点的最小凸多边形
• 最小：凸包一定是所有包含S的凸集合的子集
• 凸包能方便地提供目标形状或给定数据集地一个近似

Extreme Point

极点：对于任何以集合中点为端点的线段，不是线段中点的点

• 极点有一些特性是凸集中其他点不具备的性质

  • 单纯形法：如果存在极值，则一定可以在极点处取到
  • 找到极点、极点排序方向即可解决凸包问题

• 举例

  • 三角形中3个顶点
  • 圆周上所有点

总述

涉及连续性数学问题

• 解方程、方程组，计算定积分，函数求值
• 和离散数学中：图、树、排序、组合相对

特点

• 大部分此类问题只能近似求解

  • 泰勒展开求解$e^x$
  • Composite Trapezoidal rule：组合梯形法则，计算 定积分

• 此类问题大部分要操作实数，而实数在计算机内部只能近似表示 ，大量对近近似数的算术操作可能会叠加误差，输出错误结果

整数乘法

俄式乘法

两个正整数n、m相乘的非主流算法

算法

• 反复应用以下公式，简化每步的计算 $$n为奇数：n * m = \frac n 2 * 2m + m \\ n为偶数：n * m = \frac n 2 * 2m$$
• 以$1 * m$作为算法终止条件

特点

• n为奇数步骤中的m，可以最后累加即可

• 算法中只有折半、加倍、相加操作

  • 手动计算非常简便
  • 计算机硬件对折半、加倍只需要移位就可

• 减常因子法

大整数乘法

算法

考虑a、b两个n位整数，n为偶数

• 从中间把数字分段，得到$a_1, a_0, b_1, b_0$

• 则有

  $$\begin{align} c & = a * b = (a_1 10^{n/2} + a_0) * (b_1 10^{n/2} + b_0) \\ & = (a_1 * b_1)10^n + (a_1 * b_0 + a_0 * b_1) 10^{n/2} + (a_0 + b_0) \\ & = c_2 10^n + c_1 10^{n/2} + c_0 \end{align}$$
  • $c_2 = a_1 * b_1$
  • $c_0 = a_0 * b_0$
  • $c_1 = (a_1 + a_0) * (b_1 + b_0) - (c_2 + c_0)

• 若n/2也是偶数，可以使用相同的方法计算得到三个乘法表达式

  • 若n为2的幂次，就可以得到计算n位数积的递归乘法
  • n迭代到足够小时，递归就可以停止

特点

• 算法效率

  • 乘法次数递推式：$M(n)=3M(n/2), M(1)=1$，则 $M(n) = n^(log_2 3) \approx n^{1.585}$
  • 加法次数递推式：$A(n)=3A(n/2) + cn, A(1)=1$，则 $A(n) \in \Theta(n^{log_2 3})$

• 算法有渐进效率优势，实际性能依赖于计算机系统、算法实现 质量，在某些情况下

  • 计算8位乘法时，分治算法速度快于传统方法
  • 计算超过100位时，速度是传统算法2倍

• 分治法

欧几里得算法

计算最大公约数、最大公倍数

最大公约数

• n为0，返回m作为结果结束
• 将m处以n的余数赋给r
• 将n付给m，r赋给n，返回第一步

1
2
3
4
5
6

Euclid(m, n)
	while n != 0 do
		r = m mod n
		m = n
		n = r
	return m

最大公倍数

• 利用最大公约数计算最小公倍数

特点

• 变治法（+减可变规模）

特定点求值

霍纳法则（计算多项式）

霍纳法则：不断将x作为公因子提取出来，合并降次后的项，然后 计算多项式在特定点的值

算法

1
2
3
4
5
6
7
8

Horner(P[0..n], x)
	// 用霍纳法则求多项式在给定点的值
	// 输入：多项式系数数组P[0..n]、数字x
	// 输出：多项式在x点的值
	p = P[n]
	for i = n-1 downto 0 do
		p = x*p + P[i]
	return p

特点

• 算法效率

  • 效率始终为n，只相当于直接计算中$a_n x^n$的乘法数量

• 变治法

二进制（计算）幂

将幂次转换为二进制位串，利用二进制位串简化计算

从左至右二进制幂

• 对位串应用霍纳法则

1
2
3
4
5
6
7
8
9
10

LeftRightBinaryExponentiation(a, B[0..n-1])
	// 从左至右二进制幂算法计算a^n
	// 输入：数字a、表示幂次的二级制位串B[0..n-1]
	// 输出：a^n的值
	product = a
	for i = n-1 downto 0 do
		product = product * product
		if B[i] == 1:
			prduct = product * a
	return product

从右至左二进制幂

• 累次计算二进制位串中为1部分值，将其累乘

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

RightLeftBinaryExponentiation(a, B[0..n-1])
	// 从右至左二进制幂算法
	// 输入：数字a、表示幂次的二级制位串B[0..n-1]
	// 输出：a^n的值
	term = a
	if B[0] == 1
		product = a
	else
		product = 1
		// 保存累乘值
	for i = i to n do
		term *= 2
		// 保存二进制位为1部分值
		if B[i] = 1
			product = product * term
	return product

特点

• 算法效率

  • 两个算法效率取决于位串长度，是对数级的

• 变治法

应用

• 在密码技术中，需要对超过100位十进制整数进行乘法运算，而 计算机往往不能直接运算

矩阵乘法

Strassen矩阵乘法

算法

若A、B是两个n阶方阵（若n不是2幂次，考虑填充0）

• 将A、B、C均分块为4个n/2子矩阵
• 递归使用Strassen方程中定义的矩阵M进行计算计算C各个子阵

算法特点

• 对2 * 2分块计算，Strassen算法执行了7次乘法、18次加减法， 蛮力算法需要执行8次乘法、4次加法

• 算法效率

  • 乘法次数递推式：$M(n) = 7M(n/2), M(1) = 1$，则 $M(n) = 7^{log2 n} = n^{log_2 7} \approx n{2.807}$
  • 加法次数递推式：$A(n) = 7A(n/2) + 18(n/2)^2, A(1)=0$ ，则$A(n) \in \Theta(n^{log_2 7})$
  • 矩阵趋于无穷大时，算法表现出的渐进效率卓越

• 还有一些算法能运行时间$\in \Theta(n^\alpha)$，最小能达到 2.376，但是这些算法乘法常量很大、算法复杂，没有实用价值

• 矩阵乘法效率下界为$n^2$，目前得到的最优效率和其还有很大 距离

• 分治法

线性方程组

• 假设方程组系数矩阵为n阶方阵，且解唯一
• 主要思想都是高斯消元法（变治法），只是出于效率、误差有 不同实现方式

前向消去法

算法

1
2
3
4
5
6
7
8
9
10
11

ForwardElimination(A[1..n, 1..n], b[1..n])
	// 对方程组扩展矩阵[A|b]使用高斯消元法
	// 输入：矩阵A[1..n, 1..n]，向量b[1..n]
	// 输出：扩展的上三角矩阵
	for i = 1 to n do
		A[i, n+1] = b[i]
		// 得到扩展矩阵
	for i = 1 to n-1 do
		for j = i+1 to n do
			for k = n+1 downto i do
				A[j, k] = A[j, k] - A[i, k]*A[j, i] / A[i, i]

算法特点

• 前向消去法不一定正确

  • 如果A[i, i]==0，不能以其作为除数，此时需要交换行 （解唯一时总是存在非0行）
  • A[i, i]非常小，导致比例因子A[j, i] / A[i, i]非常大， 产生大的舍入误差

• 最内层循环效率低

部分选主元法

算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

BetterForwardElimination(A[1..n, 1..n], b[1..n])
	// 用部分选主元法实现高斯消去
	// 输入：矩阵A[1..n, 1..n]，向量b[1..n]
	// 输出：扩展的上三角矩阵
	for i = 1 to n do
		A[i, n+1] = b[i]
	for i = 1 to n-1 do
		pivotrow = i
		for j = i+1 to n do
			if |A[j, i]| > A[pivot, i]
				pivotrow = j
				// 选择第i列系数最大的行作为第i次迭代基点
				// 保证比例因子绝对值不会大于1
			for k = i to n+1 do
				swap(A[i, k], A[pivot, k])
			for j = j+1 to n do
				temp = A[j, i] / A[i, i]
				// 这样只需要计算依次比例因子
				for k = i to n+1 do
					A[j, k] = A[j, k] - A[i, k] * temp

特点

• 部分选主元法克服了前向消去法弊端
  • 最内层乘法（加法）执行次数为 $\frac {n(n-1)(2n+5) 6 \approx \frac n^3 3 \in \Theta(n^3)$
  • 始终能保证比例因子绝对值不大于1

反向替换法

在得到上三角系数矩阵中

• 从最后一个方程中可以立刻求出$x_n$
• 将$xn$带入倒数第二个方程求出$x{n-1}$
• 逐次递推得到所以解

特点

• 算法时间效率$\in \Theta(n^2)$

高斯消去法应用

• 矩阵（可逆矩阵）中应用
  • LU分解（Doolittle分解）
  • Cholesky分解（要求矩阵正定）
  • 求逆
  • 求行列式
• 高斯消元法整个算法效率取决于消去部分，是立方级
  • 事实上此方法在计算机上求解大规模方程组很难，因为舍入 误差在计算过程中会不断累积

非线性方程求解

• 5次及以上多项式没有只包含多项式系数、算术操作、开根号 的通用求根公式

• 方程的代数解并不具有很大的意义，充其量只是为方程的根设置 一个符号，然后再说方程有一个根等于这个符号（高斯）

平分法

基于连续函数界值定理，类似于连续版折半查找

算法

在区间[a, b]的端点上，$f(x)$符号取反

• 计算$f(x{mid}), x{mid}= \frac {a+b} 2$的值
• 若$f(x_{mid})=0$，则求得一个
• 否则选择使得$f(x)$能在端点上取得相反值区间$[a, x{mid}$ 、$[x{mid}, b]$
• 当包含根得区间小于预定义得$\epsilon > 0$时，就可以停止 算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

Bisection(f(x), a, b, eps, N)
	// 评分法求f(x) = 0的一个根
	// 输入：f(a)f(b) < 0，eps绝对误差上界，N迭代次数上界
	// 输出：(a, b)上的一个根近似（精确）值，或包含根的区间
	n = 1
		// 迭代计数
	while n <= N do
		x = (a + b)/2
		if x - a < eps
			 return x
		fval = f(x)
		if fval = 0
			return x
		if fval*f(a) < 0:
			b = x
		else
			a = x
		n += 1
	return a, b
		// 达到迭代限制，返回包含根的区间

特点

• 求解精度
  • 理论上迭代次数足够$x_n$可以任意接近真实根$x^{*}$
  • 实际上，机器使用0表示非常小的值，$\epsilon$小于特定 机器阈值时，算法不会停止，也无法得到满足条件的解
  • d对目标函数求值时可能会发生舍入误差
• 缺点
  • 相较于其他已经算法，收敛速度较慢
  • 并且无法扩展到更加一般的方程、方程组领域
• 优点
  • 区间特性容易检验

Method of False Position

试位法：类似于连续版差值查找

算法

• 类似平分法每次也使用某个区间$[a_n, b_n]$括住连续函数的 根，函数在端点取值符号相反

• 使用穿过$(a_n, f(a_n)), (b_n, f(b_n))$的直线在x轴截距 $x=\frac {a_nf(b_n) - b_nf(a_n)} {f(b_n) - f(a_n)}$作为 分割点

特点

• 对许多实例，试位法收敛速度较平分法更快

牛顿法

Newton-Raphon Method

算法

• 方法产生近似解序列：函数切线在x轴截距 $x_{n+1} = x_n - \frac {f(x_n)} {f^{‘}(x_n)},n=0,1,\cdots$

特点

• 大多数情况下，若初值$x_0$足够接近根，牛顿法能够保证序列 收敛与根；对远离根的初值，无法保证一定会收敛

• 优点

  • 牛顿法相较于平分法、试位法收敛速度更快，选定合适的 初值能够快速收敛
  • 能够应用于更一般类型的方程、方程组

• 方法每次都迭代需要重新求函数、导数值

  • 导数值等于0，则牛顿法失效
  • 导数绝对值越大，牛顿法越有效

• 牛顿法不会把根括起来

概述

概念

• data：数据，对客观事物的符号表示，在计算机科学中，指 所以能输入计算机中、并被计算机处理的符号总称
• data element：数据元素，数据基本单位，在计算机中通常 作为整体考虑
• data item：数据项，数据元素的组成部分
• data object：数据对象，性质相同的数据元素的集合，数据 的子集

Data Structure

数据结构：相互直接存在一种或多种特定关系的数据元素的集合

• 使用基本类型不断组合形成的层次结构
• 某种意义上，数据结构可以看作是一组具有相同结构的值

• $D$：数据元素有限集
• $S$：结构/关系有限集，数据元素之间相互之间的逻辑关系

• 集合：结构中数据元素只有同属一个集合的关系

• 线性结构：结构中数据元素之间存在一对一关系

  • 存在唯一一个被称为“第一个”的数据元素
  • 存在唯一一个被称为“最后一个”的数据元素
  • 除第一个外，每个数据元素均只有一个前驱
  • 除最后一个外，每个数据元素均只有一个后继

• 树型结构：结构中数据元素存在一对多关系

• 图状/网状结构：结构中数据元素存在多对多的关系

关系表示

• 逻辑结构：数据结构中描述的逻辑关系
• 物理/存储结构：数据结构在计算机中的表示（映像）

数据元素之间关系在计算机中映像/表示方法/存储结构

• 顺序映像：借助元素在存储器中的相对位置表示数据元素 之间的逻辑关系

  • 需要使用地址连续的存储单元依次存储数据元素
  • 所以需要静态分配空间，即给可能数据对象预分配空间 ，空间不够时只能重新分配
  • 由此得到顺序存储结构

• 非顺序/链式映像：借助指示元素存储地址的指针表示数据 元素之间的逻辑关系

  • 可以使用任意存储单元存储数据元素，另外存储一个指示 其直接后继的信息
  • 常用动态分配空间，即在需要创建数据对象时给其分配空间
  • 也可以静态分配空间，使用地址连续的存储单元存储数据 对象，此时指示元素可以是序号
  • 由此得到链式存储结构

• node：节点，数据元素信息、直接后继元素信息的存储映像
• 数据域：存储元素信息的域
• 指针域：存储直接后继位置的域

Data Type

数据类型：值的集合和定义在值集上的一组操作的总称

• atomic data type：原子类型，值不可分解
• fixed-aggregate data type：固定聚合类型，值由确定数目 的成分按某种结构组成
• variable-aggregate data type：可变聚合类型，值的成分 数目不确定
• 结构类型：固定、可变聚合类型的统称，值由若干成分按某种 结构组成，可分解，其成分可以是结构或非结构

  • 结构类型可以看作是由一种数据结构和定义在其上的一组 操作组成

• 在计算机中，每个处理核心（硬件、软件）都提供了一组原子 类型或结构类型
• 从硬件角度，引入数据类型是作为解释计算机内存中信息 含义的手段
• 对使用者而言，实现了信息的隐蔽

Abtract Data Type

ADT：抽象数据类型，一个数学模型已经定义在该模型上的 一组操作

• $D$：数据对象
• $S$：D上的关系集
• $P$：对D的基本操作集

• 根据其行为而不是其内部表示定义类型
• 实质上与数据类型是同一个概念，“抽象”的意义在于数据类型的 数学抽象特性
  • 或者说抽象数据类型范畴更广，包括自定义数据类型
• 抽象层次越高，含有该抽象数据类型的程序复用程度越高

面向对象

• ADT是面向对象编程的核心

• 将对象行为和其实现相分离，这也是面向对象编程的基本 技术

  • simplicity：简单性，隐藏细节方便理解
  • flexibility：灵活性，类通过对外行为被定义，可以 自由改变内部实现
  • security：安全性，扮演防火墙，确保实现、用户彼此 分离

基础

算法：一系列解决问题的明确指令，即对于符合一定规范的 输入，能够在有限时间内获得要求的输出

• 算法每步都必须没有歧义
• 必须确定算法所处理的输入的值域
• 同一算法可以用几种不同的形式描述
• 同一问题，可能存在几种不同的算法
• 同问题的不同算法，可能基于不同的解题思路，速度也会不同

算法正确性证明

• 对某些算法，正确性证明十分简单，对于另一些算法，可能十分 复杂
• 证明正确性的一般方法是使用数学归纳法，因为算法的迭代过程 本身就符合其所需的一系列步骤
• 根据特定输入追踪算法操作有意义，但是并不能证明算法的 正确性，只需要一个算法不能正确处理的输入实例就足够了
• 对于近似算法，常常试图证明算法所产生的误差，不超出预定义 的误差

算法分析方向

• 时间效率（time efficiency）：算法运行速度
• 空间效率（space efficiency）：算法需要多少额外的存储空间
• 简单性（simplicity）：取决于审视者的眼光
  • 简单的算法更容易理解、实现
  • 相应程序包含更少的bug
• 一般性（generality）
  • 所解决问题的一般性
  • 所接受输入的一般性
• 最优性（optimality）：与所解决问题的复杂度有关，与某算法 效率无关
• 是否每个问题都能够用算法的方法来解决

非确定性

Deterministic Alogrithm

确定算法：利用问题解析性质，产生确定的有限、无限序列使其收敛 于全局最优解

• 依某确定性策略搜索局部极小，试图跳跃已获得的局部极小而 达到某个全局最优点

• 能充分利用问题解析性质，从计算效率高

Nondeterministic Algorithm

不确定算法，包括两个阶段，将判定问题的实例l作为其输入

• 猜测（非确定）阶段：生成任意串S作为l候选解
• 验证（确定）阶段：把l、S作为输入，，若S是l解输出是， 否则返回否或无法停止

• 当选仅当对问题每个真实例，不确定算法会在某次执行中 返回是时，称算法能求解此问题

• 即要求不确定算法对某个解至少能够猜中一次、验证正确性， 同时不应该将错误答案判定为是

• Nondeterministic Polynominal Algorithm：验证阶段时间 效率是多项式级的不确定算法

分析框架

• time complexity：算法运行速度
• space complexity：算法需要的额外空间
  • 算法需要的额外空间已经不是需要重点关注的问题

影响因素

输入规模$n$

• 几乎所有算法，对规模更大的输入需要运行更长时间，因此使用 输入规模作为参数很有价值

• 在有些情况下，选择不同的参数表示输入规模有差别

• 选择输入规模的度量单位还受到算法的操作细节影响

• 和数字特性相关的算法，倾向于使用$n$的二进制位数 $b=\lfloor {log_{2}^{n}} \rfloor + 1$

其他因素

有些算法的运行时间不仅取决于输入规模，还取决于特定输入的细节

• worst-case efficiency：最坏情况下的效率
• best-case efficiency：最优情况下的效率
• average-case efficiency
  • 平均效率的研究比最差、优效率研究困难很多
  • 可以将输入划分为几种类型，使得对同类实例，算法基本 执行次数相同，推导各类输入的概率分布，得到平均次数
• amortized efficiency：应用于算法对同样的数据结构所执行 的一系列操作
  • 有些情况下，算法单次执行时间代价高，但是n次运行的 总运行时间明显优于单次执行最差效率 * n

衡量角度

运行时间

• 使用时间标准的度量算法程序运行时间缺陷

  • 计算机速度
  • 程序实现质量
  • 编译器
  • 计时困难

• 找到basic operation并计算其运行次数

  • 不依赖于其他无关因素
  • 对总运行时间贡献最大，不需要统计算法每步操作执行次数
  • 如：对排序基本操作为键比较，数学问题则是四则运算， 需要注意除法、乘法、加减法耗时依次减小

• 时间估计

  • $c_{op}$：特定计算一个基本操作的执行时间
  • $C(n)$：算法执行基本操作的次数
  • $T(n)=c_{op}C(n)$：可以用于估算算法的执行时间
    • 需要小心使用
    • $C(n)$不包含非基本操作的信息，也只是估计的结果
    • $c_{op}$也是不可靠的估计值

Order of Growth

小规模输入运行时间差别不足以将高效算法与低效算法相区别， 对大规模输入忽略乘法常量，仅关注执行次数的order of growth 及其常数倍，即算法的渐进效率

• 按照算法渐进效率进行分类的方法缺乏使用价值，因为没有指定 乘法常量的值

• 但是对于实际类型输入，除了少数算法，乘法常量之间不会相差 悬殊，作为规律，即使是中等规模的输入，属于较优渐进 效率类型的算法也会比来自较差类型的算法效果好

• 对数函数：增长慢，以至于可以认为，对数级操作次数的算法能 瞬间完成任何实际规模输入

• 指数级：指数函数、阶乘函数
  • 需要指数级操作次数的算法只能用于解决规模非常小的问题

渐进效率

渐进符号

$O(g(n))$

• 对于足够大的n，$t(n)$的上界由$g(n)$的常数倍确定，则 $t(n) \in O(g(n))$

• 即存在大于0的常数$c$、非负整数$n_{0}$，使得

  $$n > n_{0} 时，t(n) \leqslant cg(n)$$

• 增长次数小于等于$g(n) n \rightarrow \infty$ （及常数倍）的函数集合

$\Omega (g(n))$

• 对于足够大的n，$t(n)$的下界由$g(n)$的常数倍确定，则 $t(n) \in \Omega(g(n))$

• 即存在大于0的常数$c$、非负整数$n_{0}$，使得

  $$n > n_{0} 时，t(n) \geqslant cg(n)$$

• 增长次数大于等于$g(n) n \rightarrow \infty$ （及常数倍）的函数集合

$\Theta (g(n))$

• 对于足够大的n，$t(n)$的上、下界由$g(n)$的常数倍确定，则 $t(n) \in \Theta(g(n))$

• 即存在大于0的常数$c{1}, c{2}$、非负整数$n_{0}$，使得

  $$n > n_{0} 时，c_{2}g(n) \leqslant t(n) \leqslant c_{1}g(n)$$

• 增长次数等于$g(n) n \rightarrow \infty$（及常数倍） 的函数集合

极限比较增长次数

利用极限比较增长次数：比直接利用定义判断算法的增长次数方便， 可以使用微积分技术计算极限

基本渐进效率类型

算法的数学分析

非递归算法

分析通用方案

1. 决定表示输入规模的参数
2. 找出算法的基本操作：一般位于算法最内层循环
3. 检查算法基本操作执行次数是否只依赖于输入规模，如果和其他 特性有关，需要分别研究最差、最优、平均效率
4. 建立算法基本操作执行次数的求和表达式（或者是递推关系）
5. 利用求和运算的标准公式、法则建立操作次数的闭合公式，或 至少确定其增长次数

递归算法

用一个方程把squence的generic term和一个或多个其他项相关联， 并提供第一个项或前几项的精确值

• recurrence：递推式
• initial condition：序列起始值、递归调用结束条件
• 求解：找到序列通项的精确公式满足递推式、初始条件，或者 证明序列不存在
• general solution：满足递推方程所有解序列公式，通常 会包含参数
• particular solution：满足给定递推方程的特定序列，通常 感兴趣的是满足初始条件的特解

递归求解方法

• method of forward substituion：从序列初始项开始，使用 递推方程生成给面若干项，从中找出能用闭合公式表示的模式

  • 带入递推方程、初始条件验证
  • 数学归纳法证明

• method of backward subsitution：从序列末尾开始，把序列 通项$x(n)$表示为$x(n-i)$的函数，使得i是初始条件之一， 再求和公式得到递推式的解

• second-order linear recurrence with constant coefficients ：求解characteristic equation得到特征根得到通解

常见递推类型

decrease-by-one

减一法：利用规模为n、n-1的给定实例之间的关系求解问题

• 减常数法特例

decrease-by-a-constant-factor

减常因子法：把规模为n的实例化简为规模为n/b的实例求解问题

divide-and-conquer

分治法：将给定实例划分为若干较小实例，对每个实例递归求解，如有必要， 再将较小实例的接合并为给定实例的一个解

平滑法则、主定理

• eventually nondecreaing：$f(n)$在自然数上非负，若 $\exists n{0}, \forall n{2} > n{1} \geqslant n{0}, f(n{2}) > f(n{1})$， 则为最终非递减

• smooth：$f(n)$在自然数上非负、最终非递减，若 $f(2n) \in \Theta(f(n))$，则平滑

  • 若$f(n)$平滑，则对任何整数b有$f(bn) \in \Theta(f(n))$

平滑法则

$T(n)$最终非递减，$f(n)$平滑，若$n=b^{k}(b>2)$时有 $T(n) \in \Theta(f(n))$，则$T(n) \in \Theta(f(n))$

主定理

• 方便对分治法、减常因子法效率进行分析

$T(n)$最终非递减，满足递推式

若$f(n) \in \Theta(n^{d}), d \geqslant 0$，则

分析通用方案

1. 决定衡量输入规模的参数
2. 找出算法基本操作
3. 检查算法基本操作执行次数是否只依赖于输入规模，如果和其他 特性有关，需要分别研究最差、最优、平均效率
4. 建立算法基本操作执行次数的递推关系、相应初始条件
5. 求解递推式，或至少确定其增长次数

算法时间效率极限

确定已知、未知算法效率极限

算法下界

算法下界是问题可能具有的最佳效率

• 可以用于评价某问题具体算法效率

  • 不同问题算法直接比较无意义

• 寻找问题的更优算法时，可以根据算法下界确定期望获得的改进

  • 若算法下界是紧密的，则改进至多不过是常数因子
  • 若算法下界和算法仍有差距，则可能存在更快算法，或者是 证明更好的下界

Trivial Lower Bound

平凡下界：任何算法只要要“读取”所有要处理的项、“写”全部 输出，对其计数即可得到平凡下界

• 往往过小，用处不大

• 确定问题中所有算法都必须要处理的输入也是个障碍

• 例

  • 生成n个不同项所有排列的算法$\in \Omega(n!)$，且下界 是紧密的，因为好的排列算法在每个排列上时间为常数

  • 计算n次多项式值算法至少必须要处理所有系数，否则改变 任意系数多项式值改变，任何算法$\in \Omega(n)$

  • 计算两个n阶方阵乘积算法$\in Omega(n^2)$，因为任何 算法必须处理矩阵中$2n^2$个元素

Information-Theoretic Lower Bound

信息论下界：试图通过算法必须处理的信息量（比特数）建立 效率下界

• 例

  • 猜整数中，整数的不确定信息量就是 $\lceil \log_2 n \rceil$（数字二进制位数）， n为整数上界

Adversary Lower Bound

敌手下界：敌手基于恶意、一致的逻辑，迫使算法尽可能多执行， 从而确定的为了保证算法正确性的下界

• 恶意使得它不断把算法推向最消耗时间的路径
• 一致要求它必须和已经做出的选择保持一致（按照一定规则）

• 例

  • 猜整数中，敌手把1~n个数字作为可选对象，每次做出判断 后，敌手保留数字较多集合，使得最消耗时间、不违背之前 选择

  • 两个有序列表${a_i}, {b_j}$归并排序中，敌手使用规则： 当前仅当i < j时，对$a_i < b_j$返回真（设置列表值大小 可以达到），则任何算法必须比较2n-1次，否则交换未比较 元素归并错误

问题化简

问题Q下界已知，考虑将问题Q转换为下界未知问题P，得到P下界

• 应该表明任意Q问题实例可以转换为P问题
• 即问题Q应该是问题P的子集，正确的算法至少应该能解决Q问题

• 许多问题复杂性不清楚，而对问题复杂度的直观判断和问题表现 形式相关，并不可靠

• 常在问题化简中使用的已知下界问题

  |问题|下界|紧密性| |——-|——-|——-| |排序|$\Omega(nlogn)$|是| |有序数组查找|$\Omega(logn)$|是| |元素惟一性|$\Omega(nlogn)$|是| |n位整数乘法|$\Omega(n)$|未知| |n阶方程点乘|$\Omega(n^2)$|未知|

• 例

  • 欧几里得最小生成树：使用元素唯一性问题作为下界已知 问题

    • 将n个实数映射为x轴上的n个点
    • 设T为此点集最小生成树，T必然包含一条最短边??#todo
    • 检查T是否包含长度为0的边即为元素惟一性

  • 任意矩阵A、B乘法：使用方阵乘法作为下界已知问题

    • 将A、B化成对称方阵进行计算

      $$X = \begin{bmatrix} 0 & A \\ A^T & 0 \\ \end{bmatrix}, Y = \begin{bmatrix} 0 & B^T \\ B & 0 \\ \end{bmatrix} \\ XY = \begin{bmatrix} AB & 0 \\ 0 & A^TB^T \\ \end{bmatrix}$$

    • 乘积AB可以方便提取，而翻倍的矩阵乘法不会影响复杂性

决策树（二叉）

可以使用（二叉）决策树研究基于比较的算法性能

• 每个非叶子节点代表一次键值比较

• 叶子节点个数大于等于输出，不同叶子节点可以产生相同输出

• 对于特定规模为n的输入，算法操作沿着决策树一条从根到叶子 节点完成，所以最坏情况下比较次数等于算法决策树高度

• 如果树具有由输出数量确定叶子，则树必须由足够高度容纳叶子 ，即对于任何具有$l$个叶子，树高度 $h \leqslant \lceil log_2 l \rceil$，这也就是 信息论下界

线性表排序

任意n个元素列表排序输出数量等于$n!$，所以任何基于比较的排序 算法的二叉树高度，即最坏情况下比较次数

• 归并排序、堆排序在最坏情况下大约必须要做$nlog_2n$次比较 ，所以其渐进效率最优

• 也说明渐进下界$\lceil log_2n! \rceil$是紧密的 ，不能继续改进

  • 但这个只是基于二叉决策树的渐进下界，对于具体值估计 可能不准

  • 如$\lceil log_2 12! \rceil = 29$，而事实证明 12个元素排序30次比较是必要、充分的

• 也可以使用决策树分析基于比较的排序算法的平均性能，即 决策树叶子节点平均深度

  • 基于排序的所有输出都不特殊的标准假设，可以证明平均 比较次数下界$C_{avg}(n) \geqslant log_2n!$

  • 这个平均是建立在所有输出都不特殊假设上，所以这个其实 应该是不同算法平均比较次数下界的上界

  • 对于单独排序算法，平均效率会明显好于最差效率

有序线性表查找

有序线性表查找最主要算法是折半查找，其在最坏情况下下效率 $C{worst}^{bs} = \lfloor log_2n \rfloor + 1 = \lceil log(n+1) \rceil$

• 折半查找使用的三路比较（小于、等于、大于），可以使用 三叉查找树表示

  • 三叉查找树会有2n+1个节点：n个查找成功节点、n+1个查找 失败节点

  • 所以在最坏情况下，比较次数下界 $C_{worst}(n) \geqslant \lceil log_3{2n+1} \rceil$ 小于折半查找最坏情况下比较次数（渐进）

• 然而，事实上可以删除三叉查找树中间子树（等于分支），得到 一棵二叉树

  • 非叶子节点同样表示三路比较，只是同时作为查找成功终点

  • 可以得到一个新的下界 $C_{worst}(n) \geqslant \lceil log_2{n+1} \rceil$

• 更复杂的分析表明，标准查找假设下，折半查找平均情况比较 次数是最少的

  • 查找成功时$log_2n - 1$
  • 查找失败时$log_2(n+1)$

P、NP、完全NP问题

复杂性理论

• 如果算法的最差时间效率$\in O(p(n))$，$p(n)$为问题输入 规模n的多项式函数，则称算法能在多项式时间内对问题求解

• Tractable：易解的，可以在多项式时间内求解的问题

• Intractable：难解的，不能在多项式内求解的问题

使用多项式函数理由

• 无法保证在合理时间内对难解问题所有实例求解，除非问题实例 非常小

• 对实用类型的算法而言，其多项式次数很少大于3，虽然多项式 次数相差很大时运行时间也会有巨大差别

• 多项式函数具有方便的特性

  • 多项式加和、组合也为多项式

• 多项式类型可以发展出Computational Complexity利用

  • 该理论试图对问题内在复杂性进行分类
  • 只要使用一种主要计算模型描述问题，并用合理编码方案 描述输入，问题难解性都是相同的

Decision Problem

判定问题：寻求一种可行的、机械的算法，能够对某类问题在有穷 步骤内确定是否具有某性质

• Undecidable问题：不可判定问题，不能使用任何算法求解的 判定问题

  • 停机问题：给定程序、输入，判断程序对于输入停止还是 无限运行下去

• Decidable问题：可判定问题，能用算法求解的问题

  • 可判定、难解问题存在，但非常少

  • 很多判定问题（或者可以转化为等价判定问题），既没有 找到多项式类型算法，也没有证明这样算法不存在，即无法 判断是否难解

P、NP问题

P问题

Polynomial类型问题

• 非正式定义：易解的问题，即能够在多项式时间内求解的 问题（计算机范畴）

• 正式定义：能够用确定性算法在多项式时间内求解的 判定问题

• 多项式时间内求解：排除难解问题

• 判定问题：很多重要问题可以化简为更容易研究的判断问题 ，虽然原始表达形式不是判定问题

NP问题

Nondeterministic Polynomial类型问题：可以用不确定多项式 算法求解的判定问题

• NP问题虽然计算上对问题求解困难，但是在计算上判定待定结 是否解决问题是简单的：可以在多项式时间内完成

• 大多数判断问题都是属于NP类型的

  • $P \subseteq NP$：如果问题属于P，在不确定算法验证 阶段忽略猜测

  • 还包括以下没有找到多项式算法、也没有证明算法不存在 的组合优化问题的判定版本

    • 哈密顿回路问题
    • 旅行商问题
    • 背包问题
    • 划分问题
    • 装箱问题
    • 图着色问题
    • 整数线性规划问题

• $P \overset ? = NP$：P和NP问题是否一致，计算机科学理论 中最重要的未解之谜

  • P = NP意味着虽然没有找到，但能够在多项式时间内求解 许多组合优化问题确实存在

NPC问题

NP Complete问题

• 属于NP问题种，和该类型其他问题难度一致

• 证明问题属于NP问题比较简单

• NP中其他任何问题（已知或未知）可以在多项式时间内化简为 NPC问题

• 直接证明任何NP问题都可以在多项式时间内化简为当前问题 比较困难

• 常常利用多项式规约特性，证明某个确定NPC问题可以 多项式规约为当前问题

• 判定问题相互转换例

  • 哈密顿回路问题中图G映射加权图$G^{‘}$，G中存在边在 权重为1，不存在边权重为2，则哈密顿回路问题转换为$G^{‘}$ 是否存在长度不超过$|V|$的哈密顿回路，即旅行商问题的等价

• NPC问题案例

  • CNF-Satisfied Problem：合取范式可满足性问题，首个 被发现NPC问题

  • 前面提到的著名NP问题都是NPC问题

    • 包括哈密顿回路问题？？？

• 仅仅得到一个NPC问题的多项式确定算法，所有NP问题可以 在多项式时间内求解

  • 则$P = NP$

  • 即对于所有类型判定问题而言，检验待定解、在多项式时间 内求解在复杂性商没有本质区别

• 而NPC问题可以被其他NP问题转换而来意味着，NPC问题目前不 存在对所有实例通用的多项式时间算法

NP-Hard问题

NP-Hard问题：所有NP问题都可以通过多项式规约到其

• 不满足NPC问题第一个条件，可以不是NP问题

• 其范围包含NPC问题，前述组合优化问题最优版本也是NP-Hard

• 可以理解为：至少和NPC问题一样困难的问题

Reference

Polynomially Reducible

判定问题$D_1$可以多项式规约为判定问题$D_2$，条件是存在 函数t可以把$D_1$的实例转换为$D_2$的实例，满足

• t把$D_1$所有真实例映射为$D_2$真实例，把$D_1$所有假实例 映射为$D_2$假实例

• t可以用多项式算法计算

CNF-Satisfied Problem

合取范式满足性问题：能否设置合取范式类型的布尔表达式中布尔 变量值，使得整个表达式值为真

• 每个布尔表达式都可以表达为合取范式