Algorithm Design

Algorithm DesignChapter 0. DefinitionsChapter 1. Algorithms of Numbers1.1 数字基本算数1.1.1 加法1.1.2 乘法 & 除法1.2 模运算1.2.1 $\mathbf{Z}_N$ 上的加法、乘法1.2.2 $\mathbf{Z}_N$ 上的幂1.2.3 Euclid's Greatest Common Divisor1.2.4 Euclid GCD 算法的延伸1.2.5 $\mathbf{Z}_N$ 上的乘法逆元1.3 素性测试1.3.1 Definitions1.3.2 随机生成素数1.4 密码学1.4.1 对称加密1.4.2 非对称加密1.4.3 证书Chapter 2. 分治算法2.1 更快的乘法2.2 更一般的分治递推分析2.3 应用：比较排序的时间下界2.4 应用：中位数算法再讨论2.5 应用：矩阵乘法2.6 应用：计数逆序Chapter 3. The Algorithms using Fast Fourier Transform3.1 Revisit Complex Number3.2 Begin with The Production of PolynomialsChapter 4. Graph4.1 Revisit: DFS in Graph4.2 无向图的连通分量4.3 有向图的连通分量4.4 有向无环图（DAG）4.5 Revisit: 有向图强连通分量4.6 BFS in Graph4.7 正权图中两点间的单源最短路径4.8 含负权无负环图中两点间的单源最短路径补充：负环问题 & 最简最短路4.9 含负权的 DAGs 中两点间的单源最短路径Chapter 5. Greedy Algorithms5.1 Minimal Spanning Tree (MST)5.2 Set Cover（集合覆盖问题）5.3 贪婪算法何时失效：Coins ChargingChapter 6. 动态规划6.1 最长子序列问题 I：最长递增子序列6.2 编辑距离6.3 背包问题6.3.1 01-背包问题6.3.2 完全背包问题6.3.3 多重背包问题6.3.4 问题变种：Optimal Solution for Coins Charging6.4 最长子序列问题 II6.4.1 最长公共子序列6.4.2 最长公共子串6.4.3 Quiz: 最大连续子序列和6.5 3-Partition Problem6.6 跳石子6.7 Shortest Reliable Path (Lite) & Revisit Bellman-Ford Algorithm6.8 Revisit Shortest Paths Problem: Floyd-Warshall Algorithm6.9 Traveling Salesman Problem (TSP)6.10 Independent Sets in TreesChapter 7. Linear Programming7.1 Definitions7.3 Integer Linear Programming7.4 Dual Program7.4 Application: Shortest Path7.5 Simplex Algorithm7.5.1 算法内容7.5.2 Corner Cases7.5.3 运行时间7.6 最大流与最小割Chapter 8. NP Problems如何应对 NP 问题？梯度下降Hopfield Netural Network

Chapter 0. Definitions

介绍算法的时间复杂度（应该在数据结构中有所接触）：

$O$ Notation（上界）
- $f(n) \text{ is } O(g(n))\iff\exists c\gt0,n_0\gt0.\space s.t.\space\forall n\gt n_0,\space0\le f(n)\le cg(n)$ ；
- $f=O(f)$ ；
- $f=O(g),\space c\gt0\Longrightarrow cf=O(g)$ ；
- $f_1=O(g_1),\space f_2=O(g_2)\Longrightarrow f_1,f_2=O(g_1g_2)$ ；
- $f_1=O(g_1),\space f_2=O(g_2)\Longrightarrow f_1+f_2=O(\max\{g_1,g_2\})$ ；
- $f=O(g),\space g=O(h)\Longrightarrow f=O(h)$ ；
$\Omega$ Notation（下界）
- $f(n) \text{ is } \Omega(g(n))\iff\exists c\gt0,n_0\gt0.\space s.t.\space\forall n\gt n_0,\space 0\le cg(n)\le f(n)$ ；
  恰好与大 O 表示法相反；
$\Theta$ Notation（tight bound）
- $f(n) \text{ is } \Theta(g(n))\iff\exists c_1\gt0,c_2\gt0,n_0\gt0.\space s.t.\space\forall n\gt n_0,\space 0\le c_1g(n)\le f(n)\le c_2g(n)$ ；
- 关联 $f(n)=\Theta(g(n))\iff f(n)=O(g(n))\text{ and }f(n)=\Omega(g(n))$ ；
- 特殊性质：
  $\exists c \in (0, + \infty), s . t . lim_{n \to \infty} \frac{f (n)}{g (n)} = c ⟹ f (n) = Θ (g (n))$
  $f(n)=O(g(n))$ $+\infty$ $f(n)=\Omega(g(n))$ ；
  证明：
  $\begin{aligned} Prerequisites \exists c \in (0, + \infty), s . t . lim_{n \to \infty} \frac{f (n)}{g (n)} = c \\ ⟹ & \forall ε > 0, \exists n_{0} > 0, s . t . \forall n > n_{0}, c - ε \leq \frac{f (n)}{g (n)} \leq c + ε \\ ⟹ & \exists n_{0} > 0, s . t . \forall n > n_{0}, \frac{1}{2} c \leq \frac{f (n)}{g (n)} \leq \frac{3}{2} c, (ε = \frac{1}{2} c > 0) \\ ⟹ & \exists c_{1} = \frac{1}{2} c > 0, c_{2} = \frac{3}{2} c > 0, n_{0} > 0, s . t . \forall n > n_{0}, c_{1} g (n) \leq f (n) \leq c_{2} g (n) \\ ⟹ & f (n) = Θ (g (n)) \end{aligned}$
  错误证法：

\begin{aligned} Prerequisites f (n) = Θ (g (n)) \\ ⟹ & \exists c_{1} > 0, c_{2} > 0, n_{0} > 0. s . t . \forall n > n_{0}, 0 \leq c_{1} g (n) \leq f (n) \leq c_{2} g (n) \\ ⟹ & \forall n \in (n_{0}, + \infty), n_{0} > 0, 0 \leq f (n) - c_{1} g (n) \leq (c_{2} - c_{1}) g (n) \\ ⟹ & \forall n \in (n_{0}, + \infty), n_{0} > 0, \exists M > 0, | \frac{f (n)}{g (n)} - c_{1} | \leq M \\ ⟹̸ & \exists c > 0, lim_{n \to + \infty} \frac{f (n)}{g (n)} = c \end{aligned}

$O$ Notation with multiple variables
- $f(m,n)\text{ is }O(g(m,n))\iff\exists c\gt0,\space m_0\gt0,\space n_0\gt0,\space s.t.\space\forall m\gt m_0,\space n\gt n_0,\space f(m,n)\le cg(m,n)$ ；
Examples：
- $f(n)=32n^2+17n+1$ ：
  - $f(n)\text{ is both }O(n^2)\text{ and }O(n^3)$ ；
  - $f(n)\text{ is both }\Omega(n)\text{ and }\Omega(n^2)$ ；
  - $f(n)\text{ is }\Theta(n^2)$ ；
- $f(n)=32mn^2+17mn+32n^3$ ：
  - $f(n)\text{ is neither }O(n^3)\text{ nor }O(mn^2)$ ；
  - $f(n)\text{ is both }O(mn^2+n^3)\text{ and }O(mn^3)$ ；

Chapter 1. Algorithms of Numbers

看两个问题：

$N$ ，将它表示成素因子的乘积形式；
$N$ ，判定其是否为素数；

事实上，第一个问题相当复杂，第二个问题却相当简单。

$b$ $k$ $b^k-1$ $b$ $N$ $\lceil\log_b(N+1)\rceil$ 位数；

$O$ $b\gt1$ $N$ $O(\log N)$ ；

1.1 数字基本算数

1.1.1 加法

引理：任意 3 个单数位数字之和（不论进制），结果最多只有 2 个数位长。

由引理，我们讨论加法运算的时间复杂度：

$x,y$ $n$ $c_0+c_1n$ $O(n)$ $n$ 次，因此是 optimal 的）；

1.1.2 乘法 & 除法

对于乘法一般性的讨论：

$x,y$ $n$ $n$ $2n$ $O(n)\times(n-1)\rightarrow O(n^2)$ ；

$a\cdot b$ $a$ $b$ $a$ $a$ $b$ $a\cdot b$ 的值；

使用另一种算法：

