算法设计与分析

1. Introduction

1.1. Stirling 公式

𝑛! = \sqrt{2 𝜋 𝑛} {(\frac{𝑛}{𝑒})}^{𝑛} (1 + Θ (\frac{1}{𝑛}))

$\begin{matrix} 𝑛! = 𝑜 (𝑛^{𝑛}) \\ 𝑛! = 𝜔 (2^{𝑛}) \\ \log (𝑛!) = Θ (𝑛 \log (𝑛)) \end{matrix}$

1.2. 取整函数

⌊ \frac{⌊ \frac{𝑛}{𝑎} ⌋}{𝑏} ⌋ = ⌊ \frac{𝑛}{𝑎 𝑏} ⌋ ⌈ \frac{⌈ \frac{𝑛}{𝑎} ⌉}{𝑏} ⌉ = ⌈ \frac{𝑛}{𝑎 𝑏} ⌉

2. Algoritnm Basis

2.1. 序列求和

\sum_{𝑘 = 1}^{𝑛} \frac{1}{𝑘} = \log 𝑛 + 𝑂 (1)

\begin{matrix} \sum_{𝑡 = 1}^{𝑘} 𝑡 2^{𝑡 - 1} & = 2 (\sum_{𝑡 = 1}^{𝑘} 𝑡 2^{𝑡 - 1}) - \sum_{𝑡 = 1}^{𝑘} 𝑡 2^{𝑡 - 1} \\ = \sum_{𝑡 = 1}^{𝑘} 𝑡 2^{𝑡} - \sum_{𝑡 = 1}^{𝑘} 𝑡 2^{𝑡 - 1} \\ = 𝑘 2^{𝑘} - 1 + \sum_{𝑡 = 1}^{𝑘 - 1} (𝑡 2^{𝑡} - (𝑡 + 1) 2^{𝑡}) \\ = (𝑘 - 1) 2^{𝑘} + 1 \end{matrix}

2.2. 迭代法求解递推方程（汉诺塔问题为例）

def hanoi(A, C, n):

    if n == 1:

        move(A, C)

    else:

        hanoi(A, B, n-1)

        move(A, C)

        hanoi(B, C, n-1)

def hanoi(A, C, n):

    if n == 1:

        move(A, C)

    else:

        hanoi(A, B, n-1)

        move(A, C)

        hanoi(B, C, n-1)

\begin{matrix} 𝑇 (𝑛) & = 2 𝑇 (𝑛 - 1) + 1 \\ = 2 (2 𝑇 (𝑛 - 2) + 1) + 1 \\ ⋮ \\ = 2^{𝑛 - 1} 𝑇 (1) + 2^{𝑛 - 2} + \dots + 2 + 1 \\ = 2^{𝑛} - 1 \end{matrix}

2.3. 差消法化简递推方程（快排为例）

def qsort(arr, start, end):

    if end - start <= 1: return

    mid = split(arr, start, end)

    qsort(arr, start, mid)

    qsort(arr, mid+1, end)

def qsort(arr, start, end):

    if end - start <= 1: return

    mid = split(arr, start, end)

    qsort(arr, start, mid)

    qsort(arr, mid+1, end)

𝑇 (𝑛) = \frac{2}{𝑛} \sum_{𝑖 = 0}^{𝑛 - 1} 𝑇 (𝑖) + (𝑛 - 1)

