算法理论复习

本文参考：胡神笔记：https://junyaohu.github.io/2021/10/26/%E3%80%8A%E7%AE%97%E6%B3%95%E5%AF%BC%E8%AE%BA%E3%80%8B%E7%AC%94%E8%AE%B0/

1.算法概叙

算法复杂性和算法复杂性的计算O记，以及倍率计算

1.1 算法概念

1.1.1 概念

一系列将问题的输入转换为输出的计算或操作步骤。

1.1.2 性质

• 输入 有外部提供的量作为算法的输入。
• 输出 算法产生至少一个量作为输出。
• 确定性 组成算法的每条指令是清晰、无歧义的。
• 有限性 算法中每条指令的执行次数是有限的，执行每条指令的时间也是有限的。

1.2 算法复杂性

算法的复杂性(C):

算法执行所需的时间和空间的数量。

$$T=T(N, I)=\sum_{i=1}^{k} t_{i} e_{i}(N, I)$$

平均情况

$$T_{\text {avg }}(N)=\sum_{I \in D_{N}} P(I) T(N, I)=\sum_{I \in D_{N}} P(I) \sum_{i=1}^{k} t_{i} e_{i}(N, I)$$

渐进性态

$$\frac{T(N)-\overset{\thicksim}{T}(N)}{T(N)} \rightarrow 0$$

大O表示法(算法运行时间的上限 )

就是逼近的一个上界，可以那泰勒的上界来理解。

大W表示法(算法运行时间的下限）

下界

算法复杂度排序：

1.3 NP问题判断

这部分不考，但既然学算法，应该了解一下这些NP难题

NP(Nondeterministic Polynomially，非确定性多项式)类问题是指一个复杂问题不能确定是否在多项式时间内找到答案，但是可以在多项式时间内验证答案是否正确。

P问题是一个判定问题类，这些问题可以用一个确定性算法在多项式时间内判定或解出。

NP问题是指可以在多项式时间内被非确定机解决的问题。通常它们的时间复杂度都是指数变量。

2.递归与分治

2.1 递归

递归定义 用函数自身定义的函数

递归函数两个要素 边界条件与递归方程

递归算法转化为非递归算法

1. 直接转化法：直接用循环结构的算法替代递归算法，不需要使用栈
2. 用栈模拟系统的运行过程，通过分析只保存必须保存的信息，从而用非递归算法替代递归算法，需要使用栈

整数划分

对于数据n，最大加数不大于m的划分个数记作$q(n,m)$

$$q(n,m) = \left\{\begin{matrix} 1 & n = 1,m = 1\\ q(n,n) &n<m \\ 1+q(n,n-1) &n = m \\ q(n,m-1)+q(n-m,m) &n>m>1 \end{matrix}\right.$$

2.2 分治

分治法的设计思想是：将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。

分治策略是：对于一个规模为n的问题，若该问题可以容易地解决（比如说规模n较小）则直接解决，否则将其分解为k个规模较小的子问题，这些子问题互相独立且与原问题形式相同，递归地解这些子问题，然后将各子问题的解合并得到原问题的解。这种算法设计策略叫做分治法。

分治法所能解决的问题一般具有以下几个特征：

1) 该问题的规模缩小到一定的程度就可以容易地解决

2) 该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质。

3) 利用该问题分解出的子问题的解可以合并为该问题的解；

4) 该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子子问题。

算法模板

Divide-and-Conquer(P)
  	if |P|≤n0
		then return(ADHOC(P))
	将P分解为较小的子问题 P1 ,P2 ,...,Pk
	for i←1 to k
		do yi ← Divide-and-Conquer(Pi) //递归解决Pi
	T ← MERGE(y1,y2,...,yk) //合并子问题
	return(T)

2.3 二分搜索

问题描述 给定已按升序排好序的n个元素a[1:n]，现要在这n个元素中找出一特定元素x

参考：https://www.programmercarl.com/0704.%E4%BA%8C%E5%88%86%E6%9F%A5%E6%89%BE.html#%E6%80%9D%E8%B7%AF

俩种思路。

2.4 合并排序和快速排序

问题描述 数组排序

合并排序

Merge-sort(A, p, r)
	if (p < r)
		q = (p + r) / 2
	Merge-sort(A, p, q)
	Merge-sort(A, q+1, r)
	Merge(A, p, q, r)

