算法设计与分析Ch03

弃坑了，转战Jeff的《Algorithms》

第三章 分治算法

第一节：分治策略的设计思想

分治策略(Divide and Conquer)

1. 将原始问题划分或者归结为规模较小的子问题
2. 迭归或逐代求解每个子问题
3. 将子问题的解综合得到原问题的解

Remark

1. 子问题与原始问题性质完全一样
2. 子问题之间可彼此独立地求解
3. 迭归停止时子问题可直接求解

二分归并排序

这段代码实现了二分归并排序算法。它将输入数组 A 分成两半递归地进行排序,然后再将排好序的两个子数组合并成一个有序数组。

二分归并排序设计思想

1. 将原问题归结为规模为 $\frac{n}{2}$ 的 2 个子问题。
2. 继续划分，将原问题归结为规模为 $\frac{n}{4}$ 的 4 个子问题，继续上述操作，当子问题规模为 1 时，划分结束。
3. 从规模为 1 到 $\frac{n}{2}$ ，逐层合并子问题的解，得到原问题的解。

二分归并排序时间复杂度分析

假设 n 为 2 的幂，则二分归并排序最坏情况下时间复杂度为：

$$\begin{align*} W(n) & = 2W(\frac{n}{2}) + n - 1 \\ W(1) & = 0 \end{align*}$$

解得：$W(n) = n \log n - n + 1$

$\mathrm{Hanoi}$ 塔问题

算法 $\mathrm{Hanoi}(A, C, n)$ // $n$ 个盘子从 $A$ 到 $C$

1. if $n=1$ then move $(A, C)$ // 1 个盘子从 $A$ 到 $C$
2. else $\mathrm{Hanoi}(A, B, n-1)$
3. $\qquad \text{move }(A, C)$
4. $\qquad \mathrm{Hanoi}(B, C, n-1)$

$\mathrm{Hanoi}$ 塔问题的时间复杂度分析

设 $n$ 个盘子的移动次数为 $T(n)$，则有

$$\begin{align*} T(1) & = 1 \\ T(n) & = 2T(n-1) + 1 \end{align*}$$

解得，$T(n) = 2^n - 1$

$\mathrm{Hanoi}$ 塔问题的算法设计思想

1. 将原问题归结为规模为 $n-1$ 的 2 个子问题。
2. 继续归约，将原问题归结为规模为 $n-2$ 的 4 个子问题，继续上述操作，当子问题规模为 1 时，归约过程结束。
3. 从规模为 1 到 $n-1$ ，逐层合并子问题的解，得到原问题的解。

小结

通过几个例子展示分治算法的特点:

• 将原问题归结为规模小的子问题，子问题与原问题具有相同的性质。
• 子问题规模足够小时可直接求解。
• 算法可以递归也可以迭代实现。
• 算法的分析方法: 递推方程。

第二节：分治算法的一般性描述与分析方法

分治算法 $\textrm{Divide-and-Conquer}(P)$ 的一般性描述

1. if $|P| ≤ c$ then $S(P)$ // 如果问题规模足够，直接求解
2. divide $P$ into $P1, P2, \cdots, Pk$ // 划分子问题
3. for $i \leftarrow 1$ to $k$
4. $\qquad y_i \leftarrow \textrm{Divide-and-Conquer}(P_i)$ // 递归求解子问题
5. Return $Merge (y_1, y_2, \cdots, y_k)$ // 合并子问题的解

设计要点

1. 原问题可以划分或者归约为规模较小的子问题
   1. 子问题与原问题具有相同的性质
   2. 子问题的求解彼此独立
   3. 划分子问题的规模尽可能均衡
2. 子问题规模足够小时可直接求解
3. 子问题的解综合得到原问题的解
4. 算法实现: 递归或迭代

分治算法时间分析

时间复杂度函数的递推方程:

$$\begin{align*} W(n) & = W(|P1|) + W(|P2|) + ... + W(|Pk|) + f(n) \\ W(c) & = C \end{align*}$$

其中:

• $P1, P2, \cdots, Pk$ 为划分后的子问题
• $f(n)$ 为划分子问题以及将子问题解综合得到原问题解的总工作量
• 规模为 $c$ 的最小子问题的工作量为 $C$

两类常见的递推方程

$$\begin{align} f(n) & = \sum_{i=1}^k a_i f(n-i) + g(n) \\ f(n) & = a * f(n/b) + d(n) \end{align}$$

求解方法：

• 方程 1：迭代法、递归树
• 方程 2：迭代法、换元法、递归树、主定理

方程2: $T(n)=a T(n / b)+d(n)$

当 $d(n)$ 为常数时：