\begin{matrix} 𝑛 𝑇 (𝑛) & = 2 \sum_{𝑖 = 0}^{𝑛 - 1} 𝑇 (𝑖) + 𝑛 (𝑛 - 1) \\ (𝑛 - 1) 𝑇 (𝑛 - 1) & = 2 \sum_{𝑖 = 0}^{𝑛 - 2} 𝑇 (𝑖) + (𝑛 - 1) (𝑛 - 2) \\ 𝑛 𝑇 (𝑛) - (𝑛 - 1) 𝑇 (𝑛 - 1) & = 2 𝑇 (𝑛 - 1) + 2 (𝑛 - 1) \\ 𝑛 𝑇 (𝑛) & = (𝑛 + 1) 𝑇 (𝑛 - 1) + 2 (𝑛 - 1) \\ \frac{𝑇 (𝑛)}{𝑛 + 1} & = \frac{𝑇 (𝑛 - 1)}{𝑛} + 2 \frac{𝑛 - 1}{𝑛 (𝑛 + 1)} \\ = Θ (\sum_{𝑘 = 1}^{𝑛} \frac{1}{𝑘}) = Θ (\log 𝑛) \end{matrix}

𝑇 (𝑛) = Θ (𝑛 \log 𝑛)

2.4. 主定理

𝑇 (𝑛) = 𝑎 𝑇 (\frac{𝑛}{𝑏}) + 𝑓 (𝑛)

若 $\exists 𝜀 > 0, 𝑓 (𝑛) = 𝑂 (𝑛^{\log_{𝑏} 𝑎 - 𝜀})$ 则
$𝑇 (𝑛) = Θ (𝑛^{\log_{𝑏} 𝑎})$
若 $𝑓 (𝑛) = Θ (𝑛^{\log_{𝑏} 𝑎})$ 则
$𝑇 (𝑛) = Θ (𝑛^{\log_{𝑏} 𝑎} \log 𝑛)$
若 $\exists 𝜀, 𝑓 (𝑛) = Ω (𝑛^{\log_{𝑏} 𝑎 + 𝜀})$ 且 $\exists 𝑐 < 1, \exists 𝑛_{0}, \forall 𝑛 \geq 𝑛_{0}, 𝑎 𝑓 (\frac{𝑛}{𝑏}) \leq 𝑐 𝑓 (𝑛)$ 则
$𝑇 (𝑛) = Θ (𝑓 (𝑛))$

不能使用主定理的例子 $𝑇 (𝑛) = 2 𝑇 (\frac{𝑛}{2}) + 𝑛 \log 𝑛$

𝑛^{\log_{2} 2} = 𝑛^{1}

∄ 𝜀 > 0 s.t. 𝑛 \log 𝑛 = Ω (𝑛^{1 + 𝜀})

3. Divide and Conquer

3.1. 分治算法改进：减少子问题数量

𝑇 (𝑛) = 4 𝑇 (\frac{𝑛}{2}) + 𝑂 (𝑛) \Rightarrow 𝑇 (𝑛) = 3 𝑇 (\frac{𝑛}{2}) + 𝑂 (𝑛)

3.2. 分治算法改进：增加预处理

作用是减少 $𝑓 (𝑛)$

4. Classic Divide and Conquer

4.1. 一般性质选择问题

5个一组分别排序，每个组的中位数的集合取中位数 $𝑚^{⋆}$ ，根据 $𝑚^{⋆}$ 划分子问题，根据子问题的规模大小与 $𝑘$ 的大小关系排除部分子问题

$𝑊 (𝑛) = 𝑊 (\frac{𝑛}{3}) + 𝑊 (\frac{2}{3} 𝑛) + 𝑂 (𝑛)$

$𝑊 (𝑛) = 𝑊 (\frac{𝑛}{5}) + 𝑊 (\frac{7}{10} 𝑛) + 𝑂 (𝑛)$

4.2. 卷积

𝑎 * 𝑏 = (\begin{matrix} 𝑐_{0} \\ 𝑐_{1} \\ ⋮ \\ 𝑐_{𝑘} \\ ⋮ \\ 𝑐_{𝑚 + 𝑛} \end{matrix}) = (\begin{matrix} 𝑎_{0} 𝑏_{0} \\ 𝑎_{0} 𝑏_{1} + 𝑎_{1} 𝑏_{0} \\ ⋮ \\ \sum_{𝑖 + 𝑗 = 𝑘} 𝑎_{𝑖} 𝑏_{𝑗} \\ ⋮ \\ 𝑎_{𝑚} 𝑏_{𝑛} \end{matrix})

