分治策略-改进.md

减少子问题数

依据

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

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

aa:子问题数,n/bn/b:子问题规模,d(n)d(n):划分与综合工作量。

aa比较大,bb较小,d(n)d(n)不大时,方程的解:W(n)=Θ(nlogba)W(n)=\varTheta(n^{\log_b a})

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

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

例1. 整数位乘问题

输入:X,YX,Ynn位二进制数,n=2kn=2^k

输出:XYXY

普通乘法:需要O(n2)O(n^2)次乘运算

简单划分,令

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

可以得到:

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

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

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

AD+BC=(AB)(DC)+AC+BDAD+BC = (A-B)(D-C) + AC + BD

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

算法复杂度:

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

方程的解:

W(n)=O(nlog3)=O(n1.59)W(n) = O(n^{\log 3}) = O(n^{1.59})

例2. 矩阵相乘的问题

输入:

输出:

小结

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

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

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

增加预处理

例子:平面点对的问题

输入: 平面点集PP中有nn个点,n>1n>1

输出:PP中的两个点,其距离最小

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

分治策略:PP划分为大小相等的PLP_LPRP_R

  • 分别计算PL,PRP_L, P_R中最近点对

  • 计算PLP_LPRP_R中各一个点的最近点对

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

总结

  • 依据

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

  • 提高算法效率的方法

    • 减少子问题个数aa

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

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

作者

Hu

发布于

2021-09-07

更新于

2021-08-25

许可协议

评论