算法设计与分析 | BarryZed的个人博客

By BarryZed

算法概述

性质：

有穷性：一个算法必须总是在执行有穷步骤之后结束，且每一步都在有穷时间内完成。

确定性：算法中每一条指令必须有确切的含义。不存在二义性。即对于相同的输入只能得出相同的输出。

可行性：一个算法是可行的。即算法描述的操作都是可以通过已经实现基本运算，执行有限次来实现的

输入：一个算法有零个或多个输入，这些输入取自于某个特定的对象集合。

输出：一个算法有一个或多个输出，这些输出同输入之间有着某些特定的关系。

复杂度分析

渐进分析：只要最高次项，忽略系数与其他项

渐进上界里c是常数，只要够大就行，满足条件再大也可以

迭代法示例

第1步：写出原始式
T(n) = T(n-1) + c （c 是常数）
第2步：开始迭代展开（写几层看模式）
T(n) = T(n-1) + c
= [T(n-2) + c] + c = T(n-2) + 2c
= [T(n-3) + c] + 2c = T(n-3) + 3c
= [T(n-4) + c] + 3c = T(n-4) + 4c
……
第3步：写出通用形式（第 i 层）
T(n) = T(n - i) + i·c
第4步：确定展开到什么时候（找 k）
我们一直展开到子问题规模变成基例，即 n - i ≤ 1
→ i = n - 1 （当 i = n-1 时，n - (n-1) = 1）
第5步：代入 k 并化简（重点）
把 i = n-1 代入通用形式：
T(n) = T(n - (n-1)) + (n-1)·c
= T(1) + (n-1)·c
因为 T(1) = Θ(1)，(n-1)·c 是线性项，
所以：
T(n) = Θ(1) + Θ(n-1) = Θ(n)
——Grok

Master Theory

递归与分治策略

分治法的要求：

子问题与原问题性质完全相同

子问题之间相互独立，可分别求解

最小子问题可以直接求解

自顶向下，大问题拆分成小问题

n位大整数乘法

动态规划

自底向上，由子问题答案推导出大问题答案

备忘录法：自顶向下，递归 + 记忆缓存

矩阵连乘问题

变量名

m[i][j] ：到连乘的最少乘法次数

p[i] ：存的是维数，的维数是p[i] x p[i+1]

s[i][j]：i,j之间最佳断点

s[][]存放的是i,j之间最佳断点，就是上面转移方程中m[i][j] 取到时k 的值，加括号：

s[1][1] （i==k 没有意义直接跳过）

s[1][2] = 1 ：1，2之间在1后加括号（即1自己加括号括起自己没有意义）

…

s[1][4] = 3 ：1，4之间在3后加括号（即1、2、3括起来，4、5、6括起来）

s[1][5] = 3 ：1，5之间在3后加括号（即不变）

…

s[2][4] = 3 ：2，4之间在3后加括号（即2、3括起来，4单独不用管）

…

s[4][6] = 5 ：4，6之间在5后加括号（即4、5括起来，6单独不用管）

最后答案为(1 (2 3)) ((4 5) 6)

最长公共子序列（LCS, Longest Common Subsequence）问题

变量名

X, Y ：原序列

Z ：LCS

c[i][j] ：序列和的最长公共子序列的长度

LU, L, U : Left-up, Left, Up

rec[i][j] ：记录子问题最优解的来源内容LU/L/U

如果c[i][j] 取了c[i-1][j] 说明行号更小，往上走了，所以rec[i][j] = U ，另一个取L 同样道理

c[i-1][j] 与c[i][j-1] 相等时，优先取U

通过rec 写出LCS：从右下角开始：LU就取字符并斜走，U向上，L向左，最后逆序输出

最大子段和（Maximum Subarray Sum）问题

变量名

：以开头的最大子序列

rec[i]：以为起点的最优连续子数组的结束位置

rec[3]=6：为

当，则有,反之，当，则有

由于要知道的值，所以要从后开始算

例子：（本表格白字部分是填的，从后往前，每一列先再rec）

ㅤ	i	1	2	3	4	5	6	7	8	9	10	11	12
X	ㅤ	1	-2	4	5	-2	8	3	-2	6	3	7	-1
D	ㅤ	31	30	32	28	23	25	17	14	16	10	7	-1
rec	ㅤ	11	11	11	11	11	11	11	11	11	11	11	12

得出最大子段和为，rec[3] = 11 ，所以是~

0-1背包问题

变量

v[i] ：第i 件物品的价值

w[i] ：第i 件物品的重量

x[i] ：0为不拿，1为拿

m[i][j]=前i件物品，在容量j下的最大价值

