算法设计与分析-总结

文章上次更新于2020年12月21日。

本总结并没有发挥事实作用。

我们考什么

要点

• 五种算法
• 几个点

题型

选择

2*10=20
都是基本概念，包含：

• 五种基本算法
• 以及他们的复杂度

填空

2*10=20

• 同上

简答

7*5=35

• 没讲

分析

25*1

贪心

• 建模
• 输入输出的约束条件
• 贪心局限
• 贪心实现

五种算法

• 递归与分治法
• DP法
• 贪心法
• 回溯法
• 分支界限法

理论

函数渐进的界

$O$

就是上界

定义： 设 $f$ 和 $g$ 是定义域为自然数集 $N$ 上的函数。
若存在正数 $c$ 和 $n_0$，使得对一切 $n \ge n_0$ 有 $0 \le f(n) \le c \cdot g(n)$ 成立，则称 $f(n)$ 的渐进的上界是 $g(n)$ ，记作 $f(n) = O(g(n))$ 。

$O(g(n))$表示的函数集合的函数是阶数不超过$g(n)$的函数。

例如：$f(n)=2\cdot n+2=O(n)$
证明：当$n>3$的时候，$2\cdot n +2<3n$，所以可选$n_0=3$,$c=3$，则$n>n_0$的时候，$f(n) < c\cdot (n)$，所以$f(n)=O(n)$。
现在再证明$f(n)=2n+2=O(n^2)$
证明：当$n>2$的时候，$2n+2<2n^2$，所以可选$n_0=2$,$c=2$,则$n>n_0$的时候，$f(n)< c\cdot (n^2)$，所以$f(n)=O(n^2)$。
同理可证$f(n)=O(n^a)$，$a>1$

$\Omega$

就是下界

定义： 设 $f$ 和 $g$ 是定义域为自然数集 $N$ 上的函数。
若存在正数 $c$ 和 $n_0$，使得对一切 $n \ge n_0$ 有 $0 \le c \cdot g(n)\le f(n) $ 成立，则称 $f(n)$ 的渐进的下界是 $g(n)$ ，记作 $f(n) = \Omega (g(n))$ 。

例如：$f(n)=2n^2+3n+2=\Omega (n^2)$
证明：当$n>4$的时候，$2n^2+3n+2>n^2$，所以可选$n_0=4$,$c=1$,则$n>n0$的时候，$f(n)>c\cdot (n^2)$，所以$f(n)=\Omega (n^2)$。
同理可证$f(n)=\Omega (n)$,$f(n)=\Omega (1)$

$\Theta$

$\Theta$记号介于大$O$记号和$\Omega$记号之间。他表示，存在正常数$c_1$,$c_2$,$n_0$，当$n>n0$的时候，$c_1g(n)≤f(n)≤c_2g(n)$，则$f(n)=\Theta (g(n))$。 他表示所有阶数与$g(n)$相同的函数集合。

例如： $f (n) = n^2 + n$，$g(n) = 100n^2$，那么有$f (n)=\Theta (g(n))$

$o$ / $\omega$

$f(n)=o(g(n))$当且仅当$f(n)=O(g(n))$且$f(n)≠\Omega (g(n))$。也就是说小o记号可以表示时间复杂度的上界，但是一定不等于下界。
$\Omega$则相反，$f(n)=\Omega (g(n))$当且仅当$f(n)=\Omega (g(n))$且$f(n)≠O(g(n))$。也就是说小$o$记号可以表示时间复杂度的下界，但是一定不等于上界。

几个渐进界的定理

定理1

设 $f,g$ 是定义域为自然数集合的函数.

1. 如果$\lim\limits_{n→+∞} \frac{f(n)}{g(n)}$ 存在，并且等于某个常数 $c>0$ ，那么$f(n)=Θ(g(n))$.
2. 如果$\lim\limits_{n→+∞} \frac{f(n)}{g(n)} =0$，那么$f(n)=o(g(n))$.
3. 如果$\lim\limits_{n→+∞} \frac{f(n)}{g(n)} =+∞$，那么$f(n)=\Omega (g(n))$.

定理2

函数的阶之间的关系具有传递性

设函数 $f,g,h$ 的定义域为自然数集合，

