800 lines
26 KiB
Markdown
800 lines
26 KiB
Markdown
|
||
# 第四章 分治法 (Divide and Conquer)
|
||
|
||
## 目录
|
||
|
||
本章共有8个小节：
|
||
|
||
* **4.1 一般方法**
|
||
|
||
* **4.2 二分查找**
|
||
|
||
* **4.3 归并排序**
|
||
|
||
* **4.4 斯特拉森矩阵乘法**
|
||
|
||
* **4.5 二维极大点问题**
|
||
|
||
* **4.6 分治法的优化**
|
||
|
||
* **4.7 主定理**
|
||
|
||
* **4.8 小结**
|
||
|
||
|
||
---
|
||
|
||
## 4.1 一般方法
|
||
|
||
### 1. 分治法适用的问题特征
|
||
|
||
当一个问题满足以下三个特征时，适合使用分治法求解：
|
||
|
||
* **规模大**：输入规模 $n$ 取值相当大，直接求解往往非常困难，甚至无法求出。
|
||
|
||
|
||
* **可分解**：能够将整个输入分解成 $k$ 个不同的子集，从而得到 $k$ 个不同的、可以**独立求解**的子问题。
|
||
|
||
|
||
* **可合并**：在求出子问题的解之后，能够找到适当的方法把它们合并成整个问题的解。
|
||
|
||
|
||
|
||
> **逻辑架构图**：
|
||
>
|
||
>
|
||
> ```
|
||
> 问题 (n个输入)
|
||
> / | \
|
||
> 子问题1 子问题2 ... 子问题k
|
||
> | | |
|
||
> 解1 解2 ... 解k
|
||
> \ | /
|
||
> 整个问题的解
|
||
>
|
||
> ```
|
||
>
|
||
>
|
||
|
||
### 2. 分治法的求解思想（三大核心步骤）
|
||
|
||
分治法的核心是**分而治之**，天然适合用**递归**来实现：
|
||
|
||
* **分 (Divide)**：将原问题分解为若干个子问题。子问题与原问题具有**相同的特征**，但**规模更小**。
|
||
|
||
|
||
* **治 (Conquer)**：反复使用分治策略，直到可以直接求解子问题为止（达到递归边界）。
|
||
|
||
|
||
* **合 (Combine)**：将各个子问题的解逐步组合、合并成原问题的解。
|
||
|
||
|
||
|
||
### 3. 分治策略 DANDC 的抽象化控制（通用的分治伪代码）
|
||
|
||
PPT 提供了一个名为 `DANDC`（Divide AND Conquer）的通用过程模型：
|
||
|
||
```pascal
|
||
procedure DANDC(p, q)
|
||
global n, A(1:n); integer m, p, q;
|
||
// 约束条件: 1 ≤ p ≤ q ≤ n //
|
||
if SMALL(p, q) then
|
||
return (G(p, q))
|
||
else
|
||
m ← DIVIDE(p, q)
|
||
return (COMBINE(DANDC(p, m), DANDC(m+1, q)))
|
||
endif
|
||
end DANDC
|
||
|
||
```
|
||
|
||
* **参数说明**：原问题为数组 $A(1:n)$，初始调用函数为 `DANDC(1, n)`。
|
||
|
||
|
||
* **`SMALL(p, q)`**：一个布尔函数，用于判断当前输入的规模 $q - p + 1$ 是否足够小，小到可以直接求解。
|
||
|
||
|
||
* **`G(p, q)`**：直接求解该小规模问题的函数。
|
||
|
||
|
||
* **`DIVIDE(p, q)`**：分割函数。将原问题在 $m$（$p \le m \le q$）处切开，分为 $A(p:m)$ 和 $A(m+1:q)$ 两个子问题。
|
||
|
||
|
||
* **`COMBINE`**：合并函数，将两个子问题的解合并为原问题的解。
|
||
|
||
|
||
|
||
### 4. 思考题：子问题的个数 $K$ 与规模
|
||
|
||
* **子问题的个数 $K$ 是越多越好吗？**
|
||
|
||
|
||
PPT 中提到了一个“蚯蚓的故事”来启发思考：
|
||
|
||
|
||
> 小蚯蚓无聊，把自己切成两段去打羽毛球了；蚯蚓妈妈觉得不错，把自己切成四段打麻将去了；蚯蚓爸爸想踢足球，于是把自己切成了肉末，结果却死了。
|
||
|
||
|
||
故事寓意：切得太碎（子问题过多、规模太小）会导致**分与合的代价**过大，反而降低算法效率。
|
||
|
||
|
||
* **思考题**：子问题的规模相近或不相近是否会影响算法效率？（后续会给出答案：规模相近即均衡分治往往效率最高）。
|
||
|
||
|
||
|
||
### 5. 分治策略 DANDC 的计算时间
|
||
|
||
假设问题被平分为两个规模大致相等的子问题，则分治策略的计算时间 $T(n)$ 可表示为递推式：
|
||
|
||
|
||
$$T(n) = \begin{cases} g(n) & n \text{ 足够小} \\ 2T(n/2) + f(n) & \text{否则} \end{cases}$$
|
||
|
||
* $T(n)$：输入规模为 $n$ 的分治策略计算时间。
|
||
|
||
|
||
* $g(n)$：对足够小的输入规模，能够直接计算出答案的时间。
|
||
|
||
|
||
* $f(n)$：`DIVIDE` 分割与 `COMBINE` 合成原问题解所消耗的计算时间。
|
||
|
||
|
||
|
||
---
|
||
|
||
## 4.2 二分查找 (Binary Search)
|
||
|
||
### 1. 问题描述与分治建模
|
||
|
||
* **问题描述**：已知一个**非降序**排列的数组 $a_1, a_2, \dots, a_n$，判定给定元素 $x$ 是否在其中。若是，找出 $x$ 的位置并将其下标赋给变量 $j$；否则 $j$ 置为 $0$。
|
||
|
||
|
||
* **分治法建模**：将查找问题表示为 $I = (n, a_1, \dots, a_n, x)$。
|
||
|
||
|
||
* **分**：选取一个下标 $k$，可得到三个子问题：
|
||
|
||
|
||
* $I_1 = (k-1, a_1, \dots, a_{k-1}, x)$ （左半部分）
|
||
|
||
|
||
* $I_2 = (1, a_k, x)$ （中间元素）
|
||
|
||
|
||
* $I_3 = (n-k, a_{k+1}, \dots, a_n, x)$ （右半部分）
|
||
|
||
|
||
|
||
|
||
* **治**：
|
||
|
||
|
||
* 若 $x = a_k$，则 $j \leftarrow k$，算法结束。
|
||
|
||
|
||
* 若 $x < a_k$，说明 $x$ 只可能在左边，在子问题 $I_1$ 中继续求解。
|
||
|
||
|
||
* 若 $x > a_k$，说明 $x$ 只可能在右边，在子问题 $I_3$ 中继续求解。
|
||
|
||
|
||
|
||
|
||
* **合**：当前子问题的解就是整个问题 $I$ 的解（不需要额外的合并操作）。
|
||
|
||
|
||
|
||
|
||
* **思考题**：
|
||
1. $k$ 取什么值？**答**：取中间位置（$\lfloor(low+high)/2\rfloor$）。
|
||
|
||
|
||
2. 合并策略是否正确？即为什么可以忽略掉其他子问题？**答**：因为数组是非降序的，利用单调性可以排除不可能包含 $x$ 的那另一半区域。
|
||
|
||
|
||
|
||
|
||
|
||
### 2. 算法描述 (`BINSRCH` 伪代码)
|
||
|
||
```pascal
|
||
procedure BINSRCH(A, n, x, j)
|
||
integer low, high, mid, j, n;
|
||
low ← 1; high ← n;
|
||
while low ≤ high do
|
||
mid ← ⌊(low + high) / 2⌋ // 取中间值
|
||
case
|
||
: x < A(mid): high ← mid - 1 // 前一半
|
||
: x > A(mid): low ← mid + 1 // 后一半
|
||
: else: j ← mid; return; // 查找成功结束
|
||
endcase
|
||
repeat
|
||
j ← 0 // 查找失败
|
||
end BINSRCH
|
||
|
||
```
|
||
|
||
### 3. 正确性证明思路
|
||
|
||
1. **检验到参数的每类取值**。
|
||
|
||
|
||
2. **检验到算法的每个分支**。
|
||
|
||
|
||
|
||
* 如果 $n=0$，则不进入循环，$j=0$，算法终止，正确。
|
||
|
||
|
||
* 否则进入循环：
|
||
* **成功情况**：若 $x = A(mid)$，则 $j = mid$，查找成功，算法终止。若 $x < A(mid)$，由于数组有序，$x$ 不可能在 $mid \sim high$ 范围，查找范围缩小到 $low \sim mid-1$（$x > A(mid)$ 时同理缩小到右半部分），正确。
|
||
|
||
|
||
* **不成功情况**：由于 `low`, `high`, `mid` 都是整型变量，查找范围不断缩小，总可以在有限步内使得 $low > high$，说明 $x$ 不在 $A$ 中，退出循环，$j = 0$ 算法终止，正确。
|
||
|
||
|
||
|
||
|
||
|
||
### 4. 算法实例与二元比较树
|
||
|
||
假设 $n=9$，排好序的数组为：
|
||
|
||
| 下标 | A[1] | A[2] | A[3] | A[4] | A[5] | A[6] | A[7] | A[8] | A[9] |
|
||
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
|
||
| **值** | -15 | -6 | 0 | 7 | 9 | 23 | 54 | 82 | 101 |
|
||
|
||
PPT 举了4种查找情况：
|
||
|
||
* **情况1**：$x = 9$，在 `mid=5` 处第1次比较即成功。
|
||
|
||
|
||
* **情况2**：$x = -15$，依次比较 `A[5]` $\rightarrow$ `A[2]` $\rightarrow$ `A[1]`，第3次成功。
|
||
|
||
|
||
* **情况3**：$x = 101$，依次比较 `A[5]` $\rightarrow$ `A[7]` $\rightarrow$ `A[8]` $\rightarrow$ `A[9]`，第4次成功。
|
||
|
||
|
||
* **情况4**：$x = 8$（查找失败），依次比较 `A[5]` $\rightarrow$ `A[7]` $\rightarrow$ `A[6]` $\rightarrow$ 失败退出。
|
||
|
||
|
||
* **思考题**：对称的元素为什么比较次数不同？
|
||
这是由**二元比较树 (Binary Comparison Tree)** 的结构决定的。二分查找的执行过程本质上就是在一棵确定的二元比较树上从根节点向下走的过程。
|
||
|
||
|
||
* **内节点**：记录一个 `mid` 值，表示一次元素的比较。
|
||
|
||
|
||
* **外节点（方块）**：表示查找失败的一种情况。
|
||
|
||
|
||
* **路径**：表示一个元素的比较序列。
|
||
|
||
|
||
|
||
|
||
|
||
> 对于 $n=9$，生成的二元比较树结构如下（节点中为对应数组下标）：
|
||
>
|
||
>
|
||
|
||
```
|
||
> 5
|
||
> / \
|
||
> 2 7
|
||
> / \ / \
|
||
> 1 3 6 8
|
||
> / \
|
||
> 4 9
|
||
```
|
||
|
||
|
||
* **思考题**：二元比较树的结构受问题实例（具体数据值）影响吗？**答**：不受影响，它仅仅由数组的大小 $n$ 决定。
|
||
|
||
### 5. 性能与复杂度分析
|
||
令根节点在第1级，内节点最大级数为 $k$。
|
||
* **成功查找**：元素比较次数等同于所在**内节点级数**。最少 $1$ 次，最多 $k$ 次。
|
||
* **失败查找**：元素比较次数等同于对应**外节点级数 $- 1$**。最少 $k-1$ 次，最多 $k$ 次。
|
||
|
||
针对 $n=9$ 的具体实例分析：
|
||
* **成功查找总比较数** = $1 + 2\times2 + 4\times3 + 2\times4 = 25$（即各内节点级数之和：$1+2+2+3+3+3+3+4+4=25$）。
|
||
* **失败查找总比较数** = $3+3+3+4+4+3+3+3+4+4 = 34$。
|
||
|
||
| 查找结果 ($n=9$) | 最好情况 | 最坏情况 | 平均情况 |
|
||
| :--- | :---: | :---: | :---: |
|
||
| **成功** | 1 | 4 | $25/9$ |
|
||
| **失败** | 3 | 4 | $34/10$ |
|
||
|
||
#### 内节点个数 $n$ 与最大级数 $k$ 的数学关系
|
||
最大级数为 $k$ 的二元比较树，其前 $k-1$ 层必为满二叉树。因此有：
|
||
$$2^{k-1} \le n < 2^k \implies k-1 \le \log_2 n < k \implies k = \lfloor\log_2 n\rfloor + 1$$
|
||
由于 $k = \Theta(\log n)$，这奠定了二分查找的时间基调。
|
||
|
||
#### 核心定理 4.1
|
||
> 若 $n$ 在区域 $[2^{k-1}, 2^k)$ 中，则对于一次成功的查找，二分查找算法至多做 $k$ 次比较；而对于一次不成功的查找，或者作 $k-1$ 次比较或者作 $k$ 次比较。
|
||
|
||
#### 成功查找的平均时间复杂度证明
|
||
利用内部路径长度 $I$（根到所有内节点距离之和）和外部路径长度 $E$（根到所有外节点距离之和）的特殊关系：
|
||
1. 数学上可证明：$E = I + 2n$。
|
||
2. 成功平均比较次数：$S(n) = (I / n) + 1$。
|
||
3. 失败平均比较次数：$U(n) = E / (n + 1)$。
|
||
代入公式推导：
|
||
$$E = (n+1)U(n) = I + 2n = n(S(n)-1) + 2n \implies S(n) = (1 + \frac{1}{n})U(n) - 1$$
|
||
由此证明 $S(n) = \Theta(U(n)) = \Theta(\log n)$。
|
||
|
||
#### `BINSRCH` 算法的时空复杂度总结
|
||
* **时间复杂度**：
|
||
* **成功查找**：最好 $\Theta(1)$，最坏 $\Theta(\log n)$，平均 $\Theta(\log n)$。
|
||
* **失败查找**：最好 $\Theta(\log n)$，最坏 $\Theta(\log n)$，平均 $\Theta(\log n)$。
|
||
* **空间复杂度**：除了存放数组 $A$ 本身之外，只需要存储 `low`, `high`, `mid`, `x`, `j` 五个辅助变量，共需空间 $n + 5 = \Theta(n)$。
|
||
|
||
### 6. 算法的变型
|
||
* **思考题**：二分思想下的查找算法时间复杂度是固定不变的吗？会受到实现细节的影响吗？
|
||
为了探究这一点，PPT 给出了两个变型算法：
|
||
|
||
#### 变型一：使用 `if-else` 代替 `case`
|
||
```pascal
|
||
// 循环中一次关键字比较分出两个分支，而非三个分支
|
||
if x < A(mid) then high ← mid - 1
|
||
else if x > A(mid) then low ← mid + 1
|
||
else j ← mid; return;
|
||
|
||
```
|
||
|
||
缺点：最坏情况下，$x$ 每一轮循环都要被比较两次。
|
||
|
||
#### 变型二：`BINSRCH1`（延迟比较相等）
|
||
|
||
```pascal
|
||
procedure BINSRCH1(A, n, x, j)
|
||
integer low, high, mid, j, n;
|
||
low ← 1; high ← n + 1; // high总比可能的取值大1
|
||
while low < high - 1 do
|
||
mid ← ⌊(low + high) / 2⌋
|
||
if x < A(mid) then high ← mid // 在循环中只做一次比较
|
||
else low ← mid // x >= A(mid)
|
||
endif
|
||
repeat
|
||
if x = A(low) then j ← low // 退出循环后再判断x是否存在
|
||
else j ← 0
|
||
end BINSRCH1
|
||
|
||
```
|
||
|
||
* **特点**：无论成功与否，最好、最坏和平均情况的时间复杂度**全部死死固定为 $\Theta(\log n)$**（失去了最好情况 $\Theta(1)$ 的优势）。
|
||
|
||
|
||
|
||
### 7. 以比较为基础的查找问题时间下界
|
||
|
||
* **定理 4.2**：设 $A(1:n)$ 含有 $n$ 个互不相同的有序元素。任何以比较为基础去判断 $x \in A(1:n)$ 的算法，在最坏情况下所需的最小比较次数 $FIND(n) \ge \lceil\log_2(n+1)\rceil$。
|
||
|
||
|
||
* **证明思路**：任意一种查找算法都可以构建一棵二元比较树，其最坏情况比较次数对应树的最大高度。树中必须包含至少 $n$ 个内节点（对应 $n$ 种查找成功的情况）。根据二叉树性质，高度为 $k$ 的树最多有 $2^k-1$ 个内节点，因此 $n \le 2^k - 1 \implies FIND(n) = k \ge \lceil\log_2(n+1)\rceil$。
|
||
|
||
|
||
* **结论**：**二分查找是解决查找问题最坏情况下的最优算法**，不存在比 $\Theta(\log n)$ 级别更低的基于比较的查找算法。
|
||
|
||
|
||
* **本节留下的思考题**：
|
||
1. 证明 $E = I + 2n$。
|
||
|
||
|
||
2. 证明 `BINSRCH1` 在各种情况下的时间均为 $\Theta(\log n)$。
|
||
|
||
|
||
3. 三分（或多分）查找会得到更优的结果吗？（提示：虽然层数变少，但单层的比较次数变多，整体复杂度数量级不变）。
|
||
|
||
|
||
|
||
|
||
|
||
---
|
||
|
||
## 4.3 归并排序 (Merge Sort)
|
||
|
||
### 1. 分治策略设计
|
||
|
||
对比普通的**直接插入法**（最好 $O(n)$，最坏 $O(n^2)$），归并排序通过分治法极大地提升了最坏情况下的效率：
|
||
|
||
* **分**：将包含 $n$ 个元素的序列 $A(1..n)$ 平均分成两个子集：$A(1 \dots \lfloor n/2\rfloor)$ 和 $A(\lfloor n/2\rfloor+1 \dots n)$。
|
||
|
||
|
||
* **治**：递归调用自身，将这两个子集分别排好序。
|
||
|
||
|
||
* **合**：调用 `MERGE` 算法将两个有序的子集组合成一个完整的有序集合。
|
||
|
||
|
||
|
||
### 2. 算法描述
|
||
|
||
#### 主算法 `MERGESORT`
|
||
|
||
```pascal
|
||
Procedure MERGESORT(low, high)
|
||
int low, high, mid;
|
||
if low < high then
|
||
mid ← ⌊(low + high) / 2⌋
|
||
call MERGESORT(low, mid) // 递归对左半部分排序
|
||
call MERGESORT(mid + 1, high) // 递归对右半部分排序
|
||
call MERGE(low, mid, high) // 合并
|
||
endif
|
||
end MERGESORT
|
||
|
||
```
|
||
|
||
#### 核心合并算法 `MERGE` 的思想与实现
|
||
|
||
* **合并思想**：设定两个指针 $h$ 和 $j$ 分别指向两个子数组的起点，挨个比较大小，把小的挪到辅助数组 $B$ 的 $i$ 位置中：
|
||
|
||
|
||
1. 若 $h \le mid$ 且 $j \le high$，则 $B(i) \leftarrow \min(A(h), A(j))$。
|
||
|
||
|
||
2. 若其中一个子数组已处理完（例如 $h > mid$），则直接拷贝另一个子数组的剩余部分。
|
||
|
||
|
||
|
||
|
||
|
||
```pascal
|
||
procedure MERGE(low, mid, high)
|
||
integer h, i, j, k, low, mid, high;
|
||
global A(low: high); local B(low: high);
|
||
h ← low; i ← low; j ← mid + 1;
|
||
|
||
// 两个子集合都有剩余元素时进行处理
|
||
while h ≤ mid and j ≤ high do
|
||
if A(h) ≤ A(j) then
|
||
B(i) ← A(h); h ← h + 1
|
||
else
|
||
B(i) ← A(j); j ← j + 1;
|
||
endif
|
||
i ← i + 1
|
||
repeat
|
||
|
||
// 处理某一侧剩余的元素
|
||
if h > mid then
|
||
for k ← j to high do B(i) ← A(k); i ← i + 1; repeat
|
||
else
|
||
for k ← h to mid do B(i) ← A(k); i ← i + 1; repeat
|
||
endif
|
||
|
||
// 将辅助数组B中的有序数据复制回原数组A
|
||
for k ← low to high do A(k) ← B(k)
|
||
end MERGE
|
||
|
||
```
|
||
|
||
### 3. 算法实例
|
||
|
||
PPT 展现了 $n=5$ 时的数组 `[6, 3, 9, 4, 1]` 的递归分解与合并过程：
|
||
|
||
* **分解树的调用顺序 (low, high)**：`(1,5)` $\rightarrow$ `(1,3)` $\rightarrow$ `(1,2)` $\rightarrow$ `(1,1)` 与 `(2,2)`。
|
||
|
||
|
||
* 触底单元素后开始执行 `MERGE(low, mid, high)`：依次调用 `MERGE(1,1,2)` $\rightarrow$ `MERGE(1,2,3)` $\rightarrow$ 右侧 `MERGESORT(4,5)` 触发 `MERGE(4,4,5)` $\rightarrow$ 最后执行大合并 `MERGE(1,3,5)`。
|
||
|
||
|
||
* **思考题**：算法的调用过程受问题实例影响吗？**答**：不受影响，只取决于 `low` 和 `high` 的计算。
|
||
|
||
|
||
|
||
### 4. 计算时间分析
|
||
|
||
归并排序的递推关系式为：
|
||
|
||
|
||
$$T(n) = \begin{cases} a & n = 1 \\ 2T(n/2) + cn & n > 1 \end{cases} \quad \text{($a, c$ 为常数)}$$
|
||
|
||
|
||
通过展开递推式：
|
||
|
||
|
||
$$T(n) = 2^2 T(n/4) + 2cn = 2^3 T(n/8) + 3cn = \dots = 2^k T(1) + kcn$$
|
||
|
||
|
||
设 $n = 2^k$，则有 $k = \log_2 n$，代入得：$T(n) = an + cn\log_2 n$。
|
||
如果 $2^k < n \le 2^{k+1}$，同样可得：$T(n) = O(n\log n)$。
|
||
|
||
* **结论**：归并排序在**最好、最坏、平均**情况下的时间复杂度全部为 **$O(n\log n)$**。
|
||
|
||
|
||
|
||
### 5. 归并排序算法的优化技巧
|
||
|
||
* **时间优化**：频繁的递归调用会带来很大的系统开销。可以在子集合的元素个数**很少时，转而采用“直接插入排序”**，从而减少递归深度，节省运行时间。
|
||
|
||
|
||
* **空间优化**：创建辅助数组 $B$ 并将结果拷回 $A$ 非常耗费空间和时间。可以引入一个链接数组 `LINK(1:n)`，里面存放的是指向 $A$ 元素的指针（下标），通过改变指针来指示有序序列，消除物理拷贝。
|
||
|
||
|
||
* **思考题**：能否采用自底向上的设计方式来取消对系统栈空间的需要？**答**：可以，通过循环迭代逐步合并长度为 1、2、4、8...的子数组（即非递归归并排序）。
|
||
|
||
|
||
|
||
### 6. 以比较为基础的排序算法时间下界
|
||
|
||
* 任何基于关键字比较的排序算法，其最坏情况下的时间下界均为 **$\Omega(n\log n)$**。因此，从数量级角度看，归并排序是最坏情况下的最优算法。
|
||
|
||
|
||
* **证明方法**：利用三元素排序的二元比较树来阐述。$n$ 个关键字共有 $n!$ 种不同的排列组合，这就意味着二元比较树必须至少有 $n!$ 个外节点。设最坏情况下的比较次数（即树的高度）为 $T(n)$，则有：
|
||
|
||
|
||
|
||
$$2^{T(n)} \ge n! \ge n(n-1)\dots(\lfloor n/2\rfloor) \ge (n/2)^{n/2}$$
|
||
|
||
|
||
|
||
两边取对数，当 $n \ge 4$ 时，由于 $\log_2(n/2) \ge \frac{1}{2}\log_2 n$，可以推导出：
|
||
|
||
|
||
|
||
$$T(n) \ge \frac{n}{2}\log_2(\frac{n}{2}) \ge \frac{n}{4}\log_2 n \implies T(n) = \Omega(n\log n)$$
|
||
|
||
|
||
|
||
---
|
||
|
||
## 4.4 斯特拉森矩阵乘法 (Strassen's Matrix Multiplication)
|
||
|
||
### 1. 传统矩阵相乘及普通分治的瓶颈
|
||
|
||
对于两个 $n \times n$ 的矩阵 $A$ 和 $B$（假设 $n$ 为 2 的幂），传统的标准计算方法需要执行 $n^3$ 次乘法和 $n^2(n-1)$ 次加法，时间复杂度为 **$O(n^3)$**。
|
||
|
||
如果使用普通的**分治法**，将 $A$ 和 $B$ 各自切分为4个 $(n/2) \times (n/2)$ 的子矩阵：
|
||
|
||
|
||
$$\begin{bmatrix} C_{11} & C_{12} \\ C_{21} & C_{22} \end{bmatrix} = \begin{bmatrix} A_{11} & A_{12} \\ A_{21} & A_{22} \end{bmatrix} \begin{bmatrix} B_{11} & B_{12} \\ B_{21} & B_{22} \end{bmatrix}$$
|
||
|
||
|
||
展开后的子矩阵计算公式为：
|
||
|
||
|
||
$$C_{11} = A_{11}B_{11} + A_{12}B_{21}$$
|
||
|
||
$$C_{12} = A_{11}B_{12} + A_{12}B_{22}$$
|
||
|
||
$$C_{21} = A_{21}B_{11} + A_{22}B_{21}$$
|
||
|
||
$$C_{22} = A_{21}B_{12} + A_{22}B_{22}$$
|
||
|
||
|
||
这种普通分治法一共需要进行 **8 次矩阵乘法**和 **4 次矩阵加法**。其计算时间递推式为：
|
||
|
||
|
||
$$T(n) = \begin{cases} b & n \le 2 \\ 8T(n/2) + dn^2 & n > 2 \end{cases}$$
|
||
|
||
|
||
利用主定理计算，其时间复杂度依然是 **$O(n^3)$**。
|
||
|
||
* **思考题**：当前分治法没有提高求解效率的原因是什么？**答**：子问题的个数（8次矩阵乘法）太多了。
|
||
|
||
|
||
|
||
### 2. 斯特拉森矩阵乘法核心思想
|
||
|
||
斯特拉森（Strassen）利用高超的代数技巧，将子问题的矩阵乘法个数**由 8 个缩减为 7 个**。
|
||
他首先计算出 7 个中间矩阵 $M_1 \sim M_7$（用了7次乘法，10次加/减法）：
|
||
|
||
* $M_1 = A_{11}(B_{12} - B_{22})$
|
||
* $M_2 = (A_{11} + A_{12})B_{22}$
|
||
* $M_3 = (A_{21} + A_{22})B_{11}$
|
||
* $M_4 = A_{22}(B_{21} - B_{11})$
|
||
* $M_5 = (A_{11} + A_{22})(B_{11} + B_{22})$
|
||
* $M_6 = (A_{12} - A_{22})(B_{21} + B_{22})$
|
||
* $M_7 = (A_{11} - A_{21})(B_{11} + B_{12})$
|
||
|
||
随后，通过 8 次加/减法组合出最终的子矩阵解：
|
||
|
||
* $C_{11} = M_{5} + M_{4} - M_{2} + M_{6}$
|
||
* $C_{12} = M_{1} + M_{2}$
|
||
* $C_{21} = M_{3} + M_{4}$
|
||
* $C_{22} = M_{5} + M_{1} - M_{3} - M_{7}$
|
||
|
||
### 3. 时间复杂度推导
|
||
|
||
新的时间复杂度递推式为：
|
||
|
||
|
||
$$T(n) = \begin{cases} O(1) & n \le 2 \\ 7T(n/2) + O(n^2) & n > 2 \end{cases}$$
|
||
|
||
|
||
令 $n = 2^k$，逐步展开可以得到：
|
||
|
||
|
||
$$T(n) = 7^k T(n/2^k) + an^2 \sum_{i=0}^{k-1} (\frac{7}{4})^i \le 7^k + cn^2(\frac{7}{4})^k$$
|
||
|
||
|
||
因为 $7^k = 7^{\log_2 n} = n^{\log_2 7}$，代入化简最终得到：
|
||
|
||
|
||
$$T(n) = O(n^{\log_2 7}) \approx \mathbf{O(n^{2.81})}$$
|
||
|
||
|
||
这成功打破了 $O(n^3)$ 的魔咒。
|
||
|
||
### 4. 总结
|
||
|
||
* 分治法不一定总能自动提高效率，**减少子问题个数**是降低时间复杂度的极其有效的途径。
|
||
|
||
|
||
* Hopcroft 和 Kerr 已于 1971 年证明，计算两个 $2 \times 2$ 矩阵的乘积，**7次乘法是绝对必要的**。若想进一步降低复杂度，必须跳出 $2 \times 2$ 的框架，转而研究 $3 \times 3$ 或 $5 \times 5$ 的更优切分方法。
|
||
|
||
|
||
|
||
---
|
||
|
||
## 4.5 二维极大点问题 (Two-dimensional Maxima Problem)
|
||
|
||
### 1. 问题描述
|
||
|
||
* **支配规则**：在二维平面空间中，如果满足 $x_1 \ge x_2$ 且 $y_1 \ge y_2$，则称点 $(x_1, y_1)$ **支配**点 $(x_2, y_2)$。
|
||
|
||
|
||
* **极大点**：在一个点集中，如果某一个点**没有被其他任何点支配**，它就是极大点。
|
||
|
||
|
||
* **任务**：给定包含 $n$ 个平面的点集 $S$，找出其中所有的极大点。
|
||
|
||
|
||
* **蛮力法**：直接两两比较，时间复杂度为 $O(n^2)$。
|
||
|
||
|
||
|
||
### 2. 分治法设计思想
|
||
|
||
* **分**：设计一条垂直于 X 轴的**中位线 $L$**，将整个点集平分为包含 $n/2$ 个点的左右两个子集 $S_L$ 和 $S_R$。
|
||
|
||
|
||
* **治**：递归地分别找出 $S_L$ 和 $S_R$ 的极大点。
|
||
|
||
|
||
* **合**：基于支配规则合并两边的结果。由于 $S_R$ 中所有的点的 $x$ 值都大于 $S_L$ 中的点，所以 **$S_R$ 的极大点绝对不可能被 $S_L$ 支配**。我们在合并时，只需要检查 $S_L$ 的极大点 $p$：若 $y_p$ 小于 $S_R$ 中极大点的最大 $y$ 值，则说明 $p$ 被右侧的点支配了，应当将其舍弃。
|
||
|
||
|
||
|
||
### 3. 核心问题思考
|
||
|
||
* **思考1：怎样确定中位线？** 答：对集合所有点按 $x$ 值进行排序，取第 $n/2$ 个点的位置。
|
||
|
||
|
||
* **思考2：怎样设计递归出口？** 答：如果集合 $S$ 中只有一个点，那么该点直接输出为极大点。
|
||
|
||
|
||
* **思考3：$S_L$ 和 $S_R$ 先求解哪一个更合理？** 答：先求解 $S_R$。因为先求出 $S_R$ 就可以直接得到右侧极大点的最大 $y$ 值，从而在处理 $S_L$ 时顺便完成过滤。
|
||
|
||
|
||
|
||
### 4. 算法时间复杂度与“预排序”优化
|
||
|
||
如果我们在每一步递归中都对 $x$ 重新排序来找中位线，则划分（分）的代价为 $O(n\log n)$。
|
||
递推式为：$T(n) = 2T(n/2) + O(n\log n) + O(n)$，这样计算会导致总时间退化为 $O(n\log^2 n)$。
|
||
|
||
* **“预排序”优化策略**：把排序工作提取到递归过程之外。在分治前，先对所有点的 $x$ 坐标进行一次总的预排序（时间为 $O(n\log n)$）。后续递归时只需根据预排序好的序列直接 $O(1)$ 查找中位线。
|
||
|
||
|
||
* **优化后的分治计算时间**：
|
||
|
||
|
||
|
||
$$T(n) = \begin{cases} 1 & n = 1 \\ 2T(n/2) + O(n) & n > 1 \end{cases} \implies \text{分治核心阶段需 } O(n\log n)$$
|
||
|
||
|
||
* **总时间复杂度**：预排序 $O(n\log n)$ + 分治过程 $O(n\log n)$ = **$O(n\log n)$**，完美优于蛮力法的 $O(n^2)$。
|
||
|
||
|
||
|
||
---
|
||
|
||
## 4.6 分治法的优化技巧总结
|
||
|
||
分治法虽然强大，但在某些情况下如果设计不当，也会导致效率低下。
|
||
|
||
### 效率低下的两大诱因
|
||
|
||
1. **原因1：子问题个数多**。通常发生在“治”的环节。
|
||
|
||
|
||
2. **原因2：递归过程内的工作量过多**。通常发生在“分”或“合”的环节。
|
||
|
||
|
||
|
||
### 对应两大优化策略
|
||
|
||
* **策略1（针对子问题多）**：**寻找子问题之间的依赖关系**。如果某个子问题的解可以通过其他子问题的解经由简单的代数运算得到，就绝不重新递归计算它。
|
||
|
||
|
||
* *典型范例*：斯特拉森矩阵相乘（减少1个乘法子问题）、归并排序（小规模下直接用插入排序减少小规模子问题）。
|
||
|
||
|
||
|
||
|
||
* **策略2（针对递归内工作量大）**：**提取到递归过程之外进行预处理**。
|
||
|
||
|
||
* *典型范例*：二维极大点问题（提前预排序 $x$ 轴坐标）；二维最近点对问题（提前预排序 $x$ 和 $y$ 坐标，以便合并时用双指针技巧减少线段比较次数）。
|
||
|
||
|
||
|
||
|
||
|
||
---
|
||
|
||
## 4.7 主定理 (Master Theorem)
|
||
|
||
### 1. 什么是主定理
|
||
|
||
主定理专门用于求解形如 $T(n) = aT(n/b) + f(n)$ 的分治递推式渐近界，其中 $a \ge 1, b > 1$ 为常数，$f(n)$ 是非负函数。
|
||
根据 $f(n)$ 的数量级与 $n^{\log_b a}$ 的大小对比，分为三种情况：
|
||
|
||
* **情况 1（$f(n)$ 数量级显著低于 $n^{\log_b a}$）**：
|
||
若存在常数 $\epsilon > 0$，使得 $f(n) = O(n^{\log_b a - \epsilon})$，则：
|
||
|
||
|
||
|
||
$$T(n) = \Theta(n^{\log_b a})$$
|
||
|
||
|
||
* **情况 2（$f(n)$ 数量级恰好等于 $n^{\log_b a}$）**：
|
||
若 $f(n) = \Theta(n^{\log_b a})$，则：
|
||
|
||
|
||
|
||
$$T(n) = \Theta(n^{\log_b a}\log n)$$
|
||
|
||
|
||
* **情况 3（$f(n)$ 数量级显著高于 $n^{\log_b a}$）**：
|
||
若存在常数 $\epsilon > 0$，使得 $f(n) = \Omega(n^{\log_b a + \epsilon})$，且满足常规条件：当 $n$ 足够大时，对某个常数 $c < 1$ 有 $a f(n/b) \le c f(n)$，则：
|
||
|
||
|
||
|
||
$$T(n) = \Theta(f(n))$$
|
||
|
||
|
||
|
||
### 2. 用主定理理解前文算法
|
||
|
||
1. **斯特拉森矩阵乘法**：$a = 7, b = 2, f(n) = \Theta(n^2)$。
|
||
计算 $n^{\log_b a} = n^{\log_2 7} \approx n^{2.81}$。因为 $n^2 = O(n^{2.81 - \epsilon})$，符合**情况1**，故 $T(n) = \Theta(n^{\log_2 7})$。
|
||
|
||
|
||
2. **归并排序**：$a = 2, b = 2, f(n) = \Theta(n)$。
|
||
计算 $n^{\log_b a} = n^{\log_2 2} = n^1$。因为 $f(n) = \Theta(n^1)$，符合**情况2**，故 $T(n) = \Theta(n\log n)$。
|
||
|
||
|
||
|
||
### 3. 通用简便效率分析结论
|
||
|
||
如果在通用递归式中，合并所需时间简写为 $f(n) = \Theta(n^d)$，我们只需直接比较 $\log_b a$ 与 $d$ 的大小关系：
|
||
|
||
|
||
$$T(n) = \begin{cases} \Theta(n^d) & \text{当 } a < b^d \\ \Theta(n^d \log n) & \text{当 } a = b^d \\ \Theta(n^{\log_b a}) & \text{当 } a > b^d \end{cases}$$
|
||
|
||
---
|
||
|
||
## 4.8 本章小结
|
||
|
||
* **分治法的三个核心特点**：**分（Divide）- 治（Conquer）- 合（Combine）**。
|
||
|
||
|
||
* **子问题独立性**：各子问题之间是独立的，两个子问题绝不会共享同一个问题域更小的公共子问题。
|
||
|
||
|
||
* **方向**：自顶向下地将原问题分解成子问题。
|
||
|
||
|
||
|
||
### 各节重点掌握要求
|
||
|
||
1. **4.1 一般方法**：掌握分治法适用的问题特点、求解思想、一般控制流程和计算时间模型。
|
||
|
||
|
||
2. **4.2 二分查找 & 4.3 归并排序**：掌握算法的设计思想、正确性证明、时间复杂度分析方法（如二元比较树法）。
|
||
|
||
|
||
3. **4.4 斯特拉森矩阵乘法 & 4.5 二维极大点问题 & 4.6 分治法的优化**：深入理解如何应对复杂问题，掌握**减少子问题个数**与**预处理提取**两大优化核心技巧。
|
||
|
||
|
||
4. **4.7 主定理**：必须熟练掌握并运用主定理来独立分析算法复杂度。
|