4.3. 多项式系数

𝐴 (𝑥) = 𝑎_{0} + 𝑎_{1} 𝑥 + \dots 𝑎_{𝑚 - 1} 𝑥^{𝑚}

𝐵 (𝑥) = 𝑏_{0} + 𝑏_{1} 𝑥 + \dots 𝑏_{𝑛 - 1} 𝑥^{𝑛}

\begin{matrix} 𝐴 (𝑥) 𝐵 (𝑥) & = 𝑎_{0} 𝑏_{0} + (𝑎_{1} 𝑏_{0} + 𝑎_{0} 𝑏_{1}) 𝑥 + \dots + (𝑎_{𝑚 - 1} 𝑏_{𝑛 - 1}) 𝑥^{𝑚 + 𝑛} \\ = 𝑐_{0} + 𝑐_{1} 𝑥 + \dots 𝑐_{𝑚 + 𝑛 - 2} 𝑥^{𝑚 + 𝑛} \end{matrix}

where 𝑐 = 𝑎 * 𝑏

4.4. 分治法多项式求值

assume that $𝑚$ is odd

𝐴 (𝑥) = 𝑎_{0} + 𝑎_{1} 𝑥 + \dots 𝑎_{𝑚 - 1} 𝑥^{𝑚 - 1}

\begin{matrix} 𝐴 (𝑥) = 𝐴_{even} (𝑥^{2}) + 𝑥 𝐴_{odd} (𝑥^{2}) \\ where \\ 𝐴_{even} (𝑥) = 𝑎_{0} + 𝑎_{2} 𝑥 + \dots + 𝑎_{𝑚 - 2} 𝑥^{\frac{𝑚 - 2}{2}} \\ 𝐴_{odd} (𝑥) = 𝑎_{1} + 𝑎_{3} 𝑥 + \dots + 𝑎_{𝑚 - 1} 𝑥^{\frac{𝑚 - 2}{2}} \end{matrix}

\begin{matrix} 𝑇 (𝑛) = 2 𝑇 (\frac{𝑛}{2}) + 𝑂 (𝑛) \\ 𝑇 (𝑛) = 𝑂 (𝑛 \log 𝑛) \end{matrix}

4.5. FFT

求多项式 $𝐴 (𝑥)$ 和 $𝐵 (𝑥)$ 的乘积 $𝐶 (𝑥)$ 选择 $2 𝑛$ 个 $𝑥$ 的值（选择 $1$ 的 $2 𝑛$ 次根），求出 $𝐴 (𝑥_{𝑗})$ 和 $𝐵 (𝑥_{𝑗})$ 的值，再用求出 $𝐶 (𝑥_{𝑗}) = 𝐴 (𝑥_{𝑗}) 𝐵 (𝑥_{𝑗})$ ，最后多项式插值求出 $𝐶 (𝑥)$

对每个 $𝑥_{𝑗}$ 计算 $𝐴 (𝑥_{𝑗})$ 和 $𝐵 (𝑥_{𝑗})$ 的值 $𝑂 (𝑛 \log 𝑛)$
对每个 $𝑥_{𝑗}$ 计算 $𝐶 (𝑥_{𝑗})$ 的值 $𝑂 (𝑛)$
定义 $𝐷 (𝑥) = 𝐶 (𝑥_{0}) + 𝐶 (𝑥_{1}) 𝑥 + \dots + 𝐶 (𝑥_{2 𝑛 - 1}) 𝑥^{2 𝑛 - 1}$
计算 $𝐷 (𝑥_{𝑗})$ $𝑂 (𝑛 \log 𝑛)$
$2 𝑛 𝑐_{2 𝑛 - 𝑗} = 𝐷 (𝑥_{𝑗})$ $𝑂 (𝑛)$

𝑇 (𝑛) = 𝑂 (𝑛 \log 𝑛)

5. Dynamic Programming