1. 如果 $f=O(g)$ 且 $g=O(h)$，那么 $f=O(h)$.
2. 如果 $f=\Omega (g)$ 且 $g=\Omega (h)$，那么 $f=\Omega (h)$.
3. 如果 $f=Θ(g)$ 且 $g=Θ(h)$，那么 $f=Θ(h)$.

定理3

假设函数 $f,g$ 的定义域为自然数集，若对某个其它函数 $h$, 有 $f=O(h)$ 和 $g=O(h)$，那么$f+g=O(h)$

小结

估计函数的阶的方法：

• 计算极限
• 阶具有传递性

几类重要的函数

对数函数$\log _ax$的阶 < 幂函数$x^a$的阶
多项式函数$f(x)=a_n·x^n+a_{n-1}·x^{(n-1)}+…+a_2·x^2+a_1·x+a_0$的阶 < 指数函数$a^x$的阶.

• 指数
• 多项式
• 对数

递推方程的求法

写出递推方程，如下（第N个基于n-i还是倍数个），g(n)是划分时间，然后让你给出通项公式。

第一类

$f(\boldsymbol{n})=\sum_{i=1}^{k} \boldsymbol{a}_{i} \boldsymbol{f}(\boldsymbol{n}-\boldsymbol{i})+\boldsymbol{g}(\boldsymbol{n})$

迭代法

直接

• 插入排序最坏情况下时间分析
  • 直接将其带入，一层层求解计可

换元

