算法设计与分析课程笔记
算法设计与分析 王东滨
第一章 算法概述
算法
能够对一定规范的输入，在有限时间内活的所要求的输出。
不同的算法可能用不同的时间、空间或效率解决问题。
算法是有穷的指令序列：
- 输入：有零或若干个外部提供的量作为算法的输入
- 输出：算法产生至少一个量作为输出
- 确定性：组成算法的每条指令是清晰，无歧义的
- 有穷性：算法中每条指令的执行次数是有限的，执行每条指令的时间也是有限的
程序
程序是算法用某种程序设计语言的具体实现
程序可能不满足算法的性质。
操作系统是在一个无限循环中执行的程序，因而不是一个算法
问题求解
理解问题→精确解或近似解选择数据结构算法设计策略→设计算法→证明正确性→分析算法→设计程序
算法复杂性
算法复杂性 = 算法所需要的计算机资源
算法时间复杂性T(n)
算法空间复杂性S(n)
其中n是问题的规模（输入大小）
C=F(N,I,A)
C：算法复杂性
N：解的问题的规模
I：算法的输入
A：算法本身
*F( N，I，A )*：由参数确定的三元函数
***时间复杂性 T= T ( N，I，A ) ；空间复杂性 S= S ( N，I，A )*
通常A隐含在复杂性函数名当中，简写为：
T= T ( N，I) ；S=S ( N，I)
算法的时间复杂性
1）最坏情况下的时间复杂性
$$
T_{\max}(n)=\max {T(I)|\mathrm{size}(I)＝n}
$$
2）最好情况下的时间复杂性
$$
T_{\min}(n)=\min {T(I)|\mathrm{size}(I)＝n}
$$
3）平均情况下的时间复杂性
$$
T_{\min}(n)=\sum_\mathrm{size(I)=n} p(I)T(I)
$$
其中I是问题的规模为n的实例，p(I)是实 例I出现的概率算法渐进复杂性
算法渐近复杂性
$$
T(n)\rightarrow \infty \
$$
$$
(T(n)-t(n))/T(n)\rightarrow 0 , \mathrm{as}\ n \rightarrow \infty
$$
t(n)是T(n)的渐近性态，为算法的渐近复杂性。在数学上，t(n)是T(n)的渐近表达式，是T(n)略去低阶项留下的主项
$$
\mathrm{as}\ n \rightarrow \infty
$$
t(n)渐进于T(n)， t(n)替代T(n)作为算法的复杂性度量
渐近分析的记号
渐进上界记号O
f(n) = O(g(n))
- $$
{存在正常数c和n_0,使得对所有n\ge n_0有 - 0 \le cg(n) \le f(n) }
$$
渐进下界记号Ω
f(n) =Ω(g(n))
- $$
{存在正常数c和n_0,使得对所有n\ge n_0有 - 0 \le f(n) \le cg(n) }
$$
非紧上界记号o
f(n) = o(g(n))
$$
{
对于任何正常数c>0，存在正数和n_0 \ge 0
使得对所有n \ge n_0有: 0 \le cg(n) < f(n) }\
等价于 \frac{f(n)}{g(n)} \rightarrow c\ ,\ as \ n \rightarrow \infty
$$
非紧下界记号ω
f(n) = ω(g(n))
$$
{对于任何正常数c>0，存在正数和n_0 \ge 0使得对所有n \ge n_0有: 0 \le f(n) < bcg(n) }
\
等价于\frac{f(n)}{g(n)} \rightarrow c\ ,\ as \ n \rightarrow \infty
$$
$$
f(n) \in \omega(g(n))\Leftrightarrow g(n) \in o(f(n))
$$
紧渐近界记号Θ
f(n) =* Θ *(g(n))
当且仅当f*(n) = O(g(n))且*f(n) =ω(g(n)) ， f(n) 与g(n)同阶
$$
{存在正常数c_1,c_2和n_0使得对所有n \ge n_0有：c_1g(n) \le f(n)
\le c2g(n) }
$$
定理1：
$$
\Theta(g(n)) = O(g(n)) \cap \omega(g(n))
$$
小结
重点
$$
算法复杂度定义、 O(g(n))、 \omega(g(n))
$$
难点
$$
O(f(n))+O(g(n)) = O(max{f(n),g(n)}) \
O(f(n))+O(g(n)) = O(f(n)+g(n)) \
O(f(n))*O(g(n)) = O(f(n)*g(n))
$$
第二章 递归与分治策略
分治法的设计思想是，将一个难以直接解决的大问题， 分割成一些规模较小的相同问题，以便各个击破，分而治之。
递归的概念
直接或间接地调用自身的算法称为递归算法。
用函数自身给出定义的函数称为递归函数。
例1 阶乘函数
阶乘函数
$$
n!=\begin{cases}1 && n=0\ n(n-1)!&& n>0\end{cases}
$$
边界条件与递归方程是递归函数的二个要素，递归函 数只有具备了这两个要素，才能在有限次计算后得出 结果。
例2 Fibonacci数列
无穷数列1,1,2,3,5, 8 , 13 , 21 , 34 , 55 , … … , 称 为Fibonacci数列。它可以递归地定义为：
$$
F(n)=\begin{cases}1 && n=0\ 1&& n=1\ F(n-1)+F(n-2)&& n>1\end{cases}
$$
前面例中的函数都可以找到相应的非递归方式定义：
$$
n!=1 ·2 · 3 … …(n- 1) ·n\ F(n)=\frac{1}{\sqrt{5}}((\frac{1+\sqrt{5}}{2})^{n+1}-\frac{1-\sqrt{5}}{2})^{n+1})
$$
例3 Ackerman函数
当一个函数及它的一个变量是由函数自身定义时，称这个函数是双递归函数。Ackerman 函数A(n,m) 定义如下：
$$
A(1,0)=2\ A(0,m)=1 \qquad m\ge 0\ A(n,0)=n+2 \qquad n\ge 2\ A(n,m)=A(A(n-1,m),m-1)\qquad n,m\ge 1
$$
A(n,m) 的自变量m 的每一个值都定义了一个单变量函数：
■ M=0 时， A(n,0)=n+2
■ M=1 时 ，A(n,1)=A(A(n-1,1),0)=A(n-1,1)+2, 和A(1,1)=2故 A(n,1)=2*n
■ M=2 时， A(n,2)=A(A(n-1,2),1)=2A(n-1,2), 和A(1,2)=A(A(0,2),1)=A(1,1)=2, 故A(n,2)= 2^n。
■ M=3 时，类似的可以推出
$$
2^{2^{2^{ \dots^{2} }}}
$$
■ M=4 时， A(n,4)的增长速度非常快，以至于没有适当的数学式 子来表示这一函数。
本例中的Ackerman 函数却无法找到非递归的定义。
例4 排列问题
设计一个递归算法生成n个元素{r,r₂ ,…,r}的全排列。
设R={r₁ ,r₂…,rn}是要进行排列的n个元素， Ri=R- {ri}。 集合X中元素的全排列记为perm(X)。
(r)perm(X) 表示在全排列perm(X) 的每一个排列前加上前 缀得到的排列。 R 的全排列可归纳定义如下：
当n=1 时， perm(R)=(r), 其 中r是集合R 中唯一的元素；
当n>1 时， perm(R) 由(r₁)perm(R₁),(r₂)perm(R₂),., (rn)perm(Rn)构成。
例5 整数划分问题
将正整数n表示成一系列正整数之和： n=n₁+n₂+…+nk, 其中n₁ ≥n₂ ≥… ≥nx≥1,k≥1。
正整数n的这种表示称为正整数n的划分。求正整数n的不 同划分个数。
例如正整数6有如下11种不同的划分：
6;
5+1;
4+2,4+1+1;
3+3,3+2+1,3+1+1+1;
2+2+2,2+2+1+1,2+1+1+1+1;
1+1+1+1+1+1。
在本例中，如果设p(n)为正整数n的划分数，则难以找到递归关 系，因此考虑增加一个自变量：将最大加数n 不大于m 的划分 个数记作q(n,m)。 可以建立q(n,m)的如下递归关系。
q(n,n)=1+q(n,n- 1);
正整数n的划分由n₁=n 的划分和n≤n-1 的划分组成。
q(n,m)=q(n,m- 1)+q(n-m,m),n>m>1;
正整数n的最大加数n,不大于m 的划分由n₁=m 的划分和 n₁ ≤m-1 的划分组成。
$$
q(n,m)=\begin{cases}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{cases}
$$
例6 Hanoi塔问题
设a,b,c是3个塔座。开始时，在塔座a上有一叠共n个圆盘，,这 些圆盘自下而上、由大到小地叠在一起。各圆盘从小到大编号 为1,2 n, 现要求将塔座a上的这一叠圆盘移到塔座b 上，并仍按同样顺序叠置。在移动圆盘时应遵守以下移动规则：
规则1:每次只能移动1个圆盘；
规则2:任何时刻都不允许将较大的圆盘压在较小的圆盘之上；
规则3:在满足移动规则1和2的前提下，可将圆盘移至a,b,c中 任一塔座上。
递归小结
优点： 结构清晰，可读性强，而且容易用 数学归纳法来证明算法的正确性，因此它 为设计算法、调试程序带来很天方便。
缺点： 递归算法的运行效率较低，无论是 耗费的讦算时间还是占用的存储空间都比非递归算法要多。
解决方法：在递归算法中消除递归调用，使其转化为非递归算法。
1 、 采用一个用户定义的栈来模拟系统的递归调用工作栈。该方法通用性强，但本质上还是递归，只不过人工做了本来由编译器做的事情， 优化效果不明显。
2、 用递推来实现递归函数。
3 、通过变换能将一些递归转化为尾递归，从而迭代求出结果。
后两种方法在时空复杂度上均有较大改善， 但其适用范围有限。
分治法
分治法的适用条件
分治法所能解决的问题一般具有以下几个特征：
1)该问题的规模缩小到一定的程度就可以容易地解决；
2)该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质
3)利用该问题分解出的子问题的解可以合并为该问题的解；
4)该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。
人们从大量实践中发现，在用分治法设计算法时， 最好使子问题的规模大致相同。即将一个问题分成 大小相等的k个子问题的处理方法是行之有效的。
这种使子问题规模大致相等的做法是出自一种平衡 (balancing) 子问题的思想，它几乎总是比子问题 规模不等的做法要好。
一个分治法将规模为n的问题分成k个规模为n/m 的子问题去 解。设分解阀值n0=1, 且adhoc 解规模为1的问题耗费1个单位 时间。再设将原问题分解为k个子问题以及用merge 将k个子问 题的解合并为原问题的解需用f(n)个单位时间。用T(n)表示该分 治法解规模为|P|=n的问题所需的计算时间，则有：
$$
T(n)=\begin{cases})(1)&& n=1\ kT(n/m)+f(n)&& n>1\end{cases}
$$
通过迭代法求得方程的解：
$$
T(n)=n^{log_m k}+\sum_{j=0}^{log_m n-1}k^jf(n/m^j)
$$
二分搜索技术
给定已按升序排好序的n个元素a[0:n-1], 现要在这n个元素中找 出一特定元素x。
分析：很显然此问题分解出的子问题相互独立，即在a[i]的前 面或后面查找x是独立的子问题，因此满足分治法的适用条件。
据此容易设计出二分搜索算法：
1 | template<class Type> |
算法复杂度分析：
每执行一次算法的while循环， 待搜索数组的大小减少一半。因此，在最坏情况下， while循环被执行了 O(logn)次。循环体内运算需要O(1)时间，因此整个算法在最坏情况下 的计算时间复杂性为O(logn)。
大整数的乘法
请设计一个有效的算法，可以进行两个n 位大整数的乘法运算
直接计算： O(n²)
$$
T(n)=\begin{cases}O(1)&n=1\ 4T(n/2)+O(n)&n>1 \end{cases}\T(n)=O(n^2)\ \ \ X=a2^{n/2}+b \ \ \ \ \ Y=c2^{n/2}+d\ XY=ac2^n+(ad+bc)2^{n/2}+bd
$$
复杂度分析
$$
T(n)=\begin{cases}O(1)&n=1\ 3T(n/2)+O(n)&n>1 \end{cases}\T(n)=O(n^{\log3})=O(n^{1.59})
$$
Strassen矩阵乘法
传统方法： O(n³)
A 和B 的乘积矩阵C 中的元素C[i,j]定义为：
$$
c[i][j]=\sum^n_{k=1}A[i][k]B[k][j]
$$
若依此定义来计算A 和B的乘积矩阵C, 则每计算C的一个元素C[i][j], 需要做n次乘法和n-1次加法。因此，算出矩阵C 的个元素所需的计算时间为O(n3)
假设矩阵A
和矩阵B都是$N*N(N=2^n)$的方矩阵，求C=AB，如下所示：
$C_{11}=A_{11}B_{11}+A_{12}B_{21}\
C_{12}=A_{11}B_{12}+A_{12}B_{22}\
C_{21}=A_{21}B_{11}+A_{22}B_{21}\
C_{22}=A_{21}B_{12}+A_{22}B_{22}\$
$$
T(n)=\begin{cases}O(1)&n=2\ 8T(n/2)+O(n^2)&n>2 \end{cases}\T(n)=O(n^{3})
$$
使用递归算法：
$$
P_1 =A_{11} · B_{12} - A_{11} · B_{22}\
P_2 =A_{11}·B_{22} + A_{12}·B_{22}\
P_3 =A_{21} · B_{11} + A_{22}· B_{11}\
P_4 =A_{22} · B_{21} - A_{22} · B_{11}\
P_5 = A_{11} · B_{11} + A_{11} · B_{22} + A_{22} · B_{11} + A_{22} · B_{22}\
P_6 = A_{12} · B_{21} + A_{12}· B_{22 }- A_{22} · B_{21} - A_{22} · B_{22}\
P_7 = A_{11}·B_{11} + A_{11} · B_{12 }- A_{21}·B_{11} - A_{21} · B_{12}
$$
$$
C_{11} = P_5 + P_4 – P_2 + P_6\
C_{12}=P_1+P_2\
C_{21}=P_3 + P_4\
C_{22} = P_5 + P_1 - P_3 -P_7
$$
复杂度分析
$$
T(n)=\begin{cases}O(1)&n=2\ 7T(n/2)+O(n^2)&n>2 \end{cases}\T(n)=O(n^{\log7})=O(n^{2.81})
$$
棋盘覆盖
在一个2k×2k个方格组成的棋盘中，恰有一个方格与其它方格不 同，称该方格为一特殊方格，且称该棋盘为一特殊棋盘。在棋 盘覆盖问题中，要用图示的4种不同形态的L型骨牌覆盖给定的 特殊棋盘上除特殊方格以外的所有方格，且任何2个L型骨牌不 得重叠覆盖。
当k>0 时，将2k×2k棋盘分割为4个2k1×2k-1 子棋盘(a)所示。
特殊方格必位于4个较小子棋盘之一中，其余3个子棋盘中无特 殊方格。为了将这3个无特殊方格的子棋盘转化为特殊棋盘，可 以用一个L型骨牌覆盖这3个较小棋盘的会合处，如 (b)所示，从 而将原问题转化为4个较小规模的棋盘覆盖问题。递归地使用这 种分割，直至棋盘简化为棋盘1×1。
合并排序
基本思想： 将待排序元素分成大小大致相同的2个子集合，分 别对2个子集合进行排序，最终将排好序的子集合合并成为所 要求的排好序的集合。
最坏时间复杂度： O(nlogn)
平均时间复杂度： O(nlogn)
辅助空间： O(n)
快速排序
对输入的子数组a[p:r],按以下三个步骤进行排序：
1 ) 分 解 (divide): 以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]
2)递归求解：通过递归调用快速排序算法，分别对a[p:q-1]和a[q+1:r]进行排序
3)合并：由于a[p:q-1]和a[q+1:r]的排序是就地进行的，因此在a[p:q-1]和a[q+1:r]都已排好序了，不需执行任 何计算， a[p:r]则已排好序了。
最坏情况：发生在划分过程产生的两个区域分别包含 n-1个元素和1个元素的时候。
最 坏 时 间 复 杂 度 ： O ( n²)
最好情况：每次划分所取的基准都恰好为中值。
最 好 时 间 复 杂 度 ： O ( n l o g n )
线性时间选择
给定线性序集中n个元素和一个整数k,1≤k≤n,要求找出这n个 元素中第k 小的元素
在最坏情况下，算法randomizedSelect需要$O(n^2)$计算时间 但可以证明，算法randomizedSelect可以在O(n)平均时间内 找出n个输入元素中的第k小元素。
●将n个输入元素划分成[n/57个组，每组5个元素，只可能 有一个组不是5个元素。用任意一种排序算法，将每组中的 元素排好序，并取出每组的中位数，共[n/5个 。
●递归调用select 来找出这[ n/57个元素的中位数。如果 「n/57是偶数，就找它的2个中位数中较大的一个。以这个元素作为划分基准。
$$
T(n)=\begin{cases}C_1&n<75\ C_2n+T(n/5)+T(3n/4)&n>75\end{cases}\T(n)=O(n)
$$
循环赛日程表
设计一个满足以下要求的比赛日程表：
(1)每个选手必须与其他n-1个选手各赛一次；
(2)每个选手一天只能赛一次；
(3)循环赛一共进行n-1天。
按分治策略，将所有的选手分为两半， n个选手的比赛日程表 就可以通过为n/2个选手设计的比赛日程表来决定。递归地用 对选手进行分割，直到只剩下2个选手时，比赛日程表的制定 就变得很简单。这时只要让这2个选手进行比赛就可以了。
第3章 动态规划
算法总体思想
动态规划算法与分治法类似，其基本思想也是将待求解问题分
解成若干个子问题
但是经分解得到的子问题往往不是互相独立的。不同子问题的
数目常常只有多项式量级。在用分治法求解时，有些子问题被
重复计算了许多次。
矩阵连乘问题
完全加括号的矩阵连乘积可递归地定义为：
（1）单个矩阵是完全加括号的；
（2）矩阵连乘积A是完全加括号的，则A可表示为2个完全加括号的矩阵连乘积 和的乘积并加括号，即A=(BC)
◼ 由于矩阵乘法满足结合律，所以计算矩阵的连乘可以有许多不
同的计算次序。这种计算次序可以用加括号的方式来确定。
◼ 若一个矩阵连乘积的计算次序完全确定，也就是说该连乘积已
完全加括号，则可以依此次序反复调用2个矩阵相乘的标准算
法计算出矩阵连乘积
◼ 特征：计算A[i:j]的最优次序所包含的计算矩阵子链 A[i:k]和A[k+1:j]的次序也是最优的。
◼ 矩阵连乘计算次序问题的最优解包含着其子问题的最优解。这种性质称为最优子结构性质。问题的最优子结构性质是该问题可用动态规划算法求解的显著特征。
建立递归关系
设计算$A_i* A_{i+1}… A_j$ 的矩阵连乘积表示为$A[i:j]$，$1≤i≤j≤n$，所需
要的最少的乘次数为$m[i,j]$，则原问题的最优值可表示为$m[1,n]$
◼ 当$i=j$时，$A[i:j]=Ai$，因此，$m[i,i]=0，i=1,2,…,n$
◼ 当$i<j$时，
若$A [i:j]$ 在$A_k$和$A_{k+1}$间断开为最优，则：
$A[i:j] = A[i:k] A[k+1:j], i⩽k<j$
$A[i:k]$为 $A[i]$的行数 $x A[k]$的列数 的矩阵
$A[i]$的行 $= A[i-1]$的列 $= p_{i-1}$ ，$A[k]$的列数$= p_k$
故：$A[i:k]$ 为$p_{i-1}$$ p_k$*的矩阵$A[k+1:j]$为$p_k$$ p_j$*的矩阵,则所需计算次数： $m[i, j] = m[i,k]+ m[k +1, j]+ p_{i−1}p_kp_j$
用动态规划法求最优解
1 | void MatrixChain(int *p，int n，int **m，int **s) |
动态规划算法的基本要素
一、最优子结构
- 矩阵连乘计算次序问题的最优解包含着其子问题的最优解。这种性质称为最优子结构性质。
- 在分析问题的最优子结构性质时，所用的方法具有普遍性：首先假设由问题的最优解导出的子问题的解不是最优的，然后再设法说明在这个假设下可构造出比原问题最优解更好的解，从而导致矛盾。
- 利用问题的最优子结构性质，以自底向上的方式递归地从子问题的最优解逐步构造出整个问题的最优解。最优子结构是问题能用动态规划算法求解的前提。
同一个问题可以有多种方式刻划它的最优子结构，有些表示方法的求解速度更快（空间占用小，问题的维度低）
二、重叠子问题
- 递归算法求解问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算多次。这种性质称为子问题的重叠性质。
- 动态规划算法，对每一个子问题只解一次，而后将其解保存在一个表格中，当再次需要解此子问题时，只是简单地用常数时间查看一下结果。
- 通常不同的子问题个数随问题的大小呈多项式增长。因此用动态规划算法只需要多项式时间，从而获得较高的解题效率。
三、备忘录方法
备忘录方法的控制结构与直接递归方法的控制结构相同，区别在于备忘录方法为每个解过的子问题建立了备忘录以备需要时查看，避免了相同子问题的重复求解。
最长公共子序列
给定序列$X={x_1,x_2,…, x_m}$，另一序列$Z={z_1,z_2,…, z_m}$。
若Z是X的子序列，是指存在一个严格递增下标序列${i_1,i_2,…,i_k}$，使得对于所有$j=1,2,…,k$有：$z_j= x_{ij}$ 。
例如：序列$Z={B，C，D，B}$是序列$X={A，B，C，B，D，A，B}$的子序列，相应的递增下标序列为${2，3，5，7}$。给定2个序列X和Y，当另一序列Z既是X的子序列又是Y的子序列时，称Z是序列X和Y的公共子序列。
给定2个序列$X={x_1,x_2,…, x_m}$和$Y={y_1,y_2,…, y_n}$，找出X和Y的最长公共子序列。
设序列$X={x_1,x_2,…, x_m}$和$Y={y_1,y_2,…, y_n}$的最长公共子序列为$Z={z_1,z_2,…,z_k}$ 则
(1)若$x_m=y_n$，则$z_k=x_m=y_n$，且$Z_{k-1}$是$X_{m-1}$和$Y_{n-1}$最长公共子序列。
(2)若$x_m≠y_n$且$z_k≠x_m$，则$Z$是$X_{m-1}$和$Y$的最长公共子序列。
(3)若$x_m≠y_n$且$z_k≠y_n$，则$Z$是$X$和$Y_{n-1}$的最长公共子序列
其中，$X_{m-1}={x_1,x_2,…,x_{m-1}}$， $Y_{n-1} ={y_1,y_2,…,y_{n-1}}$， $Z_k-1 ={z_1,z_2,…,z_{k-1}}$
由最长公共子序列问题的最优子结构性质建立子问题最优值的递归关系。用c[i][j]记录序列和的最长公共子序列的长度。其中， $X={x_1,x_2,…, x_m}$;$Y={y_1,y_2,…, y_n}$。当i=0或j=0时，空列是Xi和Yj的最长公共子序列。故此时C[i][j]=0。其它情况下，由最优子结构性质可建立递归关系如下：
$$
c[i][j]=\begin{cases} 0&i=0,j=0\ c[i-1][j-1]+1&i,j>0;x_i=y_j\ max{c[i][j-i],c[i-1][j]}&i,j>0;x_i\neq y_j\end{cases}
$$
wechat- alipay