5.1. 矩阵链相乘

另 $𝑑 [𝑖, 𝑗]$ 为 $𝑥_{𝑖} \cdot 𝑥_{𝑖 + 1} \cdot \dots \cdot 𝑥_{𝑗}$ 的最小开销

𝑑 [𝑖, 𝑗] = {\begin{matrix} 0 & if 𝑖 = 𝑗 \\ \min_{𝑖 \leq 𝑘 < 𝑗} (𝑑 [𝑖, 𝑘] + 𝑑 [𝑘 + 1, 𝑗] + 𝑝_{𝑖 - 1} 𝑝_{𝑘} 𝑝_{𝑗}) & otherwise \end{matrix}

5.2. 投资问题

$𝑥$ 元投资给 $𝑚$ 个项目，每个项目的收益为 $𝑓_{𝑖} (𝑥)$

dp [𝑥, 𝑘] = {\begin{matrix} 𝑓_{1} (𝑥) & if 𝑘 = 1 \\ \max_{𝑡 = 0, \dots, 𝑥} (dp [𝑥 - 𝑡, 𝑘 - 1] + 𝑓_{𝑘} (𝑡)) & otherwise \end{matrix}

5.3. 背包问题

$𝑛$ 种物品，可以拿多个，重量为 $𝑤_{𝑖}$ ，价值为 $𝑣_{𝑖}$ ，背包容量为 $𝑏$ ，求最大价值

𝑑 [𝑥, 𝑘] = {\begin{matrix} - \infty & if 𝑥 < 0 \\ 0 & if 𝑥 = 0 or 𝑘 = 0 \\ \max (𝑑 [𝑥 - 𝑤_{𝑘}, 𝑘] + 𝑣_{𝑘}, 𝑑 [𝑥, 𝑘 - 1]) & otherwise \end{matrix}

也可以写成投资问题那样，每一步都对拿几个进行迭代，但是时间复杂度更差

5.4. 最长公共子序列

给定 $𝑋 = (𝑥_{1}, 𝑥_{2}, \dots 𝑥_{𝑚})$ 和 $𝑌 = (𝑦_{1}, 𝑦_{2}, \dots, 𝑦_{𝑛})$

5.5. 最长上升子序列

给定 $𝑋 = (𝑥_{1}, 𝑥_{2}, \dots, 𝑥_{𝑛})$

令 $𝑑 [𝑖]$ 表示以 $𝑥_{𝑖}$ 结尾的最长上升子序列

𝑑 [𝑖] = \max_{\begin{matrix} 1 \leq 𝑗 < 𝑖 and \\ 𝑥_{𝑗} < 𝑥_{𝑖} \end{matrix}} 𝑑 [𝑗] + 1

(考虑到 $𝑑 [𝑗]$ 是递增的，也可以二分查找优化下)

6. Applications of DP

6.1. 图像压缩

给定 $𝑃 = (𝑝_{1} . 𝑝_{2}, \dots, 𝑝_{𝑛})$ ，对 $𝑃$ 进行分段，每个分段中每个数字占用的存储空间是 $𝑏 (分段中的最大值) + 11$ ，求占用空间最小的分段方式

令 $𝑑 [𝑖]$ 表示以 $𝑝_{𝑖}$ 为结尾的数据的最优分段占用

𝑑 [𝑖] = \min_{𝑗 \leq \max (𝑖, 255)} (𝑑 [𝑖 - 𝑗] + 𝑗 𝑏 (\max_{𝑖 - 𝑗 < 𝑘 \leq 𝑖} (𝑝_{𝑘})) + 11)

6.2. 最大字段和

给定 $𝐴 = (𝑎_{1}, 𝑎_{2}, \dots, 𝑎_{𝑛})$ ，求 $𝐴$ 的连续子序列的和的最大值

令 $𝑑 [𝑖]$ 表示以 $𝑎_{𝑖}$ 为结尾的子序列的和的最大值

𝑑 [𝑖] = \max (𝑑 [𝑖 - 1], 0) + 𝑎_{𝑖}

6.3. RNA二级结构预测

有点像矩阵链相乘，但是 $𝑘$ 的切分更复杂一点，这里 $𝑘$ 需要和 $𝑗$ 配对，再单独考虑 $𝑗$ 不会配对的情况

6.4. 编辑距离

给定 $𝑋 = (𝑥_{1}, 𝑥_{2}, \dots, 𝑥_{𝑚})$ 和 $𝑌 = (𝑦_{1}, 𝑦_{2}, \dots, 𝑦_{𝑛})$ ，对 $𝑋$ 进行插入，删除和替换操作，将 $𝑋$ 变为 $𝑌$ 的最少操作次数

𝑑 [𝑖, 𝑗] = {\begin{matrix} \max (𝑖, 𝑗) & if 𝑖 𝑗 = 0 \\ 𝑑 [𝑖 - 1, 𝑗 - 1] & if 𝑥_{𝑖} = 𝑦_{𝑗} \\ \max (𝑑 [𝑖, 𝑗 - 1], 𝑑 [𝑖 - 1, 𝑗], 𝑑 [𝑖 - 1, 𝑗 - 1]) + 1 & otherwise \end{matrix}

7. Greedy Algoritnm

7.1. 活动选择问题最优性证明

命题：在算法执行到第 $𝑘$ 步时，选择了 $𝑘$ 个活动，最优解 $𝐴$ 包含 $1, 𝑖_{2}, \dots, 𝑖_{𝑘}$

归纳基础

最优解A中包含

1

归纳步骤

已知最优解中包含 $1, 𝑖_{2}, \dots, 𝑖_{𝑘}$ ，证明最优解包含 $1, 𝑖_{2}, \dots, 𝑖_{𝑘}, 𝑖_{𝑘 + 1}$

另剩下的问题叫做 $𝑆^{'}$ ， $𝐵$ 为 $𝐴 - {1, 𝑖_{2}, \dots, 𝑖_{𝑘}}$
可以证明 $𝐵$ 是 $𝑆^{'}$ 的最优解，因为如果 $𝑆^{'}$ 存在更优的解， $𝐴$ 就不是最优解了因为 $𝐵$ 是 $𝑆^{'}$ 的最优解，所以 $𝑖_{𝑘 + 1} \in 𝐵$ ，所以最优解包含 $1, 𝑖_{2}, \dots, 𝑖_{𝑘}, 𝑖_{𝑘 + 1}$

7.2. 最优装载问题

0-1背包问题的特殊情况：价值都是1

证明最优性：去掉箱子1

7.3. 硬币找零问题

𝑣_{𝑘} + 𝛿 = 𝑝 𝑣_{𝑘 - 1}

𝑤_{𝑘} + 𝐺 (𝛿) \leq 𝑝 𝑤_{𝑘 - 1}

即使输入是 $𝑣_{𝑘 - 1}$ 的整数倍时，选择 $𝑣_{𝑘}$ 仍然要是最优的

8. Applications of Greedy Algoritnm

8.1. 哈夫曼算法证明

最小的两个 $𝑥, 𝑦$ 在一起
在一起之后可以等效成一个 $𝑧 = 𝑥 + 𝑦$

8.2. 最小生成树

Prime 算法: 初始化 $𝑆 = {1}$ ，不断选择 $𝑆$ 和 $𝑉 - 𝑆$ 之间的最短的边，将对应的点加入到 $𝑆$
证明： 如果 $𝑆$ 和 $𝑉 - 𝑆$ 之间的边是另一个，则和这一个构成环，可以用更小的这一个替代那一个
Kruskal 算法: 排序所有边，从小到大选择不构成环的边
证明： 最小的边一定正确，合并两个端点，化归成 $𝑘 - 1$ 问题

单链聚类是和Kruskal算法同样的流程，但是剩下 $𝑘$ 个类就停了