• 二分归并
  • 一个思路就是将倍数变成指数函数。譬如
    $\left\{\begin{array}{l} W(n)=2 W(n / 2)+n-1 \\ W(1)=0 \end{array}\right.$
    令$n=2^k$化为
    $W(2^k) = 2W(2^{k-1}) + 2^k - 1$
    $W(0) = 0$

差消

不考

尝试法

______________

第二类

$f(n)=a f\left(\frac{n}{b}\right)+d(n)$
迭代法
递归树
主定理

主定理

$T(n) = a T( \frac{n}{b}) + f(n)$

1. 若 $f(n)=O(n^{\log _b a-\varepsilon })$,$\varepsilon >0$，那么$T(n)=\Theta (n^{\log _b a})$
2. 若 $f(n)=\Theta (n^{\log _b a})$，那么$T(n)=\Theta (n^{\log _b a}\log n)$
3. 若 $f(n)=\Omega (n^{\log _b a+\varepsilon })$,$\varepsilon >0$，且对某个常数$c>1$，和所有充分大的$n$有$af(\frac {n}{b})\le cf(n)$那么$T(n)=\Theta (f(n))$

---

考到的问题

矩阵链相乘

DP

子问题

$A_{i \dots j}$ ：表示矩阵链$A_iA_{i+1}\dots A_j$ 的乘积结果，边界 i, j
输入向量：$< P_{i-1}, Pi, … , P_j >$
其最好划分的运算次数：$m[i, j]$

递推方程

书上P48

零钱

形式化问题

现有集合 $W=\{w_{1},w_{2},\dots,w_{n}\}, V=\{v_{1}, v_{2},\dots,v_{n}\}$ ，且满足 $v_{1} < v_{2} < \dots < v_{n}$ .对于给定的 $Y$ ，找出合适的 $X=\{x_{1},x_{2},\dots,x_{n}\}\space,x_{i}\in n$ ,满足 $Y=\sum_{i=1}^{n}v_{i}x_{i}$ ，求满足条件的 $X$ 中，同时满足 $min\{\sum_{i=1}^{n}w_{i}x_{i}\}$ 的集合结果.

DP

这属于整数规划问题，动态规划算法可以得到最优解。

解决DP问题，最重要的是要找出子问题。所以从这里开始。

此问题基于初始的硬币问题，下面给出题面

假设有 1 元，3 元，5 元的硬币若干（无限），现在需要凑出 11 元，问如何组合才能使硬币的数量最少？

初始的硬币问题相当于此问题中的特例，要解决题目中的问题，不妨先从这个特例开始：

特例

现在给定一个$W=\{1,1,1\}$ ， $V=\{1,5,10\}$ ， $Y=15$ ,求 $X$ 的 $min\{\sum_{i=1}^{n}w_{i}x_{i}\}$ （注意，这里求的是最小个数sum，而不是支付方式$X$）.

在这里我们将硬币看做等重量，即1，此处映射为对应面额硬币的个数。

我们给定一个二维数组F[k][y]，表示当前考虑 $1,2,\dots,k$ 的情况下，对于当前金额 $y$ 所需的最小重量（硬币数）。

我们从头开始，很显然，对于F[1][]，即只考虑 1 元硬币的情况，对于给定的当前 v 的最小值。

将 $v=0$ 置为0.接下来考虑要付 1 元钱的情况，这时只可能有 在原先0元的基础上付 1 元硬币。即 $F[1][1]=F[1][0]+w_{1}x_{1}$.

金额	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
F[1][]	0	1	2

以此类推，直到 $y=Y$.

金额	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
F[1][]	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15

接下来我们考虑 $k=2$ ，即有1元和5元硬币的情况。在 $y < 5$ 的情况下，不能用5元硬币，所以此时直接等于其上面的值。

直到 $n=5$ 可以看到此时可以拿一个5元的硬币了。我们直接从 F[2][0],F[1][5] 中查找最小值，然后加上5元的重量1.

金额	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
F[1][]	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
F[2][]	0	1	2	3	4	1

同样，对于10元，15元也是同样的处理方法。

金额	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
F[1][]	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
F[2][]	0	1	2	3	4	1	2	3	4	5	2	3	4	5	6	3

以此类推，填完表格

金额	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
F[1][]	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
F[2][]	0	1	2	3	4	1	2	3	4	5	2	3	4	5	6	3
F[3][]	0	1	2	3	4	1	2	3	4	5	1	2	3	4	5	2

状态转移方程

设 $F_{k}(y)$ 表示用前 $k$ 种零钱，总钱数为 $y$ 的最小重量。

$$\left\{ \begin{matrix}F_{k+1}(y)=\min \begin{Bmatrix}F_{k}(y) \\F_{k+1}(y-v_{k+1})+w_{k+1} \end{Bmatrix} \\F_{1}(0)=0 \end{matrix}\right.$$

$$k=1,2,\dots,n-1,y=0,1,\dots,Y$$

PPT上给出了另一种状态转移方程，但我倾向于用上方的二选一的方式表达。

下面是PPT给出的状态转移方程。

$$\left\{\begin{matrix}f_{k+1}(y)=\min_{0 \le x_{k+1} \le \left \lfloor \frac{y}{v_{k+1}} \right \rfloor }\{F_{k}(y-v_{k+1}x_{k+1})+w_{k+1}x_{k+1}\} \\f_{1}(y)=w_{1}\left \lfloor \frac{y}{v_{1}} \right \rfloor =w_{1}y \end{matrix}\right.$$

$$k=1,2,\dots,n-1,y=0,1,\dots,Y$$

复杂度

此算法常数级填写了一张二维表格。时间复杂度为

$$O(nY)$$

$n$ 为钱的种数，$Y$ 为需要给付的钱数。

若需要具体的$X$集合，只需同样[n][Y]大小的数组（或者一个[2][Y]的数组进行滚动），用来存取其选择的单元格，然后通过 $O(n+Y)$ 回溯计可获得 $X$ 的集合。

贪心

用贪心算法解决此问题，只需要保证每次选择都是当前最好的选择。

针对当前问题，为了能够得到最小的总重量我们就会优先选择单位重量下价值较高的硬币。直到不能再用，再选单位价值次之的。由于题干说明一定有价值为1的硬币，所以一定能保证付到Y价值。

复杂度

此算法需要将硬币按“单位价值比”排序，最快需要 $O(n \log n)$ 时间，此后选择只需要 $O(n)$ 时间。总的时间复杂度是

$$O(n \log n)$$

贪心局限 (看看就好)

我们不妨设这样一串硬币属性：

$$\frac{v_1}{w_1}\le\frac{v_2}{w_2}\le\dots\le\frac{v_n}{w_n}$$

使用前 $k$ 种零钱，总钱数为 $y$。

贪心法的总重为 $G_{k}(y)$，则有如下递推方程

$$\begin{array}{l} G_{k+1}(y)=w_{k+1}\left\lfloor\frac{y}{v_{k+1}}\right\rfloor+G_{k}\left(y \bmod v_{k+1}\right) \quad k1 \\ G_{1}(y)=w_{1}\left\lfloor\frac{y}{v_{1}}\right\rfloor=w_{1} y \end{array}$$

n=1, 2

$n = 1$ 只有一种零钱，$F_{1}(y) = G_{1}(y) , F_{2}(y) = G_{2}(y)$

$n = 2$, 使用价值大的钱越多($x_{2}$越大)，得到的解越好

$F_{2}(y)=\min _{0 \leq x_{2} \leq\left\lfloor y / v_{2}\right\rfloor}\left\{F_{1}\left(y-v_{2} x_{2}\right)+w_{2} x_{2}\right\}$

$$\begin{array}{l} {\left[F_{1}\left(y-v_{2} x_{2}\right)+w_{2} x_{2}\right]} -\left[F_{1}\left(y-v_{2}\left(x_{2}+\delta\right)\right)+w_{2}\left(x_{2}+\delta\right)\right] \\=\left[w_{1}\left(y-v_{2} x_{2}\right)+w_{2} x_{2}\right]-\left[w_{1}\left(y-v_{2} x_{2}-v_{2} \delta\right)+w_{2} x_{2}+w_{2} \delta\right] \\=w_{1} v_{2} \delta-w_{2} \delta=\delta\left(w_{1} v_{2}-w_{2}\right) \geq 0 \end{array}$$

说明$w_{1} ≥ \frac{w_{2}}{v}$，即多使用 $\delta$ 枚第二种硬币的重量更小。

背包问题 //

0-1背包变体

DP

简单来说，此问题基于“二维0/1背包”。在二维中，我们需要考虑背包的价值，背包的重量。“三维0/1背包”增加了“体积”这一维度。要弄清楚此问题，不妨先复习下DP方法解决二维0/1背包的思路。

二维，不考虑体积

我们从头开始，假设现在背包中放入的物品的价值最优，在考虑下一个物品时，则只需要考虑「放入」与「不放入」。
我们用 f[i, j] 表示在前 i 件物品（即物品编号为1-n）中选择若干件放在所剩空间为 j 的背包里所能获得的最大价值，于是就有以下状态转移方程：$$f[i, j] =\left{\begin{matrix}max\left { {f[i-1, j-w[i]]+v[i] , f[i-1, j]}\right } {(j \ge W{i})}\f[i-1, j]{(0 \le j \le W{i})}\end{matrix}\right.$$.

三维

和二维相同，在考虑下一个物品时，则只需要考虑「放入」与「不放入」。
我们用 f[i, j,k] 表示在前 i 件物品（即物品编号为1-n）中选择若干件放在所剩空间为 j ，所剩载重为 k 的背包里所能获得的最大价值，于是就有以下状态转移方程：$$f[i, j, k] =\left{\begin{matrix}max\left {f[i-1, j-w[i], k-b[i]]+v[i], f[i-1, j, k]\right }{(j >= w[i], k >= b[i])}\ f[i-1, j ,k]{(0 \le j \le W_{i} || 0 \le j \le W_{i})}\end{matrix}\right.$$

只在二维基础增加一维，其余完全不变。

实现形式

根据上面的公式，初始化表格（$f[1,w[0],b[0]]=v[0]$，$i=0$ 与 $j=0$ 与$k=0$情况置$0$）。并将$i,j,k$嵌套循环。

此时这个三维表格即可填满，$f[n,c,d]$即为最大价值。（所有物品n，包最大重c，最大容量d）

然后自顶向下，找出$f[i-1, j-w[i], k-b[i]]+v[i]$ 与 $f[i-1, j, k]$ 中更大的值，若是前者，则证明当前第 i 件物品已装入；若是后者则未装入。

复杂度

该算法需要填一张三维表格，需要 $O(ncd)$ 时间，回溯表格需要 $O(n)$时间。总共为 $O(n+ncd) = O(ncd)$时间复杂度。

回溯-普通

思路

在我看来，回溯法有另一个名字：及时止损的遍历法。
对于此问题，0-1 背包。每种物品只有选与不选的选项。由此构造一棵 $n$ 层二叉树，左为1，右为0，分别代表选与不选。

具体些

我们搜索一棵树，从左子树开始（意味着选择此物品），直到不能够继续装下，丢弃该节点的左子树后，向右搜索，直到叶子结点。然后比较当前的值与最大值，如果符合最优条件，那么记录此最优解，然后回溯。如果不符合，那么也回溯。

如何回溯

函数回溯法。
根据函数递归的性质，在选择一颗子树时，通过“函数调用自身”来进行下层搜索，直到叶子结点，函数将在统计当前路径的价值，比较最大值后自动回溯。

装载问题

回溯

n 个集装箱装上 2 艘载重分别为 c1 和 c2 的轮船
P125

最优装载 //

贪心

n 个集装箱 1, 2, …, n 装上轮船，集装箱 i 的重量 wi , 轮船装载重量限制为 C， 无体积限制.

即重量约束时，个数最多。
其实就是重量（这个问题里重量和价值调换了）都为1的硬币问题的另一个极端，即价值约束时，重量最少。
但要注意，这里每种只有一个，所以选完就不能再选了

变体

如果对体积进行约束呢？
其实也很简单，就是现在的实验的硬币问题。即硬币的重量不一，

最优调度

贪心

LCS

DP

子问题

我们假设当前$Z=<Z_{1}, Z_{2},…, Z_{k}>$已经是LCS，可能有$x_{m} = y_{n}$和$x_{m} \ne y_{n}$：

如果xm = yn

1. 则$zk = xm = yn$ 且 Zk-1是Xm-1和Yn-1的一个LCS.

如果xm != yn

1. 且有 $zk \ne xm$，则Z是Xm-1和Y的一个LCS.
2. 且有$zk != yn$，则Z是X和Yn-1的一个LCS.

状态转移方程

$$L[i][j] = \begin{cases} 0 & i = 0 \space or \space j = 0 \\\max\{L[i-1][j],L[i][j-1]\} & x_i\ne y_j,i>0,j>0 \\ L[i-1][j-1]+1 & x_i = y_j,i>0,j>0 \end{cases}$$

因此，我们只需要从c[0][0]开始填表，填到c[m][n]，所得到的c[m-1][n-1]就是LCS_length.

回溯

若想得到LCS，回溯一次b数组，从最后一个位置开始往前遍历：

1. 如果箭头是↖，则代表这个字符是LCS的一员，存下来后 i-- , j--
2. 如果箭头是←，则代表这个字符不是LCS的一员，j--
3. 如果箭头是↑，也代表这个字符不是LCS的一员，i--
4. 如此直到$i = 0$或者$j = 0$时停止，最后存下来的字符就是所有的LCS字符

序列	1	2	3	4	5	6	7
X	A	B	C	B	D	A	B
Y	B	D	C	A	B	A	\0
Target	B	C	B	A

复杂度

该算法无重复地填写了一张(如果需要具体的子序列内容，则是两张)二维表格，每个格子填写时都仅进行了常数次比较。时间复杂度 $O(mn)$.

回溯时，在任何情况下，都需要从[m][n]回溯到[1][1]，即回溯时间复杂度为$O(m+n)$.

所以DP算法的时间复杂度为$O(mn)$.

二分搜索

分治

二分排序

分治

思路

极简分析法：

     T(n)            拆分 n/2, 归并 n/2 ，一共是n/2 + n/2 = n

     /    \            以下依此类推：

  T(n/2) T(n/2)      一共是 n/2*2 = n

 /    \ /     \

T(n/4)    ...........   一共是 n/4*4 = n

一共有$\log n$层，故复杂度是 $O(n\log n)$

看书上P22

指定和

回溯

给定n个正整数$w_i(1<=i<=n)$和M。要求从集合$(w_1,w_2,\dots ,w_n)$中找出所有可能的子集，使得每一个子集中各元素的累加和等于M。
例如：令$(w_1,w_2,w_3,w_4)=(11,13,24,7)$和$M=31$。求该问题的解空间树。

一些补充

作业一

1

1. 假设某算法在输入规模为n时的计算时间为$T(n)=3*2^n$。在某台计算机上实现并完成该算法的时间为t秒。现有另一台计算机，其运行速度为第一台的$64$倍，那么在这台新机器上用统一算法在t秒内能解输入规模为多大的问题？
2. 若上述算法的计算时间改进为$T(n)=n^2$，其余条件不变，则在新机器上用t秒时间能解输入规模为多大的问题？
3. 若上述算法的计算时间进一步改进为$T(n)=8$，其余条件不变，则在新机器上用t秒时间能解输入规模为多大的问题？

解答：

1. 原计算机A，高校计算机B
   对A，有$T_A(n)=3 \times 2^n = t$
   对B，有$\frac {t}{64}=\frac {3 \times 2^n}{64}=T_B(n)$
   $t=T_B(n')=T_A(n)= \times 2^n=\frac {3 \times 2^{n'}}{64}$
   $\therefore n'=n+6$
   $\therefore$在t时间内，新机器能解决(n+6)规模的问题。
2. 同上$T_A(n)=n^2=t$
   $T_B(n)=\frac{n^2}{64}$
   $t=T_B(n')=T_A(n)=\frac{n^2}{64}=n^2$
   $\therefore n'=8n$
   $\therefore$在t时间内，新机器能解决(8n)规模的问题。
3. 由于算法计算时间为定值，所以无论规模多大多小，对于A机器，其总能在t时刻完成，对于B，总在$\frac{t}{64}$时刻完成。
   因此B能在t秒时间内解决任意规模的问题。

2

函数的渐进表达式。注意：需要给出具体的解题过程。
（1）$3n^2+10n$
（2）$\frac {n^2}{10} +2n$
（3）$21 + \frac {1}{n}$
（4）$\log n^3$
（5）$10\log 3^n$

实验一

统计数字

以基础值和修正值两部分计算，首先看基础值考虑 $1\to 10^i$ 的情况，修正值即 $10^i+1\to n$ 的情况，先看基础值：
(1)首先从个位开始审视：对于1-10这十个数之个位，可以发现分别出现了1-9、0. 即任意地目标X都出现了1次。
(2)以此审视1-100的十位，同理任意的X都出现了10次，如10-19中，十位为“1”的情况有10种。
(3)以此类推，归纳推理。审视 $1\to 10^i$ 的第二位（即右起第i位），其任意X都出现了 $10^{i-1}$ 次。
综上，基础值为高位的所有数字乘以当前位权，即 {高位全部数字}* $10^{i-1}$例如计算525的十位，对于十位任意的X都出现了 {5}* $10^{2-1}$次。不难看出，基础值就是当前位上任意X都出现的同样的次数。

接着考虑修正值，将问题简化，如525的修正值只考虑从501-525的情况。
(4)对于1-525，在计算十位时，若X=1 （2>X），则501-525里包含了全部的十位为1的情况，即510-519，所以需加上次。
(5)若X=2，则需要看低位的所有数字，十位为2的情况将继续重复5+1次，即520、521、522、523、524、525.
(6)若X=3（2 < X）,十位为3的情况不存在。

总结以上算法，可以看到，当计算右数第 i 位包含的 X 的个数时：
(1)取右起第 i 位左边（高位）的全部数字，乘以，得到基础值 a = {高位全部数字}* $10^{i-1}$ .
(2)取右起第 i 位数字，计算修正值和最终结果：
(3)如果大于 X，则结果为 $a+10^{i-1}$.
(4)如果小于 X，则结果为 a.
(5)如果等于 X，则取第 i 位右边（低位）数字，设为 b，最后结果为 $a+b+1$.
这里的 $X \in \{1,2,\dots ,9\}$ .由于0不会出现在最高位，所以需要另外计算：
(1)从个位开始，计算右起第i位就要结束，需要将for循环的判断条件改为 k / 10 != 0. （k为高位的全部数字）。
(2)其次，右起第 i 位的基础值 a 要变成 {高位全部数字}*$10^{i-1}-1$ ，如上述④、⑤，我们在考虑修正值时会将低位为0的情况考虑近来。但若X=0，则会多计算一次修正值（例如525，修正值范围应为501-525，不会包含500）。需要在计算时主动减去。