分治策略-改进.md

减少子问题数

依据

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

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

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

当$a$比较大，$b$较小，$d(n)$不大时，方程的解：$W(n)=\varTheta(n^{\log_b a})$。

减少$a$是降低函数$W(n)$的阶的途径。

利用子问题的依赖关系，使某些子问题的解通过组合其他子问题的解而得到。

例1. 整数位乘问题

输入：$X,Y$是$n$位二进制数，$n=2^k$

输出：$XY$

普通乘法：需要$O(n^2)$次乘运算

简单划分，令

$X=A2^{n/2}+B, \quad Y=C2^{n/2}+D.$
$XY=AC \quad 2^n + (AD + BC) \quad 2^{n/2} + BD$

可以得到：

$W(n)=4W(n/2)+O(n) \to W(n)=O(n^2)$

这种划分并没有改善效率，子问题数目为4。

子问题间的依赖关系：代数变换

$AD+BC = (A-B)(D-C) + AC + BD$

$AC,BD$可以利用之前的解，所以优化后为三个子问题。

算法复杂度：

$W(n) = 3W(n/2)+cn \\ W(1)=1$

方程的解：

$W(n) = O(n^{\log 3}) = O(n^{1.59})$

例2. 矩阵相乘的问题

输入：

输出：

小结

• 适用于：子问题个数多，划分和综合工作量不太大，时间复杂度函数为$W(n) = \varTheta(n^{\log_b a})$

• 利用子问题之间的依赖关系，用某些子问题解的代数表达式表示另一些子问题的解，减少独立计算子问题的个数。

• 综合解的工作量可能会增加，但增加的工作量不会影响$W(n)$的阶。

增加预处理

例子：平面点对的问题

输入： 平面点集$P$中有$n$个点，$n>1$

输出：$P$中的两个点，其距离最小

蛮力算法：$C(n,2)$个点对，计算最小距离，$O(n^2)$

分治策略：$P$划分为大小相等的$P_L$和$P_R$

• 分别计算$P_L, P_R$中最近点对

• 计算$P_L$与$P_R$中各一个点的最近点对

• 上述情况下的最近点是解。

总结

• 依据

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

• 提高算法效率的方法

  • 减少子问题个数$a$

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

  • 增加与处理，减少$f(n)$