如果 m[i][j] == m[i-1][j]⇒ 没选第 i 个
如果 m[i][j] > m[i-1][j]⇒ 选了第i 个
——ChatGPT

例子

i(w/v) \ j	1	2	3	4	5	6	7	8	9	10
0	0	0	0	0	0	0	0	0	0	0
1(2/6)	0	6	6	6	6	6	6	6	6	6
2(2/3)	0	6	6	9	9	9	9	9	9	9
3(6/5)	0	6	6	9	9	9	9	11	11	14
4(5/4)	0	6	6	9	9	9	10	11	13	14
5(4/6)	0	6	6	9	9	12	12	15	15	15

从m[n][W]倒推

从m[5][10] = 15 开始

🔹 第一步：i=5（物品 e），j=10

对比：

m[5][10] = 15

m[4][10] = 14

👉 不一样 ⇒ 选了 e

背包容量减少：

👉 j = 10 - 4 = 6

🔹 第二步：i=4（物品 d），j=6

对比：

m[4][6] = 9

m[3][6] = 9

👉 一样 ⇒ 没选 d

👉 j 不变 = 6

🔹 第三步：i=3（物品 c），j=6

对比：

m[3][6] = 9

m[2][6] = 9

👉 一样 ⇒ 没选 c

👉 j 不变 = 6

🔹 第四步：i=2（物品 b），j=6

对比：

m[2][6] = 9

m[1][6] = 6

👉 不一样 ⇒ 选了 b

👉 j = 6 - 2 = 4

🔹 第五步：i=1（物品 a），j=4

对比：

m[1][4] = 6

m[0][4] = 0

👉 不一样 ⇒ 选了 a

👉 j = 4 - 2 = 2（结束其实已经够了）

选了abe

贪心算法

贪心算法的概述

贪心算法产生整体最优解的条件

贪心选择性：

若一个优化问题的全局最优解可以通过局部最优选择得到，则该问题具有贪心选择性。

一个问题是否具有贪心选择性需要证明。

最优子结构：

若一个优化问题的优化解包含它的子问题的优化解，则称其具有最优子结构。

（一个问题的最优答案，可以由它的子问题的最优答案拼出来）

适用贪心算法的前提：

局部最优解能推导产生全局最优解。

实际上，适用贪心算法的情况较少。对一个问题分析是否适用于贪心算法，一般地可以先选择该问题下的几个实际数据进行分析，就可做出判断。

找零问题用贪心不一定能得到最优解

面额：1、3、4 找：6

贪心：4、1、1

最优：3、3

贪心算法的基本要素

动态规划算法通常以自底向上的方式解各子问题，而贪心算法则通常以自顶向下的方式进行，以迭代的方式相继作出贪心选择，每次贪心选择后将所求问题简化为规模更小的子问题。

背包问题

开贪！：选择性价比（）最高的装，到最后装不进去时用剩下性价比最高的物品塞满。

活动安排问题

策略：结束早的优先

理由：尽量把时间空出来给后面更多选择

最优装载问题

载重一定，在无限体积的限制下尽可能装更多的货物

策略：从轻的开始装，直到装不下

哈夫曼编码

统计频率

一直合并最小的，直到得到哈夫曼树

字符	频率
A	5
B	9
C	12
D	13
E	16
F	45

把每个字符当成一棵“只有一个节点的树”：

找最小的两个合并

最小两个：A(5), B(9)

→ 合并成新节点 AB(14)

C(12), D(13)

→ CD(25)

AB(14), E(16)

→ ABE(30)

CD(25), ABE(30)

→ CDABE(55)

F(45), CDABE(55)

→ Root(100)

每次合并都会产生一个父节点：

字符	编码
F	0
C	100
D	101
A	1100
B	1101
E	111

——ChatGPT

按照哈夫曼树得到变长码（前缀码（左0右1（具体 0/1 左右可交换，但结果等价）））

多机调度问题

策略：用时最长的优先

从用时最长的开始，按顺序将任务派发给当前负载最低（作业时间和最小）的机器

回溯法

子集树

从全集中选出几个元素作为答案（0-1背包问题等）

排列树

已经确定元素，要求出顺序（旅行商问题等）

具体步骤

做选择（Choose）

从当前状态选一个可能的选项

递归深入（Explore）

继续往下走，看这条路能不能走到终点

撤销选择（Unchoose & Backtrack）

如果走不通，恢复现场，换下一条路

约束函数

判断选择是否合理。（说白了就是最基本的要求，比如：背包问题中选择后是否超重、N皇后问题中该皇后会不会被攻击等）

