[算法]分治策略

分治策略

1 基本思想

将规模为n的原问题规约为规模更小的一个或多个子问题，递归或迭代求解每个子问题，然后把子问题的解进行综合，从而得到原问题的解。

需要注意：

1. 子问题与原问题性质完全一致
2. 子问题之间可以彼此独立的求解
3. 递归停止时的子问题可以直接求解（常数时间）
4. 当子问题划分比较均匀的时候，时间复杂度相对较低

一般分治算法伪代码描述

if |P| <= c then S(p)                   // 递归出口 小规模的问题直接求解
divide P into P1, P2, ..., Pk			// 规约为k个子问题
for i = 1 to k do
	yi <- Divide-and-Conquer(Pi)		// 递归求解子问题
return Merge(y1, y2, ..., yk)           // 综合子问题的解

2 分析技术

分治算法通常是递归算法，分析时间复杂度需要求解递推方程，常见的递推方程有以下两类：
$$
\begin{aligned}
& T\left(n\right)=\sum_{i=1}^{k}a_{i}T\left(n-i\right)+f\left(n\right) \\
& T\left(n\right)=aT\left(\frac{n}{b}\right)+d\left(n\right)
\end{aligned}
$$
对于第一类方程，可以使用迭代、递归树、尝试法求解；

对于第二类方程，可以使用迭代、递归树、主定理法求解；

主定理

$$
\begin{align}
a \geq 1, b > 1 为常数，f(n)为函数，T(n)为非负整数，且T(n)=aT(n/b)+f(n)
\end{align}
$$

$$
\begin{align}
& \qquad(1)若 f(n)=O(n^{\log_ba-\varepsilon}),\varepsilon>0,
则 T(n)=\Theta(n^{\log_ba}). \\
& \qquad(2)若 f(n)=\Theta(n^{\log_ba}),
则 T(n)=\Theta(n^{\log_ba}\operatorname{log}n). \\
& \qquad(3)若 f(n)=\Omega(n^{\log_ba+\varepsilon}),\varepsilon>0, 且对于某个常数c和所有充分大的n, 有 af(n/b)\leqslant cf(n), 则 T(n)=\Theta(f(n)).
\end{align}
$$

3 改进分治算法的途径

改进算法主要有两种途径：

1. 减少子问题个数
2. 通过预处理减少递归过程中的工作量

3.1 通过代数变换减少子问题个数

这种方法主要思想是有的子问题的解可以通过简单的计算由其他子问题的解获得，那么该子问题就不必递归求解，由此减少了子问题的个数。

例子：

1. 整数乘法
2. Strassen矩阵乘法

3.2 利用预处理减少递归内部的计算量

这种方法的主要思想是通过预处理，减少递归内部的计算量，从而达到优化算法的目的。

例子：平面上最邻近点对

4 典型实例

快速幂算法