\begin{matrix} x \cdot y = {\begin{aligned} 2 (x \cdot ⌊ \frac{y}{2} ⌋), & y is even, \\ x + 2 (x \cdot ⌊ \frac{y}{2} ⌋), & y is odd \end{aligned} \end{matrix}

$n$ $\log y$ $n$ $y$ $O(n^2)$ ；

考虑除法？

1.2 模运算

本节需要线性代数、抽象代数相关知识。

x \equiv y \mod N ⟺ N divides (x - y)

几种理解方式：
$x - y$ $N$ 整除；
$x$ $N$ $y$ $x$ $N$ $y$ ；
$x$ $y$ $N$ 同余（一个等价类）；

$0\sim N-1$ $N$ 个对象作为这个代数系统的元素，因为有定义：

$G$ $\cdot$ 及集合自身构成的代数系统，满足：

$\forall a,b \in G,\space a\cdot b\in G$ ；
$\forall a,b,c \in G,\space(a\cdot b)\cdot c=a\cdot (b\cdot c)$ ；
$\exists e\in G,\space s.t.\space\forall a \in G,\space e\cdot a = a\cdot e = a$ ；
$\forall a \in G ，\exists b\in G,\space s.t.\space a \cdot b = b \cdot a = e$ ；

这个代数系统就被称为 “群”（Group）。

$G=\{0,1,\ldots,N-1\}$ $\cdot$ 为 mod 时，这个系统符合上述定义，并且具备一些良好性质，数学上一般还称之为：

最小非负完全剩余系（Minimal Non-negative Complete Residue System） $\mathbf{Z}_N$ ；

$\mathbf{Z}_N$ 中的基本四则运算、幂运算、GCD 运算，充分讨论其算法和性质，为后面的计算机算法研究提供理论基础。

我们先在整数集上观察模运算的性质：

$x\equiv x^\prime\mod N,\space y\equiv y^\prime\mod N\Longrightarrow x+y\equiv x^\prime+y^\prime\mod N,\space xy\equiv x^{\prime}y^\prime\mod N$ ；
替换准则理解为，两个数相加、相乘，其最终的余数也相加、相乘；
$x+(y+z)\equiv(x+y)+z\mod N$ ；
$xy\equiv yx\mod N$ ；
$x(y+z)\equiv xy+xz\mod N$ ；
结合、交换、分配律理解为，加法结合、乘法交换、分配不会影响同余性（仍然位于一个等价类，属于一种等价变换）；

上面的性质说明：在一系列基本算数运算过程中，模运算可以在任意阶段进行：

2^{345} \equiv (2^{5})^{69} \equiv 32^{69} \equiv 1^{69} \mod 31

也就是说在整数集上：

$x\mod N + y\mod N=(x+y)\mod N$ ；
$x\mod N\cdot y\mod N=(xy)\mod N$ ；
$x^y\mod N=(x\mod N)^y$ ；

不讨论除法，而是讨论乘法逆元！

$\mathbf{Z}_N$ 上的加法运算、乘法运算、乘法逆运算、负运算（可以由加法运算表示）、幂运算（可以由乘法运算表示）：

$x+y\mod N$ ；
$x\cdot y\mod N$ ；
$x^{-1}\mod N$ ；
$N-x\mod N$ ；
$x^y\mod N$ ；

其中注意乘法逆运算的定义：

\exists a \in Z_{N}, s . t . a x \equiv 1 \mod N ⟺ x^{- 1} \equiv a \mod N

$\mathbf{Z}_N$ $x$ $a$ $a$ $x$ 的乘法逆元，注意没有说明乘法逆元和元素是一一对应的，也就是说可能存在一个元素没有乘法逆元。我们后面具体讨论这个问题。

$\mathbf{Z}_N$ $ax\mod N=1$ $ax\equiv1\mod N$ ；

$\mathbf{Z}_N$ 上的加法、乘法

$x+y\mod N$ $[0,N-1]$ $2(N-1)$ 。

$O(n)$ $n$ $N$ 的位数；

$x\cdot y\mod N$ $(N-1)^2$ $2n$ $2n$ $O(n^2)$ ；

模的除法会涉及 0 的情况，比较复杂，后面推导；

$\mathbf{Z}_N$ 上的幂

$x^y\mod N=(x\mod N)^y$ $x\mod N$ 进行运算，可以减小运算位数：

$x\mod N$ $x^2\mod N=(x\mod N)^2\lt N$ $x^3\mod N=x^2\mod N\cdot x\mod N\lt N$ $N$ $y$ 次；

$x^y\mod N$ $y\approx2^n+1$ $N$ $n$ $y$ 的位数。

这是指数时间复杂度的算法，不能这么解决问题。

我们想到可以每次计算之后不止乘一次，而是平方一次，这样能大大加快计算速度：

$x\mod N$ $x^2\mod N=(x\mod N)^2\lt N$ $x^4\mod N=(x^2\mod N)^2\lt N$ $x^{2\lfloor\log y\rfloor}\mod N$ $O(n^2)$ $\log N$ $O(n^3)$ ；

这样可以列出公式：

\begin{matrix} x^{y} = {\begin{aligned} (x^{⌊ \frac{y}{2} ⌋})^{2}, & y is even, \\ x \cdot (x^{⌊ \frac{y}{2} ⌋})^{2}, & y is odd \end{aligned} \end{matrix}

1.2.3 Euclid's Greatest Common Divisor

$\gcd(x,y)$ $x,y$ 的最大公因数；

$\gcd(x,0)=x$ ；

$x,y$ $x\ge y$ $\gcd(x,y)=\gcd(x\mod y,y)$ ；

两个正整数的最大公因数，为其中一个较大的数模另一个数的余数，与另一个数的最大公因数。

$\gcd(x,y)=\gcd(x-y,y)$ $x$ $y$ 即可；

证明等式，将其分解为两个不等式：

$\gcd(x,y)\le\gcd(x-y,y)$ ：
- $x$ $y$ $x-y$ （替换准则）；
$\gcd(x,y)\ge\gcd(x-y,y)$ ：
- $x-y$ $y$ $x$ （替换准则）；

如何估计这个算法的时间复杂度？

引理：

a \geq b ⟹ a \mod b < \frac{a}{2}

$b\le\dfrac{a}{2}$ $b\gt\dfrac{a}{2}$ 两种情况：
$b\le\dfrac{a}{2}$ $a\mod b\lt b\le\dfrac{a}{2}$ ；
$b\gt\dfrac{a}{2}$ $a\mod b=a-b\lt\dfrac{a}{2}$ ；

$\gcd(a,b)=\gcd(a\mod b,b)$ $O(\log N)=O(n)$ $O(n^2)$ ；

$O(n^3)$ ；

1.2.4 Euclid GCD 算法的延伸

$a,b$ $d$ ？

仅验证整除性肯定是不够的，所以我们再引入一个引理：

$d$ $a$ $b$ $x,y$ $d=ax+by$ $d=\gcd(a,b)$ ；

证明引理，将等式拆成不等式：
$d\le\gcd(a,b)$ ；
$\gcd(a,b)$ $a,b$ $d=ax+by$ $\gcd(a,b)$ $d$ $\gcd(a,b)$ $d$ $\gcd(a,b)\le d$ ；
得证；

现在讨论 “扩展 Euclid 算法”：


x
function extended_Euclid(int a, int b)
// Input: a >= b >= 0
// Output: Integer x, y, d, such that: d = gcd(a, b) and ax + by = d

if b == 0: return (1, 0, a)
(xp, yp, d) = extended_Euclid(b, a mod b)
// 多了一步迭代计算 x 和 y
return (yp, xp - [a/b] * yp, d)

再引入一个引理：

$a,b$ $d,x,y$ $d=ax+by=\gcd(a,b)$ 成立；

证明上面的引理，观察到这是个递归算法，因此可以考虑从递归终止条件归纳证明。
$b=0$ 的信息，使用归纳法证明：
$b=0$ 时，显然（？）
$b=k$ $k\in N_+$ ），算法是正确的；
$a\mod b\le b$ $\gcd(b,a\mod b)=bx^{\prime}+(a\mod b)y^{\prime}$ $x,y$ 是正确的；
$a\mod b=a-\lfloor a/b\rfloor b$ $d=\gcd(a,b)=\gcd(b,a\mod b)=bx^\prime+(a\mod b)y^\prime=bx^\prime+(a-\lfloor a/b\rfloor b)y^\prime=ay^\prime+b(x^\prime-\lfloor a/b\rfloor y^\prime)$ ；
$d=ax+by$ $x=y^\prime,\space y=x^\prime-\lfloor a/b\rfloor y^\prime$ ；

人手工应该如何计算 “扩展 Euclid 算法” 的答案呢？

$x,y$ $ax+by=d$ ：

$\gcd(a,b)=d$ $(d,0),(kd,d),\ldots,(b,a\mod b),(a,b)$ ；
$(d,0)$ $d$ $d=d+0$ $(kd,d)$ $d$ $d=d+(kd-k\cdot d)$ $(a_n,b_n)$ $(a_{n-1},b_{n-1})$ $b_{n-1}$ $d$ ；
$d=x\cdot a+y\cdot b$ ；

值得注意的是，扩展 Euclid 算法涉及数论中的重要定理：

$a,b$ $x,y$ $ax+by=c$ $\gcd(a,b)$ 的倍数。

此外，扩展 Euclid 算法可以应用于：

$ax+by=c$ 的整数解；
$ax+by=c$ 整数解的存在性；
$\mathbf{Z}_N$ 的乘法逆元；
……

注，由裴蜀定理可以证明以下结论：
$ax+by=\gcd(a,b)$ $(x_0,y_0)$ 可以由扩展 Euclid 得到（或者瞪眼法），通解可以写成：
$\begin{matrix} {\begin{aligned} x & = x_{0} + \frac{b}{gcd (a, b)} k \\ y & = y_{0} - \frac{a}{gcd (a, b)} k, k \in Z \end{aligned} \end{matrix}$

$\mathbf{Z}_N$ 的乘法逆元，及其算法时间复杂度了。

$\mathbf{Z}_N$ 上的乘法逆元

$\mathbf{Z}_N$ 系统的乘法逆运算的定义，有：

x 是关于 a \mod N 的一个乘法逆元 ⟺ a x \equiv 1 \mod N

$a$ $x$ $ax$ $N$ 除后余 1；
$\mathbf{Z}_N$ 系统中，两个元素的乘法结果为 1；

引出可以被数学证明的定理：

$a\mod N\in \mathbf{Z}_{N}$ $a$ $a$ $N$ 互素时等号成立；
$a$ $N$ $a$ $\mathbf{Z}_n$ 上的乘法逆元；
$\begin{aligned} a x \mod N = a x + k N & ⟹ gcd (a, N) divides a x \mod N \\ ⟹ If gcd (a, N) = 1, then Extend-Euclid gives us x, y s.t. a x + N y = 1 \\ ⟹ a x \equiv 1 \mod N \end{aligned}$
关于不可能大于 1 的证明，使用反证法易得。
$a$ $O(n^3)$ $n$ $N$ 的位数）；

总结：

$O(n)$ ，optimal；
$O(n^2)$ ；
$O(n^2)$ ；
$\mathbf{Z}_n$ $O(n)$ ；
$\mathbf{Z}_n$ $O(n^2)$ ；
$\mathbf{Z}_n$ $O(n^3)$ ；
$\mathbf{Z}_n$ $O(n^3)$ ；

总结两个定理：

$d=ax+by$ ；
$\mathbf{Z}_N$ $a$ $a$ $N$ 互素时才有（证明使用扩展 Euclid）。

1.3 素性测试

1.3.1 Definitions

引入 费马小定理：

If p is a prime ⟹ \forall a \in [1, p), a^{p - 1} \equiv 1 \mod p

证明：
$S$ $p$ $S=\{1,2,\ldots,p-1\}$ ，
$\{a|a\in S\}$ $\{ia\mod p|i\in S\}$ 形成一个简单排列变换。
$i$ $ia\mod p$ $S$ 内；
$(p-1)!=(p-1)!a^{p-1}\mod p$ ；
$p$ $(p-1)!$ $p$ $(p-1)!$ 得：
$a^{p-1}\equiv1\mod p$ ；

我们用费马小定理就能判断素数了吗？可惜不行，因为这不是充分必要条件。

$p$ 是合数，但是能通过费马测试。但是我们认为这种情况出现的概率比较小（但这些数是无限个的）；

$p$ $a$ $p$ $a$ 满足）！这种情况被称为 Carmichael 数，它可以被其他算法剔除。

$a$ $p$ $a^{p-1}\equiv0\mod p$ $p$ $a$ ；

$N$ 都满足：

$a$ $N$ $a^{N-1}\not\equiv1\mod N$ $a\lt N$ $N$ 将无法通过费马测试（有一半及以上的例子会破坏任意性）；

证明：
$a$ $a^{N-1}\not\equiv1\mod N$ $b$ $b^{N-1}\equiv1\mod N$ $a\cdot b$ 无法通过费马测试：
$(a\cdot b)^{N-1}\equiv a^{N-1}b^{N-1}\equiv a^{N-1}\not\equiv1\mod N$ ；
$a$ $b$ $a\cdot b$ $a\cdot b\mod N$ $a\cdot i=a\cdot j$ $ai\mod p=aj\mod p$ $i\equiv j\mod p$ $i,j\ne0$ $b$ 的假设矛盾）。
$b\rightarrow a\cdot b$ $a$ $N$ $a$ ；

所以：

$N$ $a\lt N$ 都通过费马测试，能 100% 确定是素数；
$N$ $N$ $a$ $\dfrac{1}{2}$ ；

$N$ $\dfrac{1}{2^{100}}$ 的概率出错。也就是说能保证绝大多数情况的正确性。

补充：Monte-Carlo Algorithms & Las Vegas Algorithms
Monte-Carlo Algorithms：时间复杂度确定，但算法正确性是个概率（例如这里的 prime test）；
Las Vegas Algorithms：时间复杂度不确定，但算法正确性确定（例如 quicksort）；

1.3.2 随机生成素数

引入 Lagrange 素数定理：

$\pi(x)$ $x$ $\lim\limits_{x\rightarrow+\infty}\dfrac{\pi(x)}{x/\ln x}=1$ ；

这说明：
素数有无限多个，只不过越大越稀疏而已；
$n$ $N$ $\log N\sim n$ $P=\dfrac{1}{\ln 2^n}\approx\dfrac{1}{n}$ ；

$n$ 位素数的算法：

$n$ $N$ ；
$N$ 进行素数测试，如果成功则输出；失败则重复上述过程；

$N$ $\dfrac{1}{n}$ $O(n)$ $O(n)$ ；

1.4 密码学

基本设定（roles）：Alice & Bob 传递信息，不希望 Eve（偷听者，仅尝试在不被发现的情况下获取 Alice 和 Bob 交换的信息）和 Ida（中间人，它可以打破通信的规则，例如伪造身份等等，也可以做 Eve 的窃听行为）知道消息；

如果 Alice 直接向 Bob 发送原封不动的消息（称为 “明文”），那么 Eve 可以直接监听到、Ida 还可以直接进行内容篡改。

1.4.1 对称加密

所以可以采用一种简单的做法来尝试防止 Eve 和 Ida 的行为：

$e_r(x)$ $d_r(x)$ $d_r(x)$ 的相关信息）；
其中这对函数有一些硬性要求：
- $e(x)$ $x$ $e(x)$ $x$ 的详细信息；
- $e(x)$ $d(x)$ 来进行无损加密；
$x$ $e(x)$ 称为 “加密” $e(x)$ $d(e(x))=x$ 解密；

$e(x),d(x)$ $r$ ；

Sidebar：按位异或与 AES 算法
按位异或（bitwise exclusive-or）就是一种选择。
$d_r(x)=e_r(x)=x\oplus r$ ；
$d_r(e_r(x))=(x\oplus r)\oplus r=x\oplus0=x$ ；
因为它满足一些优秀性质：
是一个双射函数，其逆函数就是自身；
$e_r(x)$ $x$ $r$ $x$ 的每个二进制位有 50% 概率不变，有 50% 概率相反；
硬件计算很快，性能好；
$r$ $r$ $x\oplus r$ $y\oplus r$ $x\oplus y=x\oplus r\oplus(y\oplus r)$ $x\oplus y$ 就会间接地泄漏信息。
$x\oplus y$ 中的 0 越多，说明选举群众的共识度越高，有更多的人选择类似。
为了解决这个问题，人们基于按位异或设计了一种更强的对称加密算法：AES（Advance Encryption Standard），它的好处是：
虽然算法公开，但可以重复使用密钥；
计算效率合适；
目前没有比 brute-force 更好的办法来破解（但也没有证明绝对不可破解）；

这种方式被称为 “对称加密”（Symmetric Cryptography），即加密、解密用的密钥相同。

而 $e_r(x)$ $d_r(x)$ $r$ $e_r$ $d_r$ 本身是公开的算法。

对称加密特点：

计算量小，吞吐量大，传输大量数据不会因为加解密成为性能瓶颈；
在不知道密钥信息的前提下，窃听者、中间人无法破坏通信的安全性；

$r$ ，这样 Eve 直接在信道上监听就能拿到解密函数。

也就是说，对称加密使用的密钥目前还没有办法保证不被网络上不可信任的设备截获。

因此需要更强大的措施来防止窃听者、中间人获取密钥。

1.4.2 非对称加密

假设我们通过某种方法获得了一个神奇的算法：

$e_a(x)$ $d_b(x)$ 解密；
$a$ $b$ $a$ $b$ $b$ $a$ 解密；
$a$ $b$ $b$ $a$ 解锁），如下：
$(a,b)$ $b$ $e_a(x)$ $b$ $d_b(e_a(x))=x$ 解密；

对，就这一个更改就让 Eve 没办法了：

$b$ $b$ $a$ 永远不在网络上传播（从生成开始一直保管在 Alice 那），所以他们将无法把消息加密还原回去，这样 Bob 发现消息不对就可以及时发现问题。

$b$ $a$ 就被称为私钥（Private Key），这种加密方式被称为 “非对称加密”（Asymmetric Cryptography）；

而私钥加密、公钥解密的过程被称为 签名（signing）；

Sidebar: RSA 算法
那么上面的 “神奇算法” 是如何实现的呢？数学家想出一个方法：
$p,q$ $N=pq$ ；
$(p-1)(q-1)$ $e$ $f:x\rightarrow x^e\mod N$ $\mathbf{Z_N}$ 上的双射，作为我们的加密函数；
$e$ $\mod(p-1)(q-1)$ $d$ $\mathbf{Z_N}$ $x$ $(x^e)^d\equiv x\mod N$ ；
证明：由于第 3 条蕴含第 2 条，所以下面仅证明第 2 条：
$\begin{aligned} e d \equiv 1 \mod (p - 1) (q - 1) \\ \Rightarrow & e d = 1 + k (p - 1) (q - 1) \\ \Rightarrow & (x^{e})^{d} - x = x^{e d} - x = x (x^{k (p - 1) (q - 1)} - 1) \end{aligned}$
$x^{k(p-1)(q-1)}-1$ $x^{k(p-1)(q-1)}-1=(x^{p-1}-1)(x^{q-1}-1)P_k$ ；
$x^{p-1}\equiv1\mod p$ $p$ $p,q$ $x^{k(p-1)(q-1)}-1\mod pq=0$ $x^{ed}-x\mod N=0$ $x^{ed}\equiv x\mod N$ 得证；
$(e,N)$ $d=e^{-1}\mod(p-1)(q-1)$ $f(x)=e_{r,N}(x)=d_{r,N}(x)=x^r\mod N$ 是加/解密函数。
$O(n)$ $\mathbf{Z_N}$ $O(n^3)$ ；
这个算法安全的前提是， $N$ $p,q$ （即：素因数分解是难问题）；

但是非对称加密也有缺陷：无论是生成公私钥，还是加密数据，计算都相当复杂、性能不佳，不适合用来传递大规模数据。

于是，一般可以采用这种措施：非对称加密先用来传递对称加密的密钥，然后之后的通讯就使用对称加密来通信。这样既利用了对称加密的特性（计算量小、不知道密钥的情况下基本没法破解），又利用了非对称加密的强大安全性。

1.4.3 证书

现在 Eve（窃听者）彻底没法窃听到任何有效数据了，但是 Ida 还有办法。

Ida 可以拦截 Alice 和 Bob 间的所有流量，然后在 Alice 向 Bob 第一次发送密钥时：

截获 Alice 的公钥，自己再重新生成一份新的公私钥；
用 Alice 公钥解密、用自己的私钥加密，最后把自己的公钥交给 Bob；
Bob 以为这是 Alice 的公钥，解密也能成功，殊不知用的是 Ida 的公钥；

这下，Alice 和 Bob 在不知情的情况下，把消息全都发给了 Ida，Ida 既掌握解密的公钥、所有消息，还能不被 Alice 和 Bob 发现。

Ida 在这里被称为 “中间人”，而这种行为被称为 “中间人攻击”（Middle-in-the-man Attack，MITM）；

这样是不行的。不过往好处想，还是之前的说法，只要我们保证第一次交换对称加密密钥的过程是安全的不就行了？这里的问题在于 Ida 可能会篡改公钥；

那么有什么办法是在暴露公钥的情况下，还能防止公钥被篡改的？

这理论上肯定没法只由 Bob 和 Alice 解决，还需要外界的帮助。于是人们引入了 “第三方公证” 的机制：

人们需要设立一个第三方机构，确保它不会与中间人勾结。第三方机构本身事先生成一对公私钥，然后：

Alice 在将用自己的私钥加密的 “对称加密密钥” 传给 Bob 前，先传给第三方机构，让第三方机构用它自己的密钥再加密一次；
Alice 将第三方加密后的密钥传给 Bob，Bob 使用第三方公开的公钥解密，再用 Alice 的公钥再解一次密，就能安全拿到接下来要进行对称加密的密钥了；

由于 Ida 无法伪造第三方机构，因此最外层的密钥没法突破，因此也没法得到里面的数据进行中间人攻击了。

这里，第三方机构（证书签发机构）提供的公钥被称为 “证书”（Certificate）。Alice 使用第三方公钥加密、Bob 将加密信息给第三方解密的过程，就称为 “证书签名”；

目前，这套机制能够完全防御 Eve（窃听者）、Ida（中间人 / 攻击者）对信息的窃听和篡改。当然，证书 + 非对称加密 + 对称加密的整套机制被应用在了 SSL/TLS 当中，为 HTTPS、SSH 等协议重要通信场合提供全面的保护。

Chapter 2. 分治算法

2.1 更快的乘法

$n$ $n^{\prime}$ $n\le n^{\prime}\le2n$ $n^{\prime}$ 是 2 的非负次幂；

$(a+bi)(c+di)$ $bc+ad=(a+b)(c+d)-ac-bd$ ；

也就是说乘法次数从 4 次变为 3 次；这对于单次计算来说没什么（常数优化），但在递归的用法时会获得极大地提升：

$x,y$ 按照 2 进制数位对半拆开：

$x=2^{n/2}x_L+x_R,\quad y=2^{n/2}y_L+y_R$ ；

$xy=2^nx_Ly_L+2^{n/2}(x_Ry_L+x_Ly_R)+x_Ry_R$ ，这样递归的时间复杂度：

$T(n)=4T(\dfrac{n}{2})+O(n)$ $\dfrac{n}{2}$ $T(\dfrac{n}{2})$ $\dfrac{n}{2}$ $O(n)$ $T(n)=O(n^2)$ ，不是和原来的算法一样吗？

$x_Ly_L,x_Ly_R,x_Ry_L,x_Ry_R$ 看似要 4 次乘法，实则 3 次乘法：

$x_Ry_L+x_Ly_R=(x_R+x_L)(y_L+y_R)-x_Ly_L-x_Ry_R$ ；

这样递归时间复杂度就变为：

$T(n)=3T(\dfrac{n}{2})+O(n)$ ；

$(x_R+x_L)$ $(y_R+y_L)$ $\dfrac{n}{2}+1$ $T(\dfrac{n}{2})$ ；

$n$ $\dfrac{1}{2}$ $O(\log_2 n)$ ；

$k$ $3^k$ $\dfrac{n}{2^k}$ $O(n)(\dfrac{3}{2})^k$ ，总时间复杂度：

T (n) = \sum_{k = 1}^{\log_{3} n} O (n) (\frac{3}{2})^{k} = O (n) (\frac{3}{2} \frac{1 - (\frac{3}{2})^{\log_{2} n}}{1 - \frac{3}{2}}) = O (n) (3 (\frac{3}{2})^{\log_{2} n} - 3) \sim O (n) ((\frac{3}{2})^{\log_{2} n} - 1) \sim O (n^{\log_{2} 3})

$3^{\log_2n}=e^{\ln3\log_2n}=e^{\ln3\ln n/\ln2}=e^{\ln n\log_23}=n^{\log_23}$ ；

$O(n^{\log_2 3})\approx O(n^{1.59})$ ；

事实上还能做得更好（快速傅里叶变换），以后介绍。

2.2 更一般的分治递推分析

$O(n)$ $a$ $n/b$ $O(n^d)$ $a$ 个这样的子问题合并；

$a$ $b$ 为规模缩放因子；

$T(n)=aT(\lceil\dfrac{n}{b}\rceil)+O(n^d)$ ，由数学推导可知大师定理（master theorem）：

\begin{matrix} T (n) = {\begin{aligned} O (n^{d}), & if d & > \log_{b} a \\ O (n^{d} \log n), & if d & = \log_{b} a \\ O (n^{\log_{b} a}), & if d & < \log_{b} a \end{aligned} \end{matrix}

$n$ $b$ $b$ $n$ $n\cdot b$ $\min\limits_{k\in\mathbf{N}}|b^k-n|\le n\cdot b$ ），
$\lceil\dfrac{n}{b}\rceil$ 造成的舍入影响。
证明：
$\log_bn$ $k$ $\dfrac{n}{b^k}$ $k$ $a^k$ $k$ $O((\dfrac{n}{b^k})^d)$ ；
$T(n)=\sum\limits_{m=1}^{\log_bn}a^mO(\dfrac{n^d}{b^{md}})=O(n^d)\sum\limits_{m=1}^{\log_bn}(\dfrac{a}{b^d})^m$ ；
$\dfrac{a}{b^d}$ 和 1 的大小需要分类讨论后才能代入等比级数求和：
$\dfrac{a}{b^d}\gt1$ $d\lt\log_ba$ $T(n)=O(n^d)q\dfrac{1-q^s}{1-q}=\dfrac{1}{q-1}O(n^d)((\dfrac{a}{b^d})^{\log_bn}-1)\sim O(n^{\log_ba})$ ；
$\dfrac{a}{b^d}=1$ $d=\log_ba$ $T(n)=O(n^d\log_bn)\sim O(n^d\log n)$ ；
$\dfrac{a}{b^d}\lt1$ $d\gt\log_ba$ $T(n)=O(n^d)q\dfrac{1-q^s}{1-q}=\dfrac{q}{1-q}O(n^d)(1-(\dfrac{a}{b^d})^{\log_bn})\sim O(n^d)$ ；
$d$ $\log_ba$ $n^d$ $\log_bn$ 都有；

2.3 应用：比较排序的时间下界

我们首先讨论归并排序。

$n$ $n=1$ $n\gt1$ 时，将数组大致平分，对每一部分递归，对二者的结果进行 merge()，返回 merge 的结果；

$a=2,b=2$ ，这里重要的是 merge（也是子问题合并）算法的时间复杂度；

$O(n)$ ；

$d=1=\log_ba$ $O(n\log n)$ ；

在上升到更一般的层面：所有的基于比较的排序都可以看成是一棵比较树，这一定是一棵二叉树，因为一次只能比两个数（以一个 3 个数间最少次数比较的排序为例）：

一定 $n!$ 个叶结点的二叉树。树高就是比较次数，所以我们希望树高越矮，比较次数越少，基于比较的排序时间复杂度更低；

$\log_2(n!)$ $O(\log n!)$ $O(\log n!)\sim O(n\log n)$ ，两种方法：

$n^{n/2}\le n!\le n^n$ ；
$\lim\limits_{n\rightarrow+\infty}\dfrac{n!}{\sqrt{2\pi n}(\dfrac{n}{e})^n}=1$ ；

2.4 应用：中位数算法再讨论

$O(n)$ ；

$O(n+k\log n)$ $O(n\log n)$ ；

本章我们讨论分治策略。说到分治策略解决 Top-K Problem，就不得不提快选算法。

$O(n)$ $O(n^2)$ 最坏，但最坏可能性很小。

我们再来详细分析它的时间复杂度。

假设我们认为，如果选到 25% ~ 75% 分位的数是好的选择。因此随机选 pivot “是好的” 的概率为 50%；

另外，概率学认为平均 2 次随机选择会选到 “好的” pivot。证明：

$E$ ，因此：

$E=\dfrac{1}{2}+\dfrac{1}{2}(\dfrac{1}{2}\times2+\dfrac{1}{2}(\dfrac{1}{2}\times3+\dfrac{1}{2}(\cdots)))=\sum\limits_{k=1}^{\infty}\dfrac{k}{2^k}$ $\dfrac{1}{2}E=\sum\limits_{k=1}^{\infty}\dfrac{k}{2^{k+1}}$ $E-\dfrac{1}{2}E=\sum\limits_{k=1}^{\infty}\dfrac{1}{2^k}=1$ $E=2$ ；

每两次 $\dfrac{1}{4}$ $T(n)\le T(\dfrac{3}{4}n)+O(n)$ ；

$b=\dfrac{4}{3},a=1,d=1$ $d\gt\log_ba$ $T(n)=O(n)$ ；

2.5 应用：矩阵乘法

20 世纪，有人发现 2 x 2 的矩阵乘法计算只需要 7 次乘法（原来需要 8 次）。

因为矩阵乘法可以分块 $n\times n$ $\dfrac{n}{2}\times\dfrac{n}{2}$ ），也利用递归算法，列式：

T (n) = 7 T (\frac{n}{2}) + O (n^{2})

$b=2,a=7,d=2$ $d\lt\log_ba$ $T(n)=O(n^{\log_27})\approx O(n^{2.81})$ $O(n^3)$ 降低了不少。

2.6 应用：计数逆序

考虑一个问题：

对 n 首歌排序，两种排序方法的相近程度可以使用某个 metric 来描述。这个 metric 被称为 “计数逆序”；
定义计数逆序：以任一个排序方法为基准，另一个排序方法中，所有元素间出现逆序的次数称为 “计数逆序”；

为了方便讨论，我们以一个顺序序列作为基准（例如 1~N），给定一个输入序列，问题转换为判断这个输入序列和基准序列间的计数逆序。

$O(n^2)$ （要知道所有元素的逆序次数），但是多做了很多事，必然可以优化。

现在发现，计数逆序的求解也可以通过分治法完成。考虑分治法如何 combine two subproblems：

$A,B$ $a\in A,\space b\in B$ $(a,b)$ 间的计数逆序？

$A,B$ 都无序，那么就情况就比较头疼：遍历的时间复杂度甚至可能不如不用分治法。

$A$ $B$ $b$ $A$ $a$ $B$ 中二分查找就行。得到的逆序数累加到数组总的计数逆序中；

$O(n\log n)$ $T(n)=2T(\dfrac{n}{2})+O(n\log n)$ ；

$A,B$ 归并的时候，边归并、边计算逆序。过程类似 merge sort，其方法如下：

$A,B$ $A$ ）作为基准序列（在递归过程中要一直做基准序列）；
$B$ 中的元素的逆序计数。现在比较两个指针的数的大小：
- $B$ $A$ $A$ $B$ 的读指针；
- $B$ $A$ 的读指针；
$A$ $B$ $B$ $A$ 剩下的部分复制到结果数组中，将逆序数和累加到总体的计数逆序中。

$O(n)$ ；

$T(n)=2T(\lceil\dfrac{n}{2}\rceil)+O(n)$ $O(n\log n)$ ；

这种算法的名称就称为 sort-and-count algorithm；

Chapter 3. The Algorithms using Fast Fourier Transform

3.1 Revisit Complex Number

复数的基本运算

$z=a+bi$ $(a,b)$ ；
$z=r(\cos\theta+i\sin\theta)=re^{i\theta}$ $(r,\theta)$ ；
$\theta\in[0,2\pi)$ ；
$-z=(r,\theta+\pi)$ ；
$(r_1,\theta_1)\times(r_2,\theta_2)=(r_1r_2,\space\theta_1+\theta_2)$ ；
$z$ $r=1\iff z^n=(1,n\theta)$ （由上面的乘法法则推得）；
$z^n=1$ 的解，可以在极坐标系中描述：
- $z=(1,\theta)$ $\theta=\dfrac{2\pi m}{n},\space m\in\mathbf{Z}$ ；
- $1,\omega,\omega^2,\ldots,\omega^{n-1}$ $\omega=e^{2\pi i/n}$ ；
$z^n=1$ $z$ $r=1$ 直接出来了。
$z^n=(1,n\theta)$ $n$ $\theta$ $(1,0)$ $z$ 的解集。
$n\theta=2\pi k$ $z=(1,\dfrac{2\pi k}{n}),\space k\in\mathbf{Z}$ ；
$z$ $z=e^{2i\pi k/n},k\in\mathbf{Z}$ $\omega=e^{2\pi i/n}$ $1,\omega,\omega^2,\ldots,\omega^{n-1}$ $n-1$ ，是因为后面回环了；
$n$ 为偶数时，解的符号是正负相间的；
$z=re^{i\theta},\space z^{*}=re^{-i\theta}$ ；

3.2 Begin with The Production of Polynomials

考虑一个问题，现在我们希望计算两个两个同次多项式之积：

$A_d(x)=a_0+a_1x+\cdots+a_dx^d$ $B_d(x)=b_0+b_1x+\cdots+b_dx^d$ ；

$C(x)=c_0+c_1x+\cdots+c_{2d}x^{2d}$ ，所以我们一般可以由相关系数（coefficients）计算：

$c_k=a_ob_k+a_1b_{k-1}+\cdots+a_kb_0=\sum\limits_{i=1}^k{a_ib_{k-i}}$ ；

$n$ $c_k$ $O(k)$ $c_k$ $2d+1$ $\Theta(d^2)$ 的时间复杂度；

能否简化这个时间复杂度？

$d+1$ $d$ 次的多项式，因此我们有两种多项式表示法：

$a_0,a_1,\ldots,a_d$ ；
$A(x_0),A(x_1),\ldots,A(x_d)$ ；

$A_d(x)$ $B_d(x)$ $C(x)$ $2d+1$ $2d+1$ $C(z)=A(z)\times B(z)$ ，因此，多项式的乘法在值表示法上只需要线性时间就能计算！

所以我们想，更简单的算法应该是这样的：

计算 $A,B$ $d$ $\Theta(n^2)$ ；
$C(x)$ $A(x_i)B(x_i)$ $O(n)$ ；
插值 $C(x)$ $O(?)$ ；

$\Theta(n^2)$ $O(n\log n)$ 。这个特殊的方法就是分治 + 快速傅里叶变换（Fast Fourier Transform，FFT）。

$\pm x_0,\pm x_1,\ldots,\pm x_{n/2-1}$ $A(x_i)$ $A(-x_i)$ 计算就会有很多重复：

偶数次幂相同（省去计算）；
奇数次项相反（取反）；

这么优化是常数时间的，还远远不够。

我们还要借鉴分治法的思想，我们发现：

A (x) = A_{e} (x^{2}) + x A_{o} (x^{2})

$A_e$ $A$ $A_o$ $n/2-1$ ；

$x$ $n$ $\dfrac{n}{2}-1$ 的多项式的值：

$\pm x_i$ ，

\begin{aligned} A (x_{i}) & = A_{e} (x_{i}^{2}) + x_{i} A_{o} (x_{i}^{2}) \\ A (- x_{i}) & = A_{e} (x_{i}^{2}) - x_{i} A_{o} (x_{i}^{2}) \end{aligned}

$A_e(x_i^2)$ $A_o(x_i^2)$ 结果可以复用。

假设我们能一直这么递归下去，那么：

$\pm x_i$ $n$ $A(x)$ $A_e(x_i^2),A_o(x_i^2)$ $\dfrac{n}{2}-1$ $x_i^2$ $\dfrac{n}{2}$ 个点的子问题。

$x_i^2$ $i$ $\dfrac{n}{2}$ $O(n)$ ，计算的时间复杂度为：

T (n) = 2 T (\frac{n}{2}) + O (n)

$T(n)=O(n\log n)$ ；

可惜的是，我们并没有办法一直这样持续下去 $x_i^2$ $x_i^2=-x_j^2\ne0$ ）；

这个时候就需要用到复数了：

$x_i$ $z^n=1$ $n$ $n\ge2d+1$ $n=2^k,\space k\in\mathbf{Z}$ $k$ 需要尽可能小）。为什么需要这么做？我们先顺着向下看。

$n$ $\omega=e^{2\pi i/n}$ $1,\omega,\omega^2,\ldots,\omega^{n-1}$ $A$ $2^k$ $2^k\ge2d+1$ $z^n=1$ $\omega^{n/2+j}=-\omega^j$ $1,\omega,\omega^2,\ldots,\omega^{n-1}$ 中，互为相反的复数成对出现；

$1,w^{2},\omega^{4},\ldots,\omega^{n/2-1}$ 中，相反复数仍然成对出现，如图：

现在我们描述这个 FFT 算法：


xxxxxxxxxx
FFT(A, w)
input: coefficient reprentation of a polynomial A(x) of degree ≤ n − 1, where n is a power of 2; ω, an n-th root of unity
output: value representation of A

if w == 1 then return A(1); // w = 1 说明当前 A 的次数最大为 1
express A(x) in the form Ae(x^2)+xAo(x^2)   // 其中 Ae、Ao 都用向量表示
// 递归计数 Ae(xi^2) 在 1, w^2, w^4, ... 共当前一半数量的点处的取值，
// 其中在 1, w^2, w^4, ... 中相反数成对存在
call FFT(Ae, w^2) to evaluate Ae at even power of w;
// 同理，递归 Ao(xi^2)
call FFT(Ao, w^2) to evaluate Ao at even power of w;

// 真正计算 1, w, w^2, w^3, ..., w^{n-1} 的点，其中 n 为满足 e^{2pi*i/n}=1
for j = 0: n - 1 do
    // 这里注意 1, w, w^2, ... 这些点也是正负配对的，
    // 因此实际操作可以同两边开始，一对一对地计算以减小计算量。
    compute A(w^j) = Ae(w^{2j}) + w^j * Ao(w^{2j})
end
return (A(w^0), A(w^1), ..., A(w^{n-1}));

$\omega_n^{k}$ $\omega_n^{k+n/2}$ 就能实现计算量的节省：

$A(\omega_n^k)=A_e(\omega_n^{2k})+\omega_n^kA_o(\omega_n^{2k})$ ，

$A(\omega_n^{k+n/2})=A_e(\omega_n^{2k+n})+\omega_n^{k+n/2}A_o(\omega_n^{2k+n})=A_e(\omega_n^{2k})-\omega_n^{k}A_o(\omega_n^{2k})$ ，

可以成对处理。

$A_e(\omega_n^{2k})$ $A_o(\omega_n^{2k})$ $\omega_n^{n}=1$ 的输入，递归终止。

$O(n\log n)$ 。现在我们来讨论相反的过程：插值。

我们注意到，如果得到了结果多项式的值表示，要反过来求系数，就是在解这个线性方程组：

\begin{array}{r} [\begin{array}{c} A (x_{0}) \\ A (x_{1}) \\ ⋮ \\ A (x_{n - 1}) \end{array}] = [\begin{array}{c} 1 & x_{0} & x_{0}^{2} & \dots & x_{o}^{n - 1} \\ 1 & x_{1} & x_{1}^{2} & \dots & x_{1}^{n - 1} \\ ⋮ & ⋮ & ⋮ & ⋱ & ⋮ \\ 1 & x_{n - 1} & x_{n - 1}^{2} & \dots & x_{n - 1}^{n - 1} \end{array}] [\begin{array}{c} a_{0} \\ a_{1} \\ ⋮ \\ a_{n - 1} \end{array}] \end{array}

$M$ $x_0$ $x_{n-1}$ $M$ $M^{-1}$ ；

$O(n^3)$ $O(n^2)$ $O(n\log n)$ ；

$1,\omega,\omega^2,\cdots,\omega^{n-1}$ $M$ ：

\begin{matrix} {[\begin{matrix} 1 & 1 & 1 & \dots & 1 \\ 1 & ω & ω^{2} & \dots & ω^{n - 1} \\ ⋮ & ⋮ & ⋮ & ⋮ \\ 1 & ω^{j} & ω^{2 j} & \dots & ω^{(n - 1) j} \\ ⋮ & ⋮ & ⋮ & ⋮ \\ 1 & ω^{n - 1} & ω^{2 (n - 1)} & \dots & ω^{(n - 1) (n - 1)} \end{matrix}]}_{n \times n} \end{matrix}

$a_{ij}=\omega^{ij}$ ，注意到它有个相当优秀的性质：

$M^T=M$ ；
$M^{H}_{r*}M_{*s}=\sum\limits_{j=0}^{n-1}{\omega^{jr}}^{*}\omega^{js}=\sum\limits_{j=0}^{n-1}\omega^{-jr}\omega^{js}=\sum\limits_{j=0}^{n-1}\omega^{j(r-s)}=0$ ；
$||M_{*k}||_2^2=\sum\limits_{j=0}^{n-1}|\omega^{jk}|^2=n$ $M^HM=nI$ ；
$1,\omega^{k},\omega^{2k},\ldots,\omega^{(n-1)k}$ 中仍然有成对的相反的单位长度复向量，它们在取模平方后会变成 1；

$A$ （多项式系数向量）时的变换矩阵。这个矩阵对应的线性变换被称为傅里叶变换（Fourier Transformation），人们将其列向量称为傅里叶基（Fourier Basis）；

$M^HM=nI$ $M_n^{-1}=\dfrac{1}{n}M^H=\dfrac{1}{n}M^*$ ，我们惊喜地发现，计算：

\begin{matrix} M^{*} [\begin{matrix} A (x_{0}) \\ A (x_{1}) \\ ⋮ \\ A (x_{n - 1}) \end{matrix}] \end{matrix}

$\omega$ $A$ $n$ $\omega$ $A(x_i)$ 向量则是给定的点；

$n$ $\dfrac{1}{n}$ $O(n\log n)$ ；

Chapter 4. Graph

4.1 Revisit: DFS in Graph

首先定义一些本章会用到的方法：


xxxxxxxxxx
procedure EXPLORE(G, v)
input : G = (V, E) is a graph; v ∈ V
output: visited(u) to true for all nodes u reachable from v

visited(v) = true;
PREVISIT(v);    // 定义一个在 visit 前的活动
for each edge (v, u) ∈ E do
    if not visited(u) then EXPLORE(G, u);
end
POSTVISIT(v);   // 定义一个在 visit 后的活动


xxxxxxxxxx
procedure DFS(G)
for all v ∈ V do
    visited(v) = false;
end
for all v ∈ V do
    if not visited(v) then Explore(G, v);
end

4.2 无向图的连通分量

多次 DFS 计算连通支数：通过在 PREVISIT(v) 中定义 ccnum[v] = current_cc，然后 current_cc 在每次 DFS 后自增；
最终可以得到总连通支数、各个顶点所属连通支情况；
定义结点的 “生命周期”（从 pre visit - post visit），用 pre[], post[] 表示，可以定义：
```
xxxxxxxxxx
procedure PREVISIT(v)
pre[v] = clock;
clock++;
```
```
xxxxxxxxxx
procedure POSTVISIT(v)
post[v] = clock;
clock++;
```
则有引理：
$u,v$ ，生命周期间隔 [pre(u),post(u)] 和 [pre(v), post(v)] 要么是彼此分离的（disjoint），要么是一个完全包含另一个的；
$u$ $u$ 在栈中的时间；而由于栈后进先出的性质，好像引理不证自明；
证明：
反证。假设生命周期存在 overlap，即 pre(u) < pre(v) < post(u) < post(v)pre(u) < pre(v) < post(u) $u$ $v$ $u$ $v$ $u$ 在遍历栈的上部位置，因此 post(v) < post(u)，这与 post(u) < post(v) 矛盾，因此原命题得证；

注意，每次 DFS 后 pre 和 post number 不会重置，各个顶点的 pre/post number 只会增大；

4.3 有向图的连通分量

我们已经了解，对有向图 DFS 会生成深度优先森林（DFS Forest）。

$G$ ）：

$G$ $E_i$ ，也是该有向图 DFS 森林中的某条边；
$G$ $E_i$ ，但在 DFS 森林中指向的不是结点的直接后继（子结点）；
不是树边，而是指向间接后继结点；
$G$ $E_i$ ，但在 DFS 森林中指向的是结点的祖先结点；
不是树边，而是指向祖先结点；
$G$ $E_i$ ，但指向的既不是该结点的后继（子孙结点），也不是祖先结点；
不是树边，指向 siblings 一族结点（既不是祖先结点，也不是子孙结点）；

$(u,v)$ ，可以这么分类：

$[_u\quad[_v\quad]_v\quad]_u$ ；
$[_v\quad[_u\quad]_u\quad]_v$ ；
$[_v\quad]_v\quad[_u\quad]_u$ ；

$G$ 中的边只有这些分类？

$[_u\quad]_u\quad[_v\quad]_v$ ；

$[_u\quad]_u\quad[_v\quad]_v$ $]_u$ $[_v$ $u,v$ $(u,v)$ $(u,v)$ $u,v$ $u$ $v$ $v$ $(u,v)$ $G$ 中只有可能有以上几类情况。

4.4 有向无环图（DAG）

给出引理：

$G$ 当且仅当 $\exists E_i\in G$ $E_i$ 在 DFS 森林中是回边；

证明：

$(u,v)$ $G$ $u$ $v$ $u$ $v$ $u,v$ 间的自环；
$v_0\rightarrow v_1\rightarrow\cdots\rightarrow v_k\rightarrow v_0$ $G$ $v_i$ $v_i$ $v_i$ $(v_{i-1},v_i)$ $i=0$ $(v_k,v_0)$ ），因此这条边是 DFS 树中的回边；

$(v,u)$ 满足 post(v) < post(u)，并引出另一条引理：

在 DAG 中，每一条边总是指向 post number 减小的方向。

至此我们发现：一个有向图：无自环、可线性化、无回边实际上相互等价（是同一件事）；

进而：DAG 中，post number 最小的点一定是汇点（出度为 0），post number 最大的点一定是源点（入度为 0）；

由于正整数集上的可比性，DAG 上所有结点中必定有 post number 最大的，也必定有最小的，即证明了另一条引理：

每个 DAG 中，至少有一个源点和一个汇点；

因此，我们找到一种线性化 DAG 的方案：找到源点（post number 最大点）删除并输出，重复这个过程直至图为空；

4.5 Revisit: 有向图强连通分量

我们已经知道：

两结点间存在一条从 $v_i$ 到 $v_j$ 的有向道路且存在另一条从 $v_j$ 到 $v_i$ 的有向道路，则称 $v_i$ 和 $v_j$ 强连通；
两结点间仅存在一条从 $v_i$ 到 $v_j$ 的有向道路或仅存在另一条从 $v_j$ 到 $v_i$ 的有向道路，则称称 $v_i$ 和 $v_j$ 单向连通；
两结点间 不考虑所有道路的方向（称为“有向图的底图”），若这两个结点连通，则称 $v_i$ 和 $v_j$ 弱连通；

而且：

有向图 G 中任意两结点间都是强连通的，则 G 为强连通图；
G 的强连通子图 H 不是 G 的任何其他强连通子图的真子图，称 H 为 G 的一个极大的强连通子图，也称强连通分量；

另外，我们在有向图中讨论 “连通”，一般都指 “强连通”，除非额外说明。

现在，我们将一个有向图按强连通分量划分为若干个不相交集，如果：

将强连通分量顶点和内部边组成的集合看作一个超结点；
若划分时两个超结点内部结点间可达，则两个超结点连有同向有向边；

则一定会得到一个 DAG，我们称这种形成的 DAG 为 embedding graph（嵌图）；

这就是引理：任意一个有向图的 embedding graph 一定是 DAG；

引入定义：源/汇点强连通分量：一个有向图中，它的 embedding graph 中源/汇点对应的强连通分量；

现在考虑如何找出任意一个有向图的强连通分量。

现在已知已经存在了有效的求解强连通分量的算法，线性时间复杂度，它主要基于一些性质：

$u$ $u$ 及其所有可达结点已访问时终止；
这个性质告诉我们：如果在一个汇点强连通分量的任一顶点调用 explore 子过程，则恰好能获得这个强连通分量；
为什么必须是汇点？不然这个超结点出度不为 0，调用 explore 会出这个超结点，或者说可达结点在这个超结点之外也有；
问题是：
1. 如何确定一个有向图的汇点强连通分量中的一个顶点？
2. 通过这个性质获得了汇点强连通分量后，下一步应该怎么办？
针对第一个问题，我们率先给出了下面的性质：
在 DFS 中 post number 最大的点一定位于其中一个源点强连通分量内；
注意，post number 最小的点不一定在汇点强连通分量内，因为原图不是 DAG。这个 “post number 最大的点一定位于源点强连通分量” 的规律是比较特殊的。
由于证明它需要另外一个性质，因此先介绍：
$C$ $C^{\prime}$ $G$ $C$ $C^{\prime}$ $C$ $C^{\prime}$ 的 post number 最大值（不是所有结点都大于）；
现在先证明这条性质：
$u\in C,v\in C^{\prime}$ $C$ $C^{\prime}$ $C^{\prime}$ $C$ $C$ $C^{\prime}$ $v$ $C$ $u$ 不单向连通。分情况：
- $C^{\prime}$ $C^{\prime}$ $C$ $C^{\prime}$ $C$ 的情况；
- $C$ $C$ $u$ $C$ $C^{\prime}$ $C$ $C^{\prime}$ $u$ $C$ $C^{\prime}$ 中 post number 最大的结点；
综上，这条性质得证；
再证明上一条性质：
$(u^{\prime},v^{\prime})$ $u^{\prime}\in C,v^{\prime}\in C^{\prime}$ $C$ $C^{\prime}$ $E_0$ $E^{*}$ $E^{*}$ 的 post number 最大值更大。因此最大 post number 的结点一定位于其中一个源点强连通分量中，性质 2 得证；

有了 2、3 两个性质，我们能解决：“如何确定一个有向图的汇点强连通分量中的一个顶点” 的问题。

$G$ $G^R$ $G^R$ $G$ $G^R$ $G$ 的强连通分支中的结点情况相同。

证明：

$G^R$ $G^R$ $G$ 的汇点的强连通分量中！我们于是能成功找到整个汇点强连通分量。

$G$ $G^R$ 中对 post number 排序，不需要删除来决定新的汇点强连通分量是谁。总结：

$G^R$ $E_e,\cdots,E_2,E_1$ $E_e$ $E_e$ $G$ 的汇点强连通分量中）；
$E_e$ $G$ 中执行无向图连通算法（就是 explore，PREVISITccnum[] $E_k$ ，按 post number 降序遍历，重复本步，直至所有点都已划归为一个强连通分量为止；

线性时间 $O(\log^{*}n)$ 的算法。

考虑习题：
$G = (V, E)$ $s\in V$ from which all other vertices are reachable.
如果这个点存在，那么它一定在源点强连通部件中（反证法）；
找到任意一个源点强连通部件，做一次 DFS，如果没有遍历完所有顶点，则不存在；反之存在，并且这个强连通部件中的所有点都符合题意。

4.6 BFS in Graph

我们知道 DFS 可以找到图两点间的连通性，但是对于两个点间的最短距离却不清楚。我们可以利用广度优先搜索（BFS）来确定两点间的距离）。

我们本章认为 BFS 是先入队、更新距离，之后再出队。

并且和 DFS 不同，我们只关心同一个强连通分量中的距离情况。

有个 lemma。BFS 过程中， $d\in\mathbf{N}$ ，都总存在一个时刻，使得：

$s$ $d$ 的顶点都被正确地设置了距离；
$+\infty$ ）;
$s$ $d$ 的顶点；

可以证明：当前队列中的所有结点总小于下入队一元素的距离；

这个 lemma 形象地说明 BFS 是“按层输出”的。

4.7 正权图中两点间的单源最短路径

我们知道 BFS 只能知道等边权情况下的两点距离。如果我们需要将边长（边权）考虑进去，则就没法适用。

$l_e$ $(u,v)$ $u,v$ $l_e-1$ 个顶点），相当于转换成了等边权图。

$O(|V|+\sum\limits_{e\in E}l_e)$ ，也就是时间复杂度任意的坏（不知道边长的情况）。

再改进一些，就是 Uniform Cost Search；算法的思路是：

使用优先级队列保存结点队列（准备访问的结点），先入队起点；
总是从优先级队列中取出准备访问的结点中 cost 最小的结点，更新最短距离情况；
- 如果存在最短距且更小，则什么也不做，继续出队；
- 反之，更新这个结点的最短距，并且更新 pre[]（总是指向当前结点最短距的前一个结点，通过这个就能在最后避免回溯地获得任意结点最短路径）；
  如果没访问过这个结点，则将结点入队（Tree Search 不做这步）；
最终队列为空停止；

Dijkstra Algorithm 就是在这个算法的基础上，先将所有结点构建优先级队列（比逐个插入更快），然后通过手动出队、手动减小更新后的元素优先级、通知优先级队列调整被减小键值的元素（就是 decreaseKey），达成上面的目标。

$\infty$ ，只有源点是 0；然后对所有结点构建优先级队列；
在队列不空时循环出队：
- $u$ 时，更新相邻结点距离。如果更小就覆盖（此举会改变相邻点在优先级队列中的位置），并且维护最短路径列表 pre[]（如果需要）；
$u$ 不会再入队。这就是存在负边权时 Dijkstra 算法失效的原因。

上面的 pre[] 用到了两个性质：

$A\rightarrow C\rightarrow B\rightarrow D$ $A,D$ $A\rightarrow C\rightarrow B$ $A，B$ 间的最短路；
$dist(A,D)=dist(A,B)+l_{BD}$ ；

注意到我们可以用相似的思路，让我们把所有顶点都先放到优先级队列中（减小出入队的开销），然后遍历点是动态地更新点的最短距（也就是改变优先级队列中某元素的优先级），当我们确定下某个点的优先级后，直接将它出队，这就是 Dijkstra Algorithm；

现在我们关心这个 “优先级队列” 的实现，以及它对于各种操作的复杂度。

众所周知，优先级队列通常使用堆来实现。我们比较常用的数据结构在 Dijkstra 算法中的使用的操作的耗时情况：

Type \ Aspect	delete min	insert/decreaseKey	`\|V\|×deletemin+(\|V\|+\|E\|)×insert`
Array	$O(\|V\|)$	$O(1)$	$O(\|V\|^2)$
Binary Heap	$O(\log\|V\|)$	$O(\log\|V\|)$	$O((\|V\|+\|E\|)\log\|V\|)$
d-ary Heap	$O(\dfrac{d\log\|V\|}{\log d})$	$O(\dfrac{\log\|V\|}{\log d})$	$O(\dfrac{(d\|V\|+\|E\|)\log\|V\|}{\log d})$
Fibonacci Heap	$O(\log\|V\|)$	$O(1)$ (amortized)	$O(\|V\|\log\|V\|+\|E\|)$

因此有这几个事实：

$|E|\lt\dfrac{|V|^2}{\log|V|}$ ），使用二叉堆比数组好；
$|E|=\Omega(|V|^2)$ ），使用数组比二叉堆好；
$d$ $d=[\dfrac{|E|}{|V|}]$ $|E|=|V|^{1+\delta}$ ）可以达到线性时间！

$d$ $d$ $j$ $\lceil\dfrac{j-1}{d}\rceil$ $[(j-1)d+2,\min\left\{n,(j-1)d+d+1\right\}]$ ；

4.8 含负权无负环图中两点间的单源最短路径

如果一个图中存在负值的边权，那么为什么 Dijkstra Algorithm 不再适用了？

我们回顾 pre 用到的两个性质，子路径最短性、子路径距离可加性 都没有违反！

那究竟是哪里出问题了？实际上是这个假设： $s$ $v$ $v$ $s$ 更近的顶点！

也就是 Dijkstra Algorithm 总是从当前最近到远的方法依次更新最短距，但是如果远处有个负值会降低路径总长度，那么需要重新更新这条路上所有已经确定最短路径的顶点。

更严谨地说，我们应该从如何证明 Dijkstra Algorithm 的角度下手，看看究竟哪个证明步骤不再成立。
原先我们使用归纳假设证明 Dijkstra Algorithm：
$s$ 的所有相邻结点位置后（每一轮 while 循环后），有下列条件成立：
条件 1. $d$ $s$ $R$ $d$ $s$ $R$ 所有 $d$ ；
条件 2. $r\in R$ $s$ $r$ $R$ 中；
$d=0$ 时（起点），上述假设显然成立；
$u$ $u$ $R$ $u$ $v_i$ 。接下来需要：
$u$ $v_i$ 最短距离一定是正值 $d+\min\limits_i\{|u v_i|\}\gt d$ 满足条件 1；
$s$ $u$ 上一个顶点 $p$ $s$ $p$ $s$ $p$ $s$ $p$ $R$ 中。
$u$ $u\in R$ $(p,u)$ $R$ $s$ $u$ $R$ 上。条件 2 仍然成立。
综上，我们证明了在 Dijkstra Algorithm 的每轮 while 循环上，都有条件 1、条件 2 成立。
$s$ $v$ $v$ ；这就是 Dijkstra Algorithm 的正确性。
我们发现，如果边不再是正数，那么归纳假设中就没法证明条件 1 了！
$R$ $q$ $d$ $A\rightarrow B\rightarrow C$ $B$ $C$ $A$ $B$ 会普遍比其他结点“更难”出队、更后面出队），又由于 Dijkstra Algorithm 没法更新已经出队的结点的最短距，因此没法找到这条最短路径！

sidebar：那么能不能同时加上负值的绝对值最大值来转换成非负权的问题？不行。因为最短路中每条边被使用的次数不一样，因此这样转换没法等价为原问题。

所以本质上，Dijkstra Algorithm 无法求单源含负权图的最短路，就是因为没法更新出队后的结点最短距，因为它认为先出队的结点一定能更近地到达目标结点！

所以 “乱拳打死老师傅”，我们只要更新最短距的次数足够多、足够充分（没有 side effect 的话），那一定能知道真正的最短路。事实上也确实是这样，这就是 Bellman-Ford 算法：


xxxxxxxxxx
procedure BellmanFord(G, l, s):
(V, E) = G
for all u in V:
    dist(u) = infinity
    prev(u) = nil

// start point
dist(s) = 0
repeat |V| - 1 times:
    for all e in E:
        update(e)

procedure update((u, v) in E):
dist(v) = min{dist(v), dist(u)+l(u,v)}

这个 for all e in E 的遍历是有说法的，这不仅仅是 Dijkstra Algorithm 的一次 while 循环（确定已知顶点的相邻顶点的最短距），而是：

从顶点角度看：没有出队地确定 “所有已确认过最短距的顶点 + 未确认的相邻顶点” 的最短距；
从边的角度看：只要边有一个顶点的最短距不是无穷，就更新这条边两端顶点的最短距；

$|V|-1$ 次后，一定能获得各个顶点的最短距，并且大多数情况下顶点早于这个轮数就遍历全了。

补充：负环问题 & 最简最短路

显然，如果一个图含有负环，那么就别想求最短路了，因为最短距是负无穷。

但是如果我要求的是最简道路（不含重边和环的道路）中的最短路呢？那又可以求了！

4.9 含负权的 DAGs 中两点间的单源最短路径

如果是 DAG，那么借助这个好的性质，单源最短路径的算法甚至可以优化到线性时间。

我们知道 DAG 可以线性化，那么很显然，按照线性序的顺序访问各个顶点，直接按照沿途的边来更新结点最短距，那一定可以获得各个结点最终的最短距。

算法很简单，就是先做一次拓扑排序，标记顺序后，沿顺序遍历点，更新点的所有相邻结点的目前最短距（不继续展开，而是跟从外层循环给定的顺序），时间是线性的。

如果要求 DAGs 最长路，那么把所有边权全部转为相反数，使用求 DAGs 最短路的方法即可。

考虑问题：

有向正权图中最简最长路径？
NP Hard 问题。
有向正权图的最短环？
对每个点使用一次 Dijkstra Algorithm，找到它与其他顶点的最短距离；
$u,v$ $\text{dist}(u,v)+\text{dist}(v,u)$ $O(|V|^3)$ ；
$e_0$ $e_0$ 的最短环的长度；
$e_0$ $u,v$ $u$ $v$ $\text{dist}(u,v)$ $\text{dist}(v,u)$ $l_e$ $O(|V|^2)$ ；
$v_0$ $v_0$ ；
$v_0$ $dist(u,v_0)+dist(v_0,v)$ ；
无向正权图的最短环？
$\infty$ $c_i$ $c_i+l(e)$ 的环。遍历找长度最小的那个。
无向等权图中指定两点间最短路径数量？
$u$ $u$ 相邻的结点。其数量即为所求。
这个方法的原理是利用 BFS 的性质：在每轮结束后队列中放的是相同长度的结点（分开放能确保下一轮的结点不会混入当前队列中）。
拓展：如果是有向/无向正权图，可以修改 Dijkstra 算法更新 dist[u] + l(u,v) == dist(v) 时修改 bool 数组；

Chapter 5. Greedy Algorithms

5.1 Minimal Spanning Tree (MST)

对无向图，我们有引理 1：移除一个环上的边，不会改变这个图的连通性。

由引理 1，结合树的定义，我们可以得知：任何一个无向图，都有一个最小生成树，在保持原图连通性的同时边权和最小。

证明引理 2 $n$ $n-1$ 条边。证明过程对顶点数学归纳。

1 个顶点、0 条边的图是树；
如果一个树有 k 个顶点、k - 1 条边；则对于一个 k+1 个顶点，在 k 个顶点的基础上添加一个无向边将新的顶点与树相连，则新的图也满足树的结构，并且拥有 k 条边；

对边数学归纳：

起始状态没有边，n 个顶点不相连，有 n 个连通部件。每次向其中加一条边，要求连接其中两个不同的连通部件，则全图的连通部件数减 1；
重复上述动作，总有一个时刻全图的连通部件数为 1，此时图满足树的定义，并且边为 n - 1 条；

证明引理 3（引理 2 的逆命题） $|E|=|V|-1$ ，那么它一定是一棵树。反证法。

$|E|=|V|-1$ $e$ $|E|'$ $|E|'=|V|-1$ $|E|=|V|-1$ $|E|'\gt|E|$ 矛盾；

证明引理 4：一个无向图是一棵树当且仅当任意两结点间有一条唯一路径。分开左推右和右推左：

$\Rightarrow$ ：显然在一棵树中，任意两个结点间只能有 1 条路径。假设其间有两条路径，则这两条路径的集合构成一个环，不满足树的前提；
$\Leftarrow$ ：如果一个图的任意两个结点间只有一条路径，则说明全图只有一个连通部件，并且是无环的（也可反证），这满足树的定义，因此这个图是一棵树；

Kruskal 算法求 MST：

$|V|-1$ 个边结束。

这本质上就是一个 greedy approach；

割定理：

$X$ $G=(V,E)$ $S$ $X$ $S$ $V\backslash S$ $S$ $V\backslash S$ $G$ 的一个割（cut set，图按顶点分割）。

$S$ $V\backslash S$ $e$ $X\cup\{e\}$ $G$ 的最小生成树的一部分。

分类讨论 + 反证法证明割定理：

$G$ $T$ ；

$e\in T$ $X\cup\{e\}\subseteq T$ ；

$e\not\in T$ $e^{\prime}$ $S$ $V\backslash S$ $e^{\prime}\in T$ $T^{\prime}=T-\{e^{\prime}\}+\{e\}$ $w(T^{\prime})\lt w(T)$ $T^{\prime}$ $T+\{e\}$ $e^{\prime}$ $T^{\prime}$ 是连通的；再由 lemma2、3 得到是树）也就是这个树的边权和小于原来的 MST，这是和 MST 定义矛盾的。因此这种情况不存在。

Prim 算法求 MST：

$S=\{v_0\}$ $S$ $V\backslash S$ $S'$ $|V|-1$ 条边。

正确性由割定理保证。

考虑新的上色算法：

先指定两条上色规则：

$C$ $C$ 中选择一条最长的未着色边，并将其染成红色；
利用了树的定义，这步的转换肯定是正确的；
$D$ $D$ 中选择一条最短的未着色边，将其着色为蓝色。
利用了割定理，这步的转换也肯定是正确的；

在图上随便使用上述规则上色，直到所有边都着色为止。

最后所有的蓝色边就是这个图的 MST；

这个算法是正确的吗？我们已经知道了这两条规则是必要的，但是它能做到最后吗？

也就是说，如何证明这种上色方法能够一直做到全部上色完成而不产生冲突？

5.2 Set Cover（集合覆盖问题）

$S$ $S$ $V$ $d$ ；

这个问题等价于：

$B$ $S_1,S_2,\ldots,S_m\subseteq B$ $S_1,S_2,\ldots,S_m$ $\bigcup\limits_k{S_k}=B$ ，并且选取的集合最少。

遗憾的是，这个问题暂时没有多项式时间算法（NP Hard）。不过我们考虑 Greedy Algorithm 作为近似算法。

$S_k$ ，直至最终覆盖完全。

$\ln n$ 倍（局部最优和全局最优的误差的上界）。

证明：
$n_t$ $t$ $n_0=n$ $\text{OPT}$ 个集合；
$\text{OPT}$ 鸽巢原理（抽屉原理） $\text{OPT}$ $\dfrac{n_t}{\text{OPT}}$ $\dfrac{n_t}{\text{OPT}}$ 个元素，那么最后一定覆盖不完，这与 “最优集合能覆盖完所有顶点” 的前提矛盾）。
$n_{t+1}\le n_t-\dfrac{n_t}{\text{OPT}}$ （因为贪心法会选出每步的最优解），所以数学上：
$n_{t} \leq n_{0} (1 - \frac{1}{OPT})^{t} < n_{0} (e^{- \frac{1}{OPT}})^{t} = n_{0} e^{- \frac{t}{OPT}}$
$t=\ln n\cdot\text{OPT}$ $n_t\lt ne^{-\ln n}=1$ $\text{OPT}$ $\ln n$ 倍更差。

5.3 贪婪算法何时失效：Coins Charging

$\{1,5,10,25,100\}$ （单位略），如何用最少的货币数量凑出指定的值？

Cashier's Algorithm 就是一个 Greedy Algorithm：每次选取

但是这种最优是因为特殊的面值组合。

$\{1, 10, 21, 34, 70, 100, 350, 1225, 1500\}$ 要凑出 140；

$\{7,8,9\}$ 凑 15；

嗯，贪婪算法之所以失效，就是因为局部最优解会逐渐偏离全局最优解。接下来我们将介绍一种能够解决这种问题的算法。

Chapter 6. 动态规划

我们在解决 DAGs 中最短路径的问题（线性化后逐结点解决）的时候，使用的就是动态规划。

动态规划的解决方案，就是解决子问题的途中记录下子问题的解，最后利用这些记录的解得出最终问题的解。

分治法和动态规划的区别？
动归：小问题和大问题大小差不多（两者都是包含关系）；
动归：小问题不会 overrlap（很重要，充分利用了各个子问题的解）；

6.1 最长子序列问题 I：最长递增子序列

$a_1,a_2,,\ldots,a_n$ 最长的 $a_{i1},a_{i2},\ldots,a_{ik}$ $a_{i_1}\lt a_{i_2}\lt\cdots\lt a_{i_k}$ $i_1\lt i_2\lt\cdots i_k$ （不要求连续）。

这个问题的思路可以是用图来解决：

每个元素就是一个结点；
$(a_i,a_j)$ $a_i\lt a_j$ $i\lt j$ ；

这样所有的序列都可以转换为一个 DAG 图，那么原问题转换为求出这个 DAG 的最长路径。

$L(i)=0$ （线性时间）；
$L(j)=1+\max\{L(i)|(i,j)\in E\}$ $|E|$ 成正比）；
$L$ 数组，获得最大的值就是最长路径（也就是原问题的解）；

6.2 编辑距离

编辑器中需要有 spell checking，通常会检查 typos；而 typos 的修改建议就是借助了单词间的编辑距离。

编辑距离描述了一个单词最相近的另一个（改变次数最小，使得一个单词变成另一个单词）；

我们使用一个二维表格（含有空白）来描述编辑距离：

$ED[i,0]=i$ $ED[0,j]=j$ ；
$ED[i,j]=\min\{ED[i,j-1]+1,ED[i-1,j]+1,ED[i-1,j-1]+\text{diff}(i,j)\}$ ；
$\text{diff}(i,j)=(x[i]==y[j])$ ；
含义：只增大一方的长度（多考虑一个），则编辑距离就是在原本的基础上 + 1 个距离；如果同时增大双方的长度，则编辑距离取决于是否替换这个字符；

这被称为动态规划的 “状态转移方程”。

$O(m\cdot n)$ $m,n$ 分别为两个词的长度）；

比较有意思的是，这里时间复杂度和空间复杂度都能优化：

$ED$ 中相关 entry 间看成连接的一条条路径，可以：

进一步使用分治（求最短路径）降低时间复杂度；
仅保留其中两列 / 两行来降低空间复杂度；

6.3 背包问题

6.3.1 `01`-背包问题

考虑一个问题题干：

$N$ $V$ $i$ $C_i$ $W_i$ ；

求解在不超过容量限制的情况下，如何装入背包以获得最大价值。

在 01 背包的假设下，我们有前提：每个物品只有 1 件，只可以选择放或者不放。

这种做法比较简单，和之前我们讨论的编辑距离一样，都可以利用动态规划 “放一步看一步”。

$F[i,v]$ 表示 $i$ 个物品放入 $v$ 的背包后，可以获得的最大价值；

$i$ 个”？因为动态规划需要子问题总是被包含在大的问题内；

很容易地得到状态转移方程：

$F[0,j]=0$ ；
$F[i,v]=\max\{F[i-1,v],\space F[i-1,v-C_i]+W_i\}$ $i$ 个物品，要么不要）；
$v$ $i$ $v-C_i$ 了；
$v-C_i$ 容量的背包，但是为了动态规划借用中间结果，我们勉为其难求一下。

求解方法也很简单，就是填表，伪代码如下：


xxxxxxxxxx
procedure pack01(N, V, Costs, Values)
# output: max value we can gain

F[0, 0...V] <- 0

for i <- 1 to N
    for v <- Costs[i] to V
        F[i, v] = max{ F[i - 1, v], F[i - 1, v - Costs[i]] + Values[i] }

return F[N][V];

$O(NV)$ 时间和空间可以优化。我们以空间优化为例：

$i$ $i-1$ 的内容，因此我们可以只保留 2 行，更巧妙地，1 行的数据（转换成一维列表）：

$F[v]$ $F[i-1,v]$ $F[i-1,v-C_i]$ $v$ $v$ $v$ 小的位置遍历，例如：


xxxxxxxxxx
procedure pack01(N, V, Costs, Values)
# output: max value we can gain

F[0...V] <- 0

for i <- 1 to N
    for v <- V to Costs[i]
        F[v] = max{ F[v], F[v - Costs[i]] + Values[i] }

return F[V];

问题变种：值得注意的是，这里并没有要求背包完全装满。如果要求背包必须恰好装满，应该怎么改？

F $F[0] = 0$ $F[1...V]=-\infty$ ，就相当指定了这个背包最终状态只能空间为 0；

$i$ $i$ $-\infty$ ；

$i$ $V$ $\max\{V-\sum\limits_i^NW_i,\space C_i\}$ 就行；

6.3.2 完全背包问题

题干仍然不变，但在完全背包的假设下，我们有前提： $[0,+\infty)$ 个。

思路一：

$i$ $\lfloor\dfrac{V}{C_i}\rfloor$ 件；

即：

F [i, v] = max {F [i - 1, v - k C_{i}] + k W_{i} | 0 \leq k C_{i} \leq v}

$O(NV\sum\limits_i\dfrac{V}{C_i})$ $O(NV)$ ，我们也不得不想办法优化了。

注意到一个引理：

在完全背包的前提下 $C_i\gt C_j$ $W_i\lt W_j$ $i$ $j$ 纳入考虑范围。

$i,j$ 两个物品且背包不满。

这个引理可以完成常数时间的优化：

$V$ 的物品；
找出所有 cost 相同但 value 最大的物品，作为这个 cost 下的唯一选择（不再考虑剩下的物品）；

$O(V+N)$ 时间；

最终我们需要落实解决并优化这个问题，可以把它规约到 01 背包问题上：

$i$ $\lfloor\dfrac{V}{C_i}\rfloor$ 个 cost 和 value 一样的物品。这样做没有降低上述的时间复杂度，但是带给我们思路：把一类物品拆成多件只能选 1 个或者不选的物品；

现在我们对拆分的过程优化一下：

$i$ $C_i2^k$ $W_i2^k$ $k$ $C_i2^k\le V$ 的非负整数；

$i$ $O(\log\lfloor\dfrac{V}{C_i}\rfloor)$ 时间内讨论出。

$O(N\sum\limits_i\log\dfrac{V}{C_i})$ ；

思路二：

还有一种思路：重写状态转移方程。注意到一个物品可以选不止一次，因此新的状态转移方程是：

F [i, v] = max {F [i - 1, v], F [i, v - C_{i}] + W_{i}}

$i$ $F[i,v-C_i]+W_i$ $F[i-1,v-C_i]+W_i$ $i$ $i-1$ $i$ 本身转移就行；

$i$ $v-C_i$ $v$ 的时候，不需要像 01 背包一样倒序了（不如说倒序现在是错的了）！顺序就能解决问题。

$O(NV)$ ；

6.3.3 多重背包问题

题干仍然不变，但在完全背包的假设下，我们有前提： $[0,M_i]$ 个。

$\lfloor\dfrac{V}{C_i}\rfloor$ $M_i$ 。

这个时候我们只有一种思路：

F [i, v] = max {F [i - 1, v - k C_{i}] + k W_{i} | 0 \leq k \leq M_{i}}

$k$ $F[v]$ $i$ 轮了）比较就行。

$O(V\sum\limits_i\log M_i)$ $M_i$ 不定），如下：


xxxxxxxxxx
procedure MultiplePack(F, C, W, M):

# 对每个物品而言，存在个数 M 总是比容量可观，
# 因此 M 不是限制，直接转换成完全背包
if C * M >= V
    CompletePack(F, C, W)
    return
# 将 M[i] 个物品拆成系数 1, 2, 2^2, ..., M[i] - 2^k + 1 的 k 个不同的物品
# 这 k 个物品作为分别作为 系数*价值、系数*cost 的 01-物品 来计算 01 背包问题
k <- 1
while k < M
    Pack01(k * C, k * W)
    M <- M − k
    k <- 2k
Pack01(C * M, W * M)

我们还可以结合在完全背包中介绍过的常数时间优化，来应对这个问题。

$O(NV)$ 时间的解决方案。

拓展一下：

$O(NV)$ 的解决方案了：

$F[i,v]$ $i$ $v$ $i$ 填满 $v$ $i$ $0\le F[i,v]\le M_i$ 才是可行的状态。这样就有伪代码：


xxxxxxxxxx
procedure multiKnapsackFeasible(N, V, Costs):
# output: F[N][0...V]

F[0, 1...V] <- -1   # 不放东西是解决不了问题的
F[0, 0] <- 0        # 除非容量是 0

for i <- 1 to N
    # 对第 i 个物品
    # 讨论各种背包容量
    for j <- 0 to V
        # 如果当前容量下，用前 i - 1 件物品不能恰好填满，则前 i 件也彻底没救
        # 如果前 i - 1 件可以，先把所有第 i 件物品全部放进去（可能溢出，后面判断）
        if F[i - 1][j] >= 0
            F[i][j] = M[i]
        else
            F[i][j] = -1
    # 前 i - 1 件物品放完后，剩下空间足够放第 i 件物品的话，就用状态转移看看第 i 件物品放几个
    for j <- 0 to V - Costs[i]
        if F[i][j] > 0
            F[i][j + Costs[i]] <- max{ F[i][j + Costs[i]], F[i][j] - 1 }

6.3.4 问题变种：Optimal Solution for Coins Charging

现在我们再来看上一章用贪婪算法解决不了的 “硬币找零” 问题，发现其实它就是另一种形式的背包问题：

硬币就是这里的 “物品”；
要凑的总面值就是背包的容量；
硬币面值就是 cost；
$F$ 单元格的含义就是硬币数量）；

现在硬币找零，就是一个 “要求将物品恰好填满背包、并且价值最小（不是最大）” 的完全背包问题。

直接写出状态转移方程：

F [i, v] = min {F [i - 1, v], F [i, v - C_{i}] + 1}

好，问题解决。我们只需要注意：

同理可以只用一维列表解决这个问题；
$F[0]=0$ $F[\ldots]=+\infty$ $-\infty$ ）希望读者举一反三；

具体选取的方案可以在每层循环决定时记录在额外的数组中（如果需要的话），不影响时间和空间复杂度。

如果每种硬币数量有限，那么就是需要恰好填满的“最少”多重背包问题。这里不再赘述。

6.4 最长子序列问题 II

6.4.1 最长公共子序列

$a_1,a_2,\ldots,a_m$ $b_1,b_2,\ldots,b_n$ ，求出它们最长的公共子序列（不要求连续）。

这个问题其实就是之前编辑距离的特例。我们同样引入 “匹配距离” 的说法：

$M[i,j]$ $a_1\sim a_i$ $b_1\sim b_j$ 间公共的长度（和编辑距离 “修改多少次后相同” 不同）；
$M[0,j]=M[i,0]=0$ ）；
$M[i,j]=\max\{M[i,j-1],\space M[i-1,j],\space M[i-1,j-1]+\text{same}(i,j)\}$ ；
$M[i,j]$ $M[i,j-1]$ $M[i-1,j]$ $M[i-1,j-1]$ $i,j$ 二者单独减 1 会不会对最长公共子序列产生影响，所以取最大。
$\text{same}(i,j)$ $M[i,j-1]$ $M[i-1,j]$ 中。也就是说：
$\begin{matrix} M [i, j] = {\begin{aligned} 0, i = 0 or j = 0 \\ M [i - 1, j - 1] + 1, a [i] = a [j] \\ max {M [i, j - 1], M [i - 1, j]}, otherwise \end{aligned} \end{matrix}$

$M[m,n]$ 中；

6.4.2 最长公共子串

$a_1,a_2,\ldots,a_m$ $b_1,b_2,\ldots,b_n$ ，求出它们最长的公共子串，要求子串是连续的。

就是 “最长公共子序列” 的特殊情况：

$\text{same}(i,j)=0$ $M[i,j]$ 直接置为 0 即可。

并且最长公共子串的最优解在表的任意位置，需要遍历得到。

当然，上述只是最基础的方案，你能在网上/论文里找到更快的算法，不过它们大多数都是基于这个算法改进得到的。

6.4.3 Quiz: 最大连续子序列和

$\mathbf{Z}$ $a_1,a_2,\ldots,a_n$ ，请问：

（复习）考虑使用分治法的时间复杂度是多少？
$O(n)$ 合并），因此：
$T(n)=2T(\dfrac{n}{2})+O(n)$ $a=b=2,d=1$ $T(n)=O(n^d\log n)=O(n\log n)$ ；
如何尽快得到最大的连续子序列和？
$O(n)$ （要读入一个序列至少这个时间）；
$F[i]$ 表示 $a_i$ 结尾的最长子序列的和；
$F[i]=\max\{F[i-1]+a_i,\space a_i\}$ $F[0]=a_0$ ）填表，最后收集全表最大值（答案可能分布整个表中）。
$a_i$ 结尾”？
$a_i$ 开头也行，但讨论顺序是从后向前，不符合人们的一般认知模式。

DP 填表 General Method：
DP 填表，决定表格的维数和含义；
出口是什么？（最容易的 entries）；
填表的顺序是将大问题拆解为小问题的思路；
最优解在表的什么部分；

6.5 3-Partition Problem

${a_1,a_2,\ldots,a_n}$ $I,J,K$ ，使得：

\sum_{i \in I} a_{i} = \sum_{j \in J} a_{j} = \sum_{k \in K} a_{k} = \frac{1}{3} \sum_{m = 1}^{n} a_{m}

$F[i,x,y,z]$ $i$ $x,y,z$ $i$ $x,y,z$ 的分法分为 3 个集合。

$F[i,x,y,z]=F[i-1,x-a_i,y,z]\or F[i-1,x,y-a_i,z]\or F[i-1,x,y,z-a_i]$ ；

$F[1,a_1,0,0]=\text{True},\space F[1,0,a_1,0]=\text{True},\space F[1,0,0,a_1]=\text{True}$ ；

$F[n,\dfrac{S}{3},\dfrac{S}{3},\dfrac{S}{3}]$ $S=\sum\limits_{m=1}^na_m$ ；

6.6 跳石子

在一条河上有一座独木桥，长度为 L，上面分布着一些石子，为了简单起见，我们假设桥为 0-L 的一段线段，而石子都分布在整数坐标上，也就是有一个函数 stone(x)，表示在坐标 x 上是否有石子，比如 stone(0)= 1 表示在桥头有一个石子，stone(2) = 0 表示在坐标为 2的位置没有石子。现在有一个小朋友站在桥头的位置想要过桥（站在桥尾或者跨过桥尾均为过了桥），但他不想踩到石子，他每跨出一步的步长是 [S,T] 区间中的任何整数（包括 S 和 T）。设计算法求小朋友要过河，必须踩到的最少的石子数。

$F[i]$ $i$ 的位置上时踩到的最少石子数。因此有状态转移方程：

\begin{matrix} F [i] = {\begin{aligned} s t o n e (0), i = 0 \\ s t o n e (i) + min {F [i - S . . . i - T]}, otherwise \end{aligned} \end{matrix}

$O((T-S)n)$ ；

6.7 Shortest Reliable Path (Lite) & Revisit Bellman-Ford Algorithm

在网络拓扑图中，如果用边长表示传输时延，并且需要考虑到每一跳的丢包问题，因此需要尽可能避免边数过大。

$G$ $s,t$ $k$ 条边。

$s$ $D[v,i]$ $v$ $i$ 条边的最短路径长。

$D[v,0]=\infty,\space D[s,i]=0$ ；其中状态转移方程：

D [x, i] = min_{(x, y) \in E} {D [y, i - 1] + l (x, y)}

$\min\limits_i\{D[t,i]\}$ $k$ $i=k$ 的一列）。

$O(|V||E|)$ ；

$O(|V|^2|E|)$ $O(|V|^3)$ ，如何选择取决于图的疏密。

6.8 Revisit Shortest Paths Problem: Floyd-Warshall Algorithm

$G$ $V=\{1,2,\ldots,n\}$ $D[i,j,k]$ $i$ $j$ $i,j$ $k$ $\{1,2,\ldots,k\}$ ）的最短路的长度。

$D[i,j,0]=l(i,j)$ ；状态转移方程如下：

D [i, j, k] = min {D [i, j, k - 1], D [i, k, k - 1] + D [k, j, k - 1]}

$i$ $j$ $k$ 个结点的最短路” 的前提下，分为两类情况：
$i$ $j$ $k$ $k-1$ $k-1$ 的表格中；
$k$ $k$ $k$ $k$ 为终点；

$u$ $v$ $\min\limits_{w}D[u,v,w]$ ；

6.9 Traveling Salesman Problem (TSP)

$G$ $s$ 哈密顿回路 $H$ 回路），并且长度最小。

一般讨论完全图。因为如果两个城市间不存在路径，则添加一条远大于其余边权的边，这样不影响计算最优回路；

$G$ 中最短的 H 回路。

$s$ $(n-1)!$ $O(n!)$ ；

$V=\{1,2,\ldots,n\}$ $1$ $S\subseteq V$ $S$ $\forall j\in S$ $D[S,j]$ $S$ $G$ $j$ 的初级回路的最短长度”。

$\forall j\neq1,j\in S$ ，有状态转移方程：

D [S, j] = min_{i \in S, i \neq j} {D [S ∖ {j}, i] + l (i, j)}

$S$ $j$ $j$ $i$ $j$ 的情况。这个 “子路径最短性” 我们在 Dijkstra Algorithm 证明时已经阐述过了。

$S$ $2^n$ $O(2^n)$ $j$ $O(n)$ $i$ $O(n)$ $O(n^22^n)$ ；

$S=\{1\},\space D[S,1]=0$ $|S|\gt1,\space D[S,1]=\infty$ ；

可惜的是 TSP 问题即便使用动态规划也无法在多项式时间内解决。它是个 NP Complete 问题（因为等价于求子集问题）。

6.10 Independent Sets in Trees

$G=(V,E)$ $S\subseteq V$ $S$ 内的所有顶点两两不相连。

这个问题也是一个 NP Complete 问题（也和集合的子集数量有关）。

$G$ 是一棵树，那么可以用动态规划在线性时间内解决。

$I(u)$ $u$ 为根所在的子树最大独立集的大小。那么有状态转移方程：

I (u) = max {1 + \sum_{grandchildren w of u} I (w), \sum_{children w of u} I (w)}

解释一下，树中的两个结点不相连的情况很多，但是如果我们从共同的根结点开始看，那么就只需要讨论两类情况：

树根与孙子结点，它们俩一定可以在一个独立集中（+1），可以继续考虑以孙子结点为根的子树的独立集数量；
树根与儿子结点，它们俩一定不能在一个独立集中，因此直接讨论以儿子结点为根的子树独立集数量；

$O(n)$ $n$ 为结点个数。

Chapter 7. Linear Programming

7.1 Definitions

定义：给定一组变量，要求它们的一组取值使得：

满足约束这组变量的等式和不等式；
最大化或最小化给定的线性目标函数；

举个例子：

\begin{aligned} max & x_{1} + 6 x_{2} \\ x_{1} & \leq 200 \\ x_{2} & \leq 300 \\ x_{1} + x_{2} & \leq 400 \\ x_{1}, x_{2} & \geq 0 \end{aligned}

对于两个变量：

线性不等式约束组成二维空间的半平面；
线性等式约束组成二维空间的一条直线；
所有线性约束可能形成一个凸多边形，这是可行空间（feasible space）；如果不能形成可行空间，称约束为 infeasible；
$f(x)=c$ $c$ 使得直线上下平移；
$c_{\min},c_{\max}$ 之一可能满足下述任一情况：
1. 可行空间是 infeasible 的；
2. 可行空间过大，我们称这是 unbounded 的；
3. $c$ 对应的直线落在多边形的某个顶点上；此时有唯一解；
4. $c$ 对应的直线落在多边形的某条边上，此时有无穷多解（线性解集）；

对于三个变量：

线性不等式约束组成三维空间的半空间；
线性等式约束组成三维空间的一条直线；
所有线性约束可能形成一个凸多面体；

于是更一般的形式上，我们可以定义线性规划的规范形式（Canonical Form）：

\begin{aligned} maximize & c^{T} x \\ subject to & a_{i}^{T} x & \leq b_{i}, i \in [1, m] \\ x_{j} & \geq 0, j \in [1, n] \end{aligned}

松弛型（Slack Form）：

\begin{aligned} min & c^{T} x \\ a_{i}^{T} x + b_{i}^{T} s & = b_{i} \\ x_{j}, s_{j} & \geq 0 \end{aligned}

在 Computer Algebra System 中非常有用。

所有线性规划问题都能通过以下方法转换为规范型或松弛型：

$c^Tx$ $-c^Tx$ ；
$\ge$ 符号可以通过两边同乘以 -1 改变；
$a_i^Tx\le b_i$ 可以通过引入松弛变量（slack variable）来变为等式；
$x_1\le200,x_2\le300$ $x_1-s_1=200,x_2-s_2=300,s_1,s_2\ge0$ ；
$a_i^Tx=b_i$ $a_i^Tx\le b_i$ 且 $-a_i^Tx\le b_i$ ；
$x_j^+$ $x_j^-$ $x_j=x_j^+-x_j^-$ $x_j^+\ge0$ $x_j^-\ge0$ ；

例如：

\begin{aligned} minimize & 3 x_{1} + x_{2} \\ subject to & x_{1} & > x_{2} + 5, \\ x_{1} + 3 x_{2} & = 10 \end{aligned}

可以被转换为：

\begin{aligned} maximize & - 3 x_{1} - x_{2} \\ subject to & - x_{1} + x_{2} & < - 5, \\ x_{1} + 3 x_{2} & \leq 10 \\ - x_{1} - 3 x_{2} & \leq 10 \end{aligned}

解决上述线性规划问题的算法之一就是 simplex（单纯形法），它描述：

从可行空间代表的凸多边形的任意一个顶点出发，按任意方向遍历凸多边形的相邻顶点，找到使 objective function 的局部最优值（没有任何相邻结点能使得 objective function 的取值更优），即为线性规划的解。

但实践上有几个问题：

为什么局部最优解是全局最优解？
Answer: By simple geometry. Since all the vertex’s neighbors lie below the line, the rest of the feasible polygon must also lie below this line.
如何得到可行空间的顶点？
如何得到顶点的相邻顶点？如果退化造成死循环又该怎么办？

我们将在讨论完 “对偶问题” 的概念后再回来解决。

另一个算法是椭球法，由苏联科学家发现。我们这里不作详细描述，只需要知道它是多项式时间复杂度的算法即可。

还有一个算法是内点法，也是时间复杂度。

7.3 Integer Linear Programming

整数规划并不是说直接可以通过一般线性规划直接得到的，因为解可能是小数，仅仅做舍入运算是不一定能得到最优解的（舍入可能造成偏离目标，但有可能其他原先不是最优的点在舍入后最优了），可能是近似解。

整数规划就是一种 NP Problem，除非使用普通线性规划的解恰好是整数，否则不能很快地求出最优解。

常见方法有剪枝、动归等等。我们后面讨论。

7.4 Dual Program

同样考虑这个问题：

\begin{aligned} max & x_{1} + 6 x_{2} \\ x_{1} & \leq 200 \\ x_{2} & \leq 300 \\ x_{1} + x_{2} & \leq 400 \\ x_{1}, x_{2} & \geq 0 \end{aligned}

$(x_1,x_2)=(100,300)$ ，目标最大 1900？

$x_1+6x_2\le1900$ ），这个最紧约束一定是能达到的最优值。

因此我们进行配凑：

\begin{aligned} y_{1} & x_{1} & \leq 200 \\ y_{2} & x_{2} & \leq 300 \\ y_{3} & x_{1} + x_{2} & \leq 400 \end{aligned}

$(y_1+y_3)x_1+(y_2+y_3)x_2\le200y_1+300y_2+400y_3$

$200y_1+300y_2+400y_3$ 能取得的最小值（因为需要 “最紧约束”），一定是原问题的最大值。

也就是说，原问题转换为了：

\begin{aligned} min & 200 y_{1} + 300 y_{2} + 400 y_{3} \\ y_{1} + y_{3} & \geq 1 \\ y_{2} + y_{3} & \geq 6 \\ y_{1}, y_{2}, y_{3} & \geq 0 \end{aligned}

我们总结一下转换的方法：

$\min$ $\max$ ；
原问题目标函数中的常数直接挪到对偶问题的目标函数中；
$c$ $c^Tx$ $b$ （约束条件的右边项系数）向量互换；
原问题变量和对偶问题的约束条件互换：
- $\ge0$ $\ge c_i$ （注意，不是反号！助记：原来约束就要反抗、原来不是约束就保守）；
- $\le0$ $\le c_i$ ；
- $=c_i$ ；
原问题约束条件和对偶问题的变量互换：
- $\le b_i$ $\ge0$ ；
- $\ge b_i$ $\le0$ ；
- $=b_i$ ，对偶问题变量无限制；

另外，这种对偶问题还有 Complementary Slackness（互补松弛）来描述这种 “相互为最紧约束” 的性质：

$P$ $x^{*}$ $D$ $y^{*}$ ：

$x_i^*\gt0$ $y_i^*$ 一定是不等式约束取等时获得；
$x_i^*=0$ $y_i^*$ 一定不是约束取等时获得；
$y_i^*\gt0$ $x_i^*$ 一定是不等式约束取等时获得；
$y_i^*=0$ $x_i^*$ 一定不是约束取等是获得；

$(x_1,x_2)=(100, 300)$ $(y_1,y_2,y_3)=(0,5,1)$ 符合上述互补松弛条件：

$x_1^*,x_2^*\gt0$ $y_1+y_3\ge1$ $y_2+y_3\ge6$ 这两个约束条件取等得到；
$y_1^*=0$ $x_1\le200$ 取等得到；
$y_2^*,y_3^*\gt0$ $x_2\le300$ $x_1+x_2\le400$ 这两个约束条件取等得到；

7.4 Application: Shortest Path

$G=(V,E)$ $w:E\rightarrow Q_+$ $s$ $t$ $s$ $t$ 的最短路径权值和。

我们可以用线性规划表示这个问题！

\begin{aligned} max d_{t} \\ d_{v} & \leq d_{u} + w (u, v), (u, v) \in E \\ d_{s} & = 0 \\ d_{i} & \geq 0, i \in V \end{aligned}

$d_x$ $x$ $s$ $d_v\le d_u+w(u,v)$ 应该这么理解：

$s$ $d_s=0$ $t$ $d_t$ $\max d_t$ ），率先被拉直的边的组合就是最短路。

$(u,v)$ $d_v=d_u+w(u,v)$ $d_v\lt d_u+w(u,v)$ ；

$\text{dist}(v)\gt\text{dist}(u)+l(u,v)$ $\text{dist}(v)$ $d_x$ $x$ 真实最短路径长）的约束关系。

这恰好对应该约束条件紧绷（取等）的状态，我们可以从数学角度证明这点。

再看另一个角度：

$C_S=\{S\subseteq V|s\in S,t\not\in S\}$ $G=(V,E)$ $s-t$ 间的所有割集。

$s$ $t$ 间的最短路，转换成整数规划问题：

\begin{aligned} min & \sum_{e \in E} w_{e} x_{e} \\ \sum_{e \in δ (S)} x_{e} & \geq 1, S \in C_{S} \\ x_{e} & \in {0, 1}, e \in E \end{aligned}

$\delta(S)$ $S$ $S$ $S$ 割的边的集合）。

$s$ $t$ $s$ $t$ 是连通的），并且让这些边权和最小。

$x_e$ $[0,1]$ $x_e$ $x_e$ $x\%$ $(1-x)\%$ $x$ 一定是任意的，否则不满足条件。这种情况解所代表的超直线一定平行于可行域边缘超平面，那么取一个整数顶点也是最优解。

$x_e$ $x_e\ge0$ $e$ $\min$ ，而且是正权。

我们注意到新问题的对偶问题：

\begin{aligned} max & \sum_{c \in C_{S}} y_{c} \\ \sum_{c \in C_{S}, e \in δ (c)} y_{c} & \leq w_{e}, e \in E \\ y_{c} & \geq 0, c \in C_{S} \end{aligned}

$y$ $C_S$ 个）；

$c$ $s$ $t$ $y_c$ $c$ $s$ $t$ $e$ $s$ $t$ $e$ 的护城河总长度。

7.5 Simplex Algorithm

7.5.1 算法内容

$v$ $v^\prime$ $v=v^\prime$ ，重复至没有邻居更好（局部最优），就一定是全局最优解；

我们定义单纯形：

$S$ $S$ 中所有不等式同时取等（紧绷且恰好可行），则这个点就是可行域的一个顶点；
$n$ 个不等式确定）；
$n-1$ 个共同的不等式。

对每一次迭代，Simplex 需要：

check 当前结点间是不是 optimal 的点（要比较所有邻居，不好做）；
确定个下一步需要到达的点（用不等式找顶点，不好找）；

我们知道，如果当前顶点是原点，上面两个操作会非常简单。因此我们可以每轮迭代都进行一次坐标变换，把下一次要处理的点变成原点。

为什么顶点是原点就简单？

首先 task 1 判断是否为最优点会比较简单：

$x=(x_1,x_2,\ldots,x_n)$ ）：

\begin{matrix} max & c^{T} x \\ A x & \leq b \\ x & \geq 0 \end{matrix}

$x\ge0$ $n$ 个不等式的取等（紧绷）且在可行域内，因此原点是顶点。

$x^*=(x_1^*,x_2^*,\ldots,x_n^*)=(0,0,\ldots,0)$ $\forall i,\space c_i\le0$ ；

$c_i\gt0$ $x_i\gt0$ 能取到更优的值；

其次 task 2 判断下一个需要到达的点也会比较简单：

$c_i\gt0$ $x_i$ $x_j$ $x_i$ $x_i\ge0$ $Ax\le b$ $A_kx\le b_k$ ，

$\{x\ge0|x\}\backslash\{x_i\ge0\}\cup\{A_k x\le b_k\}$ $(0,0,\ldots,\Delta x_i,0,\ldots,0)$ $n$ 个不等式紧绷的、且在可行域的解。因此这个点就是下一个可以去的顶点。

$y_j=x_j,\space j\neq i$ $y_i=b_k-A_kx$ $n$ $y$ 即可变换坐标系。

7.5.2 Corner Cases

考虑新的情况，如果原点不是顶点怎么办？这个时候说明变量不全是大于等于 0 的（原点可能不在可行域内）。我们只要转为规范型就行了！

$-1$ ）；

然后，我们构造一个新的线性规划：

$m$ $z_1,z_2,\ldots,z_m$ $m$ 为等式数量）；
$z_i$ $i$ 等式左边；
$\min z_1+z_2+\cdots+z_m$ ；

$z_i=b_i$ ，且其他变量都是 0 可以作为起始顶点很好找。并且如果：

$z_1=z_2=\cdots=z_m=0$ 是新线性规划的最优解，此时其他变量的取值也是原线性规划的可行的起始顶点，于是我们可以用这个顶点来运行单纯形法了！
$z_1=z_2=\cdots=z_m=0$ 不是新线性规划的最优解，则说明原线性规划的等式不能同时取得，原线性规划无解。

再考虑一个可能会使单纯形法失效的情况：退化。也就是说一个顶点可能由多个超平面相交得到，多于确定一个点所需的个数。

以 3 个变量的退化的线性规划为例，可能一个顶点会满足 4 个不等式，这会导致无论选哪三个约束条件并松弛另外一个，都会超出可行域（也就是当前顶点的所有邻居和这个点一样好），进而造成死循环。

破局的方法是，向约束条件的常数添加一个极小的扰动（加或减 0.00001），这不会对最优解的获得造成影响，但能够区分各个约束条件，以跳出这个怪圈。

另外，单纯形法能应对 unbounded 吗？可以，只要出现一种情况：在松弛一个不等式时，无论如何都碰不到下一个不等式取等了。这个应对方法是设定一个最大/最小阈值，松弛到这个值还找不到就算 unbounded；

7.5.3 运行时间

$n$ $m$ $n$ 个变量大于等于 0 的条件），那么给定一个顶点有多少邻居？

$m+n$ $u$ $n-1$ $n$ 个不等式同时取等组成一个顶点。

$n$ $m$ $m\cdot n$ ；

$O((m+n)n)$ $n$ $y$ $x$ 关系式代入每个不等式中，实际是操作矩阵）；

$C_{m+n}^n$ ，意味着我们最多进行这么多轮遍历。

$O(n(m+n)C_{m+n}^n)$ ，这是指数时间复杂度！

不过线性规划是多项式时间内能解决的问题，因为椭球法、内点法是多项式时间复杂度的。

但好笑的是，单纯形算法虽然是指数级算法，但是实践中要比椭球法、内点法在大部分情况下更快。

研究人员对这个问题使用了 Smoothed Analysis，获得了2008 年的哥德尔奖。研究证明了单纯形法只有在每一轮都取到一个特定的特殊的顶点时才会 fallback 到指数时间，否则有一点扰动就极大概率是多项式时间能完成的。

7.6 最大流与最小割

最大流问题：对于一个有向图，边权为该边的流量限阈。其中图中除了源点、汇点外，流体无法存储、无法产生。

$s$ $t$ 输送尽可能多的流体。

$c_e$ $f_e$ 则：

$0\le f_e\le c_e,\space e\in E$ ;
$\sum\limits_{(w,u)\in E}f_{wu}=\sum\limits_{(u,z)\in E}f_{uz},\space u\not\in\{s,t\}$ ；
$s$ $S=\sum\limits_{(s,u)\in E}f_{su}$ ；

$s,t$ 的特殊性，便于在代数层面操作。

$(t,s)$ $+\infty$ ，这样可以让每个顶点流入都等于流出。

$\le$ 为规范型：

$0\le f_e\le c_e,\space e\in E$ ;
$\sum\limits_{(w,u)\in E}f_{wu}-\sum\limits_{(u,z)\in E}f_{uz}\le0$ （每两个边间小于等于，最终连起来就等价于等于）；
$s$ $S=f_{ts}$ ；

在线性规划的思路中，我们怎么做？

$f_e=0$ $f_i$ ，由于约束限制，最终会同时提升一条路径上的流量（相当于找到了一条路径），最终达到这条路径整体的最大容量。

于是，在每次迭代中，找到的一条路径（不小于前一条路径的流量，且这条路径后一个边不能小于前一条边），因此该路径的每一条边都满足下面两种情况之一：

$(u,v)$ 包含在最初网络中，并且未达到最大流量；
$(v,u)$ 在最初网络中，并且存在一定流量；

$(u,v)$ $c_{uv}-f_{uv}$ 的流量；

$f_{vu}$ $(v,u)$ 后最大的承载量就会取消原先选中的流量）；

$G^f$ ，用来描述选中当前路径后，网络中的 “增加流量的机会”：

\begin{matrix} c^{f} = {\begin{aligned} c_{u v} - f_{u v}, if (u, v) \in E, f_{u v} < c_{u v} \\ f_{v u}, if (v, u) \in E, f_{v u} > 0 \end{aligned} \end{matrix}

这样，我们模仿单纯形法，获得计算最大流的算法：

$G^f$ $G^f$ $s$ $t$ 的能提升当前流量的路径，然后将在流网络中插入这个路径（注意插入的路径的各边权重都等于该路径的最大流量）。

问题：给定一个有向图（含多个源点和汇点），判断它是否是流通的（circulate）；

$s$ $t$ $s$ 指向各个源点

应用：二部图匹配。

$s$ $t$ 被二部图中另一部分的所有结点指向。让每条边的权重（容量）均为 1；

则原问题等价于 “在新的图中是否有最大流的流量等于最终配对数”。

注：最大流问题的整数性。

如果所有边的容量为整数，则算法得到最大流规模也是整数。因为算法每次迭代都增加的是一个整数值的流量。

如果边的容量不是整数（例如实数），那么最大流的很多算法没法使用，例如上面的剩余网络算法可能无法终止。

Chapter 8. NP Problems

本章几乎全部是概念。

首先，问题和算法是两个概念。

有效问题和难问题：有没有一种问题，存在指数级别的 search space，且无论如何都无法找到多项式时间的算法？

例如最小生成树（Kruskal/Prim）算法能在指数级 search space 中使用接近线性时间的复杂度完成任务。这就是一个简单问题（P）；

$x_i$ $\overline{x_i}$ $\neg x_i\rightarrow x_j$ $(\overline{x_i},\space x_j)$ $x_i$ $\overline{x_i}$ 在一个强连通部件中。如果存在则冲突（不可满足），否则可以找到满足的赋值；

$N\ge3$ 和 3-SAT 问题的复杂度是一样的）

SAT 问题就是典型的 search problem。我们现在定义两个概念：

$I$ ，例如 SAT 中定义问题的 boolean 运算式；
$S$ ，例如 SAT 中满足各个 clause 的一组赋值（如果无解，需要给出提示）；

$S$ $I$ 来确定正确性，也就是说：

$I,S$ $C$ $S$ $C(I,S)$ $O(|I|^n)$ （多项式时间可验证）；

$n$ $\dfrac{n(n-1)}{2}$ $b$ $b$ （没有就报告）？这就是把 optimization problem 转换成了一个 search problem；

理论上，我们认为 optimization problem 和 search problem 的相互转换不会改变时间复杂度，因为：

优化问题转判定问题：找到最优问题的解，判断是否满足判定问题条件；
判断问题转优化问题：通过二分法试探问题的最优解；

又因为判定问题和搜索问题可以通过图灵机进行等价，因此：优化问题、判定问题、搜索问题可以相互转换（一个问题就有 3 个版本）。

通常，判定问题用作判断问题的复杂度（参数复杂性）；优化问题版本通常用来求解近似算法；

$n-1$ 次最大流算法，在多项式时间内解决；

$\dfrac{n}{3}$ $b$ 条边）不能在多项式时间内解决（N-Coloring 问题规约到它）；

ZOE：一个线性方程组系数只能是 0/1，解的取值也只能是 0/1；它和整数规划一样，不存在多项式时间算法。

因此 3 维匹配问题可以转化为 ZOE 问题（一个匹配 triple 作为一个变量），所以 3D Matching 是不存在多项式时间算法的。

独立集问题（最大顶点子集互不相连）、顶点覆盖问题（所有边至少有一个顶点在当前顶点子集中）、团问题（最大顶点子集间两两有边）三者实际相互等价。

$G$ $\overline{G}$ ；
$G$ $S$ $V-S$ 是一个顶点覆盖问题的解；

（顶点覆盖是集合覆盖的子集？）

$a_1x_1+a_2x_2+\cdots+a_nx_n=W$ ；

NP：所有种类的 search problems。多项式时间内可验证的问题（判断标准）；

co-NP：NP 问题的补问题。一般认为 co-NP 和 NP 的交集包含 P；

$P\subseteq NP$ ）；

P 问题有一条性质：关于补问题是封闭的（P = co-P）；

为什么说只要解决一个 NP 问题，就能解决所有 NP 问题（Solve one and solve all）？

$A$ $B$ $A$ $B$ ，并且：

解决问题：将未知问题规约到已知问题（已知问题有一个算法，将未知问题用这个算法来解）；
证明问题：将已知问题规约到未知问题（证明未知问题难以已知问题）；
评估问题：将未知问题规约到已知问题（问题规约到更难的问题看看参照，不作为科学证明）；

NPH：NP Hard 问题，可能没法在多项式时间内验证的问题。

NPC：NP 完全问题，其他所有 NP 问题都能规约到它（因此 NPC 不简单于 NP）。

证明：如果 NP != co-NP，则 P != NP；

如何将 H 路径问题向 H 回路（顶点和边不重复的）规约？

$G$ $x$ $u,v$ $G^\prime$ 中运行 H 回路算法；

g: 如果有 H 回路，则删除这两条边，记为原问题的解（H 道路）；如果没有 H 回路，则原问题无解；

如何将 3-SAT 问题规约到独立集问题？

考虑任意一个 3-SAT：

$x$ $\overline{x}$ ）连接一条无向边；

$G$ $G$ 的独立集：

$x$ $\overline{x}$ 只能有一个真，

如何将 SAT 问题规约到 3-SAT 问题？

$(a_1\or a_2\or\cdots\or a_n)$ ，可以转换成若干个 3 个文字组成的子句的合取：

(a_{1} \lor a_{2} \lor y_{1}) \land (\overset{―}{y_{1}} \lor a_{3} \lor y_{2}) \land \dots \land (\overset{―}{y_{k - 2}} \lor a_{k} \lor y_{k - 1}) \land \dots \land (\overset{―}{y_{n - 3}} \lor a_{n - 1} \lor a_{n})

$a$ $y$ $\overline{y}$ $y_{k-2}$ $\overline{y_{k-1}}$ 对应的正出现；

这两个子句不完全等价，但有个性质：它们同可满足性；

$\Rightarrow$ $a_i$ 为真（左边的子句为真）：

$a_i$ $a_1$ $a_2$ $\overline{y}$ $y_j=0$ 式子即取真值；
$a_i$ $a_{n-1}$ $a_n$ $y$ $y_j=1$ 式子即取真值；
$a_i$ $2\lt i\lt n-1$ $(\overline{y_{i-2}}\or a_i\or y_{i-1})$ $y_1$ $y_{i-2}$ $\overline{y_{i-1}}$ $\overline{y_{n-3}}$ $y_1\sim y_{i-2}$ $y_{i-1}\sim y_{n-3}$ 为假，那么整体为真；

$\Leftarrow$ ；反证

进一步，3-SAT 即便再简化都是难问题！例如，我们让每个变量最多出现 3 次、每个文字最多出现 2 次；

如何将 H 回路问题规约到 TSP 问题（H 回路的权值和最小）？

考虑两个问题的不同（以便构造 input f）：

多了权值；
并且 TSP 一般考虑完全图的情况；

f：将 H 回路补上边使得它称为一个完全图（完全图一定存在 H 回路），但是旧的边权设置为 1，新补的边设置大于 1；

$n$ $n$ 为顶点数），则说明没有用到新补的边，因此原图存在 H 回路；反之不存在；

如何应对 NP 问题？

梯度下降

$S=V$ $O(|V|)$ ，每个顶点都有线性多个邻居；
- 可能获得的局部最优离整体最优很远：星形图如果意外删除中心结点？二部图删除了结点少的一边？
$O(n^2)$ $O(n^3)$ ，每轮 iteration 开销更大，但遇到局部最优不是整体最优的情况更少）；
graph partition：
Metropolis Algorithm：固定温度的退火算法；
- $e^{-\Delta E/kT}$ 的概率转移到邻居；
- 优点：每次 iteration 都有概率到全局最优（不会只看到局部最优）；
- 缺点：算法难以结束（不可能跳出局部最优的时候仍然“不愿意”收敛）；
Simulated Annealing：模拟退火算法；
- $T=T(i)$ ；
- 在 Metropolis Algorithm 的基础上保证算法能快速结束；

Hopfield Netural Network

$s_i$ ）；然后给边也赋权值；

我们定义 configuration：顶点状态的一个指派；

定义一个 good edge：该边如果负权，则顶点状态相同，正权则顶点状态相反；

也就是希望两个顶点边是负值顶点状态相同，边是正值顶点状态不同；

$\sum\limits_{v:e=(u,v)\in E}w_es_us_v\le0$ ；

定义一个 stable configuration：一个对顶点状态的指派，使得所有顶点都是 satisfied nodes；

我们对任意一个连通的无向图，希望找到一个 stable configuration；

这样我们发现，只要把 unsatisfied nodes 的状态 flip 后，至少当前的顶点会变成 satisfied node！

我们让这样的 flip 变换的 configuration 为一个邻居，就有 local search：

Algorithm Design

Chapter 0. Definitions

Chapter 1. Algorithms of Numbers

1.1 数字基本算数

1.1.1 加法

1.1.2 乘法 & 除法

1.2 模运算

1.2.1 ZN\mathbf{Z}_N 上的加法、乘法

1.2.2 ZN\mathbf{Z}_N 上的幂

1.2.3 Euclid's Greatest Common Divisor

1.2.4 Euclid GCD 算法的延伸

1.2.5 ZN\mathbf{Z}_N 上的乘法逆元

1.3 素性测试

1.3.1 Definitions

1.3.2 随机生成素数

1.4 密码学

1.4.1 对称加密

1.4.2 非对称加密

1.4.3 证书

Chapter 2. 分治算法

2.1 更快的乘法

2.2 更一般的分治递推分析

2.3 应用：比较排序的时间下界

2.4 应用：中位数算法再讨论

2.5 应用：矩阵乘法

2.6 应用：计数逆序

Chapter 3. The Algorithms using Fast Fourier Transform

3.1 Revisit Complex Number

3.2 Begin with The Production of Polynomials

Chapter 4. Graph

4.1 Revisit: DFS in Graph

4.2 无向图的连通分量

4.3 有向图的连通分量

4.4 有向无环图（DAG）

4.5 Revisit: 有向图强连通分量

4.6 BFS in Graph

4.7 正权图中两点间的单源最短路径

4.8 含负权无负环图中两点间的单源最短路径

补充：负环问题 & 最简最短路

4.9 含负权的 DAGs 中两点间的单源最短路径

Chapter 5. Greedy Algorithms

5.1 Minimal Spanning Tree (MST)

5.2 Set Cover（集合覆盖问题）

5.3 贪婪算法何时失效：Coins Charging

Chapter 6. 动态规划

6.1 最长子序列问题 I：最长递增子序列

6.2 编辑距离

6.3 背包问题

6.3.1 01-背包问题

6.3.2 完全背包问题

6.3.3 多重背包问题

6.3.4 问题变种：Optimal Solution for Coins Charging

6.4 最长子序列问题 II

6.4.1 最长公共子序列

6.4.2 最长公共子串

6.4.3 Quiz: 最大连续子序列和

6.5 3-Partition Problem

6.6 跳石子

6.7 Shortest Reliable Path (Lite) & Revisit Bellman-Ford Algorithm

6.8 Revisit Shortest Paths Problem: Floyd-Warshall Algorithm

6.9 Traveling Salesman Problem (TSP)

6.10 Independent Sets in Trees

Chapter 7. Linear Programming

7.1 Definitions

7.3 Integer Linear Programming

7.4 Dual Program

7.4 Application: Shortest Path

7.5 Simplex Algorithm

7.5.1 算法内容

7.5.2 Corner Cases

7.5.3 运行时间

7.6 最大流与最小割

Chapter 8. NP Problems

如何应对 NP 问题？

梯度下降

Hopfield Netural Network

$\mathbf{Z}_N$ 上的加法、乘法

$\mathbf{Z}_N$ 上的幂

$\mathbf{Z}_N$ 上的乘法逆元

6.3.1 `01`-背包问题