复杂度

$$\begin{array} {X} T(n) = O(nlogn) =\left\{\begin{matrix} O(1) & n=1\\ 2T(\frac{n}{2} ) + O(n) & n>1 \\ \end{matrix}\right. \end{array}$$

快速排序

Partition(A,p,r) //p、r为数组下标
	x = A[r]   //将最后一个元素作为主元素
	i = p-1 // i指向的是比主元素小的位置，
	for  j = p  to  r-1     
	//从第一个元素开始到倒数第二个元素结束，比较确定主元素的位置
		do  if  A[j] <= x
			then  i = i+1 
      //如果比主元素小，则把i=i+1的位置上的元素和j位置发现小元素互换
			exchange A[i] <-> A[j]
	exchange A[i+1]<->A[r]   //最终确定主元的位置
	return i+1   //返回主元的位置
End

QuickSort(A,p,r)
	if p<r
	q = Partition(A,p,r)    //确定划分位置
	QuickSort(A,p,q-1)     //子数组A[p...q-1]
	QuickSort(Q,q+1,r)     //子数组A[q+1...r]
End

步骤

1. 分解：以a[p]为基准元素将a[p:r]划分成3段a[p:q-1],a[q]和a[q+1:r]，使a[p:q-1]中任意一个元素小于等于a[q]，而a[q+1:r]中任何一个元素大于等于a[q]，下标q在划分过程中确定

2. 递归求解：通过递归调用快速排序算法分别对a[p:q-1]和a[q+1:r]进行排序

3. 合并

最坏情况，已经排好，$O(n^2)$
最好情况，每次划分大小都是$\frac{n}{2}$，$O(nlogn)$

2.5 大整数乘法

问题描述 XY是n位二进制整数，计算他们的乘积XY

$$\begin{array} {X}X=A2^{\frac{n}{2}}+B, Y=C2^{\frac{n}{2}}+D \\ XY = AC2^n+(AD+BC)2^{\frac{n}{2} }+BD \\ =AC2^n+((A-B)(D-C)+AC+BD)2^{\frac{n}{2}}+BD \\ \end{array}$$

复杂度

$$T(n) = O(n^{log3}) =\left\{\begin{matrix} O(1) & n=1\\ 3T(\frac{n}{2} ) + O(n) & n>1 \\ \end{matrix}\right.$$

2.6 线性时间选择

无序排列中求n个元素中第k小的元素（主要求中位数）。(类似快排)

解释

根据随机产生的基准点，将元素分为2组，基准点包含在第1组中；如果k<=j，则第k小元素落在a段，为a段的第k小元素；如果k>j，则a段的所有元素都比第k小元素还要小，第k小元素落在b段，为b段中的第k-j小元素（-j的含义是去掉a段的元素总个数）

最坏情况，分成两个1和n-1的子问题，$O(n^2)$

最好情况，每次都产生$\frac{n}{2}$大小的子问题，$O(n)$

例题看书比较好。

3.动态规划

3.1 动态规划原理

动态规划，英文：Dynamic Programming，简称DP，如果某一问题有很多重叠子问题，使用动态规划是最有效的。

这里俩性质：最优子结构性质和子问题重叠性质

1. 最优子结构性质（分析问题是否满足最优性原理（用反证法）：①先假设由问题的最优解导出的子问题的解不是最优的；②再证明在这个假设下可构造出比原问题最优解更好的解，从而导致矛盾）
2. 子问题重叠性质（子问题不相互独立，重复出现，只在第一次遇到时加以求解，并把答案保存起来，以后再遇到时不必重新求解）

所以动态规划中每一个状态一定是由上一个状态推导出来的，这一点就区分于贪心，贪心没有状态推导，而是从局部直接选最优的。

编程方法：
动态规划的解题步骤
对于动态规划问题，我将拆解为如下五步曲，这五步都搞清楚了，才能说把动态规划真的掌握了！

1、确定dp数组（dp table）以及下标的含义
2、确定递推公式
3、dp数组如何初始化
4、确定遍历顺序
5、举例推导dp数组

动态规划算法设计步骤

• 分析最优解的性质，并刻划其结构特征；
• 递归地定义最优值
• 以自底向上的方式计算出最优值；
• 根据计算最优值时得到的信息，构造最优解。

3.2 矩阵连乘

问题描述 每计算出一个元素，需要q次乘法，最终得到的矩阵是p×r矩阵，有p×r个元素，因此，计算C需要的乘法次数为q×p×r。每次要选择较小的q×p×r。给定n个矩阵｛A1,A2,…,An｝，其中Ai与Ai+1是可乘的，且i=1,2⋯,n-1,如何确定计算矩阵连乘积的计算次序，使得计算矩阵连乘的数乘次数最少。

$$m[i][j]=\left\{\begin{array}{cc} 0 & i=j \\ \min_{i\leq{k}<j} \{m[i][k]+m[k+1][j]+p_{i-1}p_kp_j\} & i<j \end{array}\right.$$

解释 矩阵连乘积从$A_i$到$A_j$定义为A[i:j]，A[i:j]最少的乘法次数定义为m[i,j]，最优断开位置k记为𝑠[i,j]=k，

$T(n)=O(n^3)$

例题

计算矩阵连乘积A[1:6]的最少数乘次数，其中各矩阵的维数分别为p=[30,35,15,5,10,20,25]

3.3 最长公共子序列

问题描述：给定两个序列$X=\{x_1,x_2,\cdots,x_m\}$和$Y=\{y_1,y_2,\cdots,y_n\}$，要求找出$X$和$Y$的一个最长公共子序列。

$$c[i][j]=\left\{\begin{array}{cc} 0 & i=0, j=0 \\ c[i-1][j-1]+1 & i, j>0 ; x_{i}=y_{j} \\ \max \{c[i-1][j], c[i][j-1]\} & i, j>0 ; x_{i} \neq y_{j} \end{array}\right.$$ $$b[i][j]=\left\{\begin{array}{cc} 1 & c[i][j] = c[i-1][j-1] \\ 2 & c[i][j] = c[i-1][j] \\ 3 & c[i][j] = c[i][j-1] \end{array}\right.$$

解释 c[i,j]记录序列$X_i$和$Y_j$的最长公共子序列长度，b[i,j]可以记录是哪种类型。在c表中从最右下角的那个元素开始，看b表中对应位置的值，如果为1，则在c表中从当前位置往左上角走；如果为2，则在c表中从当前位置往正上方走；如果为3，则在c表中从当前位置沿水平方向往后退一位；依次类推，直到c表中箭头退到c[0，0]为止。

补充 两个序列的最长公共子序列不唯一，不影响最长公共子序列的长度；但是可能会产生不一样的公共子序列.

例题

给定两个序列为X=ABCBDAB和Y=BDCABA，求最长公共子序列。

3.4 图像压缩

问题描述 数字化图像是n×n的像素阵列。假定每个像素有一个0~255的灰度值，存储一个像素需8位。为了减少存储空间，采用变长模式，即不同像素用不同位数来存储。

1. 线性化：图片拉直，转换为$1×n^2$向量
2. 分段：分成连续的m段，每段像素存储位数相同，每段最多含256个像素点
3. 存放信息：第$i$段长度（8bit），第$i$段中像素存储位数（3bit）

$$\begin{matrix} s[i]=\min\limits_{1 \leq k \leq \min \{i,256\}}\{s[i-k]+k*bmax(i-k+1,i) \}+11 \\bmax(i,j)=\max\limits_{i\leq k \leq j}\{a[k]\} \end{matrix}$$

解释

假设s[i]是序列$\{p_1,p_2,…,p_i\}$的最优解，a[i]是第$i$个像素点的位数。

1. 假设$p_i$自成一段，则s[i]=s[i-1]+保存pi的代价
2. 取s[i]为min时对应的元素个数为k，s[i]=s[i-k]+保存最后k个像素的代价
3. 保存最后k个像素的代价=k*max{k个灰度值二进制位数}+11

例题

求像素序列4，6，5，7，129，138，1的最优分段。

3.5 电路布线

问题描述 确定将哪些连线安排在第一层上，使得该层上有尽可能多的连线且不相交

$$\begin{matrix} \scriptsize 当i=1时, \qquad Size(i,j) = \left\{\begin{matrix} 0 && j<\pi(1) \\1 && j \geq \pi (1) \end{matrix}\right. \\ \scriptsize 当i>1时,\qquad Size(i,j) = \left\{\begin{matrix} Size(i-1,j) && j<\pi(i) \\\max \{ Size(i-1,j),Size(i-1,\pi(i)-1)+1\} && j \geq \pi (i) \end{matrix}\right. \end{matrix}$$

解释 MNS(i,j)表示上面序号小于$i$，连接到下面的序号都小于$j$的不相交的集合，最后要求MNS(n,n)。如果$j=\pi(i)$，如果$(i,\pi(i))$不在MNS中，将i点删除没有影响，就是size(i,j)=size(i-1,j)，如果$(i,\pi(i))$在MNS中，就是size(i,j)=size(i-1,pi(i)-1)+1

例题

已知[(1 8)(2 7)(3 4)(4 2)(5 5)(6 1)(7 9)(8 3)(9 10)(10 6)]，求最大不相交情况

3.6 流水线调度

问题描述 n个作业要在两台机器M1和M2上进行加工。每个作业加工的顺序都是先在M1上加工，然后在M2加工。M1和M2加工作业$i$所需的时间分别为$a_i$ 和$b_i$。确定n个作业的最优加工顺序，使得加工完成所需的时间最少。

算法

1. 分为$N_1,N_2$集合存放 $N_1 = \{a_i\leq b_i\} ,N_2 = \{a_i > b_i\}$
2. $N_1$中作业按照$a_i$升序排序，$N_2$中作业按照$b_i$降序排序
3. $N_1$连接$N_2$，计算时间

例题

任务	J1	J2	J3	J4	J5	J6
工序1	30	120	50	20	90	110
工序2	80	100	90	60	30	10

3.7 0-1背包与完全背包

$$\begin{matrix} m(i,j) = \left\{\begin{matrix} m(i-1,j) && 0 \leq j<w_i \\ \max \{ m(i-1,j),m(i-1,j-w_i)+v_i\} && j \geq w_i \end{matrix}\right. \\ \\ m(0,j) = \left\{\begin{matrix} 0 && 0 \leq j<w_0 \\ v_0 && j \geq w_0 \end{matrix}\right. \end{matrix}$$

解释 m[i][j]表示可选择物品$i, i+1, …, n$时，背包容量为$j$装入的最大价值

例题

n=5,c=10,W={2,2,6,5,4},V={6,3,5,4,6}

4.贪心算法

听老师说是活题，那么建议参考：https://www.programmercarl.com/%E8%B4%AA%E5%BF%83%E7%AE%97%E6%B3%95%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80.html

刷点力扣涨涨见识

4.1贪心原理

思想 在贪婪算法中采用逐步构造最优解的方法。在每个阶段，都作出一个看上去最优的决策。它并不一定对所有问题都成功，因为不从整体最优加以考虑，贪心解法可能不是全局最优解，但是对某些问题特别简单、有效。

基本要素

1. 最优子结构性质 问题的最优解包含其子问题的最优解
2. 贪心选择性质 问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到，当前的选择和子问题的解无关，只和以往做出的选择有关

贪心算法一般分为如下四步：

• 将问题分解为若干个子问题
• 找出适合的贪心策略
• 求解每一个子问题的最优解
• 将局部最优解堆叠成全局最优解

4.2 活动安排

思考如下具有11个活动安排的问题？

在活动集合中选择最大的相容活动子集合

任务	1	2	3	4	5	6	7	8	9	10	11
start	0	4	4	5	3	1	8	6	8	12	2
end	3	6	5	6	8	4	11	10	12	14	13

start开始时间，end结束时间，按
任务按结束时间非减续排列
优先选取结束时间早的，判断是否相容
直到任务最后一个结束。

4.3 哈夫曼编码

前缀码 对每一个字符规定一个0,1串作为其代码，并要求任一字符的代码都不是其它字符代码的前缀，这种编码称为前缀码。

问题描述 找到使平均码长达到最小的前缀码编码方案

策略 频率小的字符，深度大。队列Q以f(c)为键值存放二叉树各结点，通过贪心选择，将最小频率的两个二叉树合并，然后将新树（频率为上述两个二叉树频率之和）插入Q中。$ T(n)=O(nlogn)$

证明贪心选择性质

设x和y是字符集C中具有最小频率的两个字符，证明存在C的最优前缀码，使x和y具有最长、相同的码长且仅最后一位编码不同。设二叉树T表示C的任意一个最优前缀码方案。只要证明可以对T做适当修改后，得到一棵新的二叉树T’， 新树中，x和y是最深叶子且为兄弟。同时，新树也是C的最优前缀码方案。

证明最优子结构性质

设T表示C的一个最优前缀码方案。x和y是树T中的叶子节点且为兄弟。z是它们的父亲。若将z看做是具有频率$f(z)=f(x)+f(y)$的字符，则证明树$T’=T-\{x,y\}$表示字符集$C’=C-\{x,y\} \bigcup \{z\}$的一个最优前缀码即可。

问题：

设在1000个字母的文章中各字母出现的频率为a:83, b:14, c:28, d:38, e:131, f:29, g:20, h:53，求最优编码。

4.3 最短路径

书上的吧，懒的写了，这个看这个就行了

4.4 最小生成树

参考数据结构，这个太简单了

4.5 0-1背包（可分割）

贪心策略

1. 计算每种物品的单价（性价比）$\frac{v_i}{w_i}$
2. 按物品单价从大到小排序
3. 优先选取物品单价高的，直到背包装满。

$n=3,c=20,W=\{18,15,10\},V=\{25,24,15\}$

补充几种贪心策略（但是都不能保证得到最优解）

1. 选择可以装入背包的价值最大的物品
2. 选择可装入背包的重量最小的物品
3. 选择可装入背包的$\frac{v_i}{w_i}$最大的物品（一般用来做回溯法或者分支限界的限界函数）

3.6最优装载

策略 重量最轻的先装$ T(n)=O(nlogn)$

策略：

1. 见货物重量按从小到大排序
2. 优先选取重量下的物品，直到无法装下为主

5.回溯法

5.1 回溯原理

这里很矛盾，书上的回溯有一点点离谱，感觉是极端的剪枝，考试还得按课本来。

算法框架

1. 子集树算法框架
   当所给的问题是从 个元素的集合 中找出 满足性质的子集时，相应的解空间树称为子集树

2. 排列树算法框架
   当所给问题是确定 个元素满足某种性质的排列时，相应的解空间树称为排列树

剪枝函数

1. 用约束函数在扩展结点处剪去不满足约束的子树；

2. 用限界函数剪去得不到最优解的子树

回溯法解决的问题都可以抽象为树形结构，所有回溯法的问题都可以抽象为树形结构！

因为回溯法解决的都是在集合中递归查找子集，集合的大小就构成了树的宽度，递归的深度，都构成的树的深度。

递归就要有终止条件，所以必然是一颗高度有限的树（N叉树）。

回溯法的效率

回溯法的性能如何呢，这里要和大家说清楚了，虽然回溯法很难，很不好理解，但是回溯法并不是什么高效的算法。

因为回溯的本质是穷举，穷举所有可能，然后选出我们想要的答案，如果想让回溯法高效一些，可以加一些剪枝的操作，但也改不了回溯法就是穷举的本质。

代码模板

void backtracking(参数) {
    if (终止条件) {
        存放结果;
        return;
    }

    for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
        处理节点;
        backtracking(路径，选择列表); // 递归
        回溯，撤销处理结果
    }
}

5.2 装载问题

问题描述 n个集装箱要装到2艘载重量分别为c1,c2的货轮，其中集装箱 $i$的重量为$w_i$。要求找到装载方案将这n个货箱装上这2艘轮船

解释 若装载问题有解, 采用如下策略可得一个最优装载方案：将第一艘轮船尽可能装满，将剩余的货箱装到第二艘轮船上。将第一艘船尽可能装满类似0-1背包问题

例题

n=4,c1=12,W={8,6,2,3}

5.3 0-1背包

解释 子集树。只要左儿子节点是一个可行结点，搜索就进入左子树（不超过背包重量）（约束剪枝）。在右子树中有可能包含最优解是才进入右子树搜索，否则将右子树剪去（利用单价贪心求解价值上限）（限界剪枝）。$cw$是背包当前重量，$M-cw$是背包剩余的空间，$cp$是当前总收益，$rp$是贪心算法剩余的物品收益，$bestw$记录当前最优价值，也就是判断$bp=cp+cp>bestw$是右节点的限界函数。（此外，回溯法解0/1背包的前置条件是物品已按$\frac{p_i}{w_i}$非增次序排序）

例题

M=110，w=(1,11,21,23,33,43,45,55)，v=(11,21,31,33,43,53,55,65)

6.分枝限定

和回溯无限接近，搞清楚优先队列的优先级就可以