$$T(n)=\left\{\begin{array}{ll} O\left(n^{\log _b a}\right) & a \neq 1 \\ O(\log n) & a=1 \end{array}\right.$$

当 $d(n)=c n$ 时：

$$T(n)=\left\{\begin{array}{ll} O(n) & a<b \\ O(n \log n) & a=b \\ O\left(n^{\log _{b} a}\right) & a>b \end{array}\right.$$

小结

第三节：芯片测试

A 报告	B 报告	结论
B 是好的	A 是好的	A、B 都好或 A、B 都坏
B 是好的	A 是坏的	至少一片是坏的
B 是坏的	A 是好的	至少一片是坏的
B 是坏的	A 是坏的	至少一片是坏的

问题

输入：
$n$ 片芯片，其中好芯片至少比坏芯片多 $1$ 片。
问题：
设计一种测试方法，通过芯片测试，从 $n$ 片芯片中挑出 $1$ 片好芯片。
要求：
使用最少的测试次数。

算法设计

判定芯片A的好坏

问题：给定芯片 A，判定 A 的好坏
方法：用其他 $n-1$ 片芯片对 A 测试

举例:
当 $n=7$ 时， 好芯片数 $\geqslant 4$
A 好, 6 个报告中至少 3 个报告"好"
A 坏, 6 个报告中至少 4 个报告"坏"

n 是奇数: 好芯片数 $\geqslant (n+1)/2$
A 好, 至少有 $(n-1)/2$ 个报告"好"
A 坏, 至少有 $(n+1)/2$ 个报告"坏"

当 $n=8$ 时， 好芯片数 $\geqslant 5$
A 好, 7 个报告中至少 4 个报告"好"
A 坏, 7 个报告中至少 5 个报告"坏"

n 是偶数: 好芯片数 $\geqslant n/2 + 1$
A 好, 至少有 $n/2$ 个报告"好"
A 坏, 至少有 $n/2+1$ 个报告"坏"

结论:
至少一半报告"好", A 是好芯片,
超过一半报告"坏", A 是坏芯片。

暴力算法

测试方法:
任取 1 片测试, 如果是好芯片, 测试结束; 如果是坏芯片, 再从剩下芯片中任取 1 片测试, 直到得到 1 片好芯片。

时间估计:
第 1 片坏芯片, 最多测试 n-2 次,
第 2 片坏芯片, 最多测试 n-3 次,
$\cdots$
总计 $\Theta(n²)$

分治算法

偶数情形

假设 n 为偶数, 将 n 片芯片两两一组做测试。剩下的芯片构成子问题，进入下一轮分组淘汰。

淘汰规则:
“好, 好” $\Rightarrow$ 任留 1 片, 进入下轮
其他情况 $\Rightarrow$ 全部淘汰

终止条件: $n \leqslant 3$

1. 3 片芯片, 1 次测试可得到好芯片。（随意选取两个再测试一次，若报告全好，则证明这两个全好；否则，剩下那个必定是好）
2. 1 或 2 片芯片, 不再需要测试。(剩下的都是好芯片)

奇数情形

伪代码

时间复杂度分析

设输入规模为 $n$, 每轮淘汰后, 芯片数至少减半，测试次数(含轮空处理): $O(n)$

时间复杂度:

$$\begin{align*} W(n) &= W(n/2) + O(n) \\ W(3) &= 1, \quad W(2) = W(1) = 0 \end{align*}$$

解得:

$$W(n) = O(n)$$

小结

第四节：快速排序

基本思想

伪代码

实例

时间复杂度分析

最坏情况:

$$\begin{align*} W(n) & = W(n-1) + n-1 \\ W(1) & = 0 \\ W(n) & = n(n-1)/2 \end{align*}$$

最好划分:

$$\begin{align*} T(n) & = 2 T(n/2) + n-1 \\ T(1) & = 0 \\ T(n) & = \Theta(n \log n) \end{align*}$$

均衡划分

平均时间复杂度

小结

快速排序算法

1. 分治策略
2. 子问题划分是由首元素决定
3. 最坏情况下时间复杂度为 $O(n²)$
4. 平均情况下时间复杂度为 $O(n \log n)$

第五节：幂乘算法及其应用

输入: $a$ 为给定实数, $n$ 为自然数
输出: $a^n$

传统算法:
顺序相乘：$a^n = (\cdots ((a a)a)a)\cdots a$

时间复杂度: $\Theta(n)$

分治算法————划分

算法分析

以乘法作为基本运算

• 子问题规模: 不超过 $n/2$
• 两个规模近似 $n/2$ 的子问题完全一样, 只要计算 1 次

$$\begin{align*} W(n) & = W(n/2) + \Theta(1) \\ W(n) & = \Theta( \log n) \end{align*}$$

实例：Fibonacci 数列

传统算法

分治算法

小结

• 分治算法的例子——幂乘算法
• 幂乘算法的应用
  • 计算 Fibonacci 数列
  • 通常算法 $O(n)$, 分治算法为 $O(\log n)$

第六节：改进分治算法的途径

改进方法一：减少子问题数

分治算法的时间复杂度方程：

$$W(n) = aW(n/b) + d(n)$$

其中:

• $a$: 子问题数
• $n/b$: 子问题规模
• $d(n)$: 划分与综合工作量

当 $a$ 较大, $b$ 较小, $d(n)$ 不大时, 方程的解为:

$$W(n) = \Theta(n^{log_b a})$$

注意事项:

• 减少 $a$ 是降低函数 $W(n)$ 的阶的途径
• 利用子问题的依赖关系, 使某些子问题的解通过其他子问题的解而得到。

整数位乘问题

因此，简单的分治并不一定能简化时间复杂度

矩阵相乘问题

小结

改进方法二：增加预处理

平面点对问题

伪代码

增加预处理

小结