限界函数

用当前状态，以最乐观的情景，估计能否得到答案；如果不能，则直接剪枝。

通常紧跟在做选择完毕并更新完状态之后，判断该状态是否值得继续扩展。

小性质（习题摘选）

回溯法效率较低的主要原因是需要枚举大量候选解

回溯法的时间复杂度通常为指数级

分支界限法

队列式

哪个节点先被选入候选队列，哪个就先扩展（FIFO）

优先队列式

候选队列中“最有希望的”节点先被扩展

最有希望：代价最小或上限最高

小性质（习题摘选）

优先队列分支限界法中通常使用的数据结构是堆

队列式分支限界法对应的搜索策略是广度优先搜索

随机化算法

线性同余法（Linear Congruential Method, LCM）

：第 n 个随机数

：乘子（multiplier）

：增量（increment）

：模数（modulus）

：种子（seed，起点）

舍伍德算法（Sherwood）

不会算错，通过随机化避免极端输入

拉斯维加斯（LasVegas）

不会算错，一直尝试到正确答案为止

蒙特卡罗（MonteCarlo）

可能算错，时间越长，正确的可能性越高

若算错的概率为，则独立运行算法次，全部失败的概率为

算法只给出一个结果

没有办法立刻验证它是不是正确

或者验证成本和求解成本差不多高

小性质（习题摘选）

随机化算法的性能通常用平均时间复杂度（期望时间）来衡量

随机化算法中期望时间复杂度的含义是对随机过程取平均后的运行时间

网络流算法

可行流

每条边的流量≤该边最大流量

（流量守恒）除了源点和汇点，中间结点的入流量等于出流量

零流

所有边的流量均为0

对任意流量网络，零流都是可行流

最大流

整个网络中，从源点到汇点的所有“流量分配方式”的总和最大值，是“全网同时运作的总运输能力”

⚠️不是某一条链！

增广链算法

链

从源点到汇点，无环的一条简单路径

前向边：顺着路径方向的边

后向边：逆着路径方向的边

增广链

所有前向边都非饱和，所有后向边流量均大于零

是构成最大流的一条链，为最大流贡献一部分流量

是为了找到一个链，并在增加一点流量

可行流是最大流 ⇔ 网络中不存在从s到t的增广链 ⇔ 残存网络里没有一条s→t的路径

残存网络

残存网络是由原网络中各边的剩余容量（正向）和已用流量（反向）构成的有向网络，用于描述当前流量状态下还能进行的流量调整可能性。 ——ChatGPT

增广链算法

不断在“残量网络”里找一条从 s 到 t 的可行路径，然后沿这条路增加流量，直到找不到为止。

割集

切一刀，使源点和汇点在两个集合里。

两个集合包含所有点，没有重复点

源点S在的是S集

汇点T在的是T集

割集：所有从S→T且被切断的边的集合

割容量：割集中所有边的容量之和（不是流量）

流值定理

最大流 ≤ 任意割的容量（弱对偶性）

最大流 = 最小割容量（强对偶性）

最小费用流问题

方法1

首先找到网络的最大流f，然后不断减小f使网络费用逐步减小，最终获得最小费用流。

方法2

首先找到费用最小的可行流f，然后不断增大f并保持费用最小，最终获得最小费用流。

用零流构建残存网络

找从源点到汇点的费用最小路径

取最小费用可增广链的最小容量作为增流值

迭代2-3直到没有增广链

Floyd-Warshall算法

本质是动态规划

dist[i][j] =min(dist[i][j], dist[i][k] + dist[k][j])

可松弛边

能通过“绕路”使得距离更短的边

ㅤ	i	1	2	3	4	5	6	7	8	9	10	11	12
X	ㅤ	1	-2	4	5	-2	8	3	-2	6	3	7	-1
D	ㅤ	31	30	32	28	23	25	17	14	16	10	7	-1
rec	ㅤ	11	11	11	11	11	11	11	11	11	11	11	12

ㅤ	i	1	2	3	4	5	6	7	8	9	10	11	12
X	ㅤ	1	-2	4	5	-2	8	3	-2	6	3	7	-1
D	ㅤ	31	30	32	28	23	25	17	14	16	10	7	-1
rec	ㅤ	11	11	11	11	11	11	11	11	11	11	11	12

ㅤ	i	1	2	3	4	5	6	7	8	9	10	11	12
X	ㅤ	1	-2	4	5	-2	8	3	-2	6	3	7	-1
D	ㅤ	31	30	32	28	23	25	17	14	16	10	7	-1
rec	ㅤ	11	11	11	11	11	11	11	11	11	11	11	12