分治法(Divide and Conquer)怎么用?

1,738 阅读5分钟

分治法的思想是什么?

给定一个问题集合,大小为n,将它划分成a个大小为 n/b 的小问题,然后组合每个子问题的结果,递归的解决每个小问题,直到最后的问题被解决

a >=1 b>1 。 解决时间为 T(n)=aT(n/b)+O(合并需要的时间)

使用分治法去解决Convex Hull

convex hull定义

可以定义到更高维,这里添加的是更简单的条件

在二维平面上给定一个集合S

S=\lbrace(x_i,y_i)|i=1,2,3,..,n\rbrace

假如任意两个点x坐标不同,y坐标不同,同时不会出现三点共线的情况,定义能够包含全部点的最小多边形为ConvexHux,简写为CH(S)
定义它的边界为按照顺时针顺序开始的双向列表

暴力方式来解决convex hull问题

连接任意的两个点,构建一条边,然后看是否所有的点都在这条边的某一侧,如果都在一侧,那么它就是,否则不是。
一共有n个点,那么得到的边数为n^2,同时要去检验所有的点是否在某一侧,那么总共的耗时为 O(n^3)

分治法解决方案

先按照x轴坐标给所有的点排序,这样的耗时为O(nlgn)
选定一个点的横坐标x,将所有的点分成两部分:CH(A)和CH(B),分别解决CH(A)和CH(B),然后再合并C(A)和CH(B)

怎么去合并

同样的可以按照粗暴的思路来解决,就是去看所有的两个CH的所有顶点连线,然后看是否所有的点都在它的一侧。
注意:找到两边都只最大的y坐标来作为一条边会出现问题

以找到上边界为例,为方便做一条直线使得它刚好切割两个CH,连接两个CH的点a_1,b_1,这两点据选取的轴线x之间的距离在两个图形中均最近。它与选定的轴交于蓝线与选定实线轴交点处。

然后按照顺时针顺序,移动b_1b_3,同样得到紫线与实线的交点
可以发现它在蓝线之下,这时候它是无法作为边的,于是b仍然取b_1,同时a按照逆时针方向移到a_4,交点为橙色线和实线

可以发现它比蓝线和实线的交点更高,于是它更适合,这个时候,再按照顺时针移动b_1b_3
可以看到b_1更加适合,于是a再逆时针移动a_3

可以看到仍然是 (a_4,b_1)仍然是最好的选择,至此a和b都找到了最佳的选择。 算法实现找到上边界伪代码为:

 i=1
 j=1
 while (y(i, j + 1) > y(i, j) or y(i − 1, j) > y(i, j))
     if (y(i, j + 1) > y(i, j)) // move right  clockwise
         j = j + 1( mod q) //右边q个节点
     else
         i = i − 1( mod p) // move left  anti-clockwise 左边p个节点
return (ai, bj ) as upper tangent

p+q=n

可以看到这种方式最多遍历完n个点,耗时为O(n),整个过程耗时为:

T(n)=2T(n/2)+O(n)=O(nlgn)

合并之后如何删掉不该有的连线?

选取新增的上边接(a_4,b_1),类似的下边界(a_2,b_2),沿着(a_4,b_1),按照顺时针的方向,碰到边(b_1,b_3),(b_3,b_2),此时的点刚好到了下边界,然后沿着下边界(a_2,b_2),继续顺时针,知道a_4即得到合并后的边界

使用分治法解决找到数组中所有元素数值大小的中间值

最明显的方式就是先排序,然后就直接获取了,排序算法的时间为O(nlgn)。而使用分治法能够达到O(n)的时间,思路如下。

Select(S, i) //i是要找的元素
 Pick x ∈ S  //选取一个元素
 Compute k = rank(x) //找到x在队列中的位置
 B = {y ∈ S|y<x}
 C = {y ∈ S|y>x}
 if k = i
     return x //x的顺序恰好和找的位置是相同的,直接返回
 else if k>i
     return Select(B, i) 
 else if k<i
    return Select(C, i − k)

对于选择x来讲,如果选择的不好,比如总共n个,恰好选择的是第n-1个,然后是第n-2个,依次类推,总共需要n/2次,每次挑选原数的集合的时候也是O(n),那么如果x选取不好整个的时间为O(n^2)

如果选取x的值?

将S分成5列,这样它就是有多行数据,一共5列的二维数组,把每列进行排序,最大的元素在上头,最后x的取值为所有列中间取值的中间的值

方便画有行列交换

经过这么划分,可以看到

  • 小于X的取值元素数量至少为:3(n/10-2)
  • 大于X的取值元素数量至少为:3(n/10-2)

这里取 n/10的上边界。可以看到一共有 n/5 行,而有一半的行都会存在小于X的数,每行都会有3个,除了包含X的那一行和不足5个元素的最后一行

可以得到整个的耗时为

T(n)=\lbrace^{O(1)\space for \space x<=140}_{T(n/5)+T(7n/10+6)+O(n)\space for\space x>140}

所有的除法全部上取整

T(n/5) 是找到所有行中的中间元素所需要的时间;T(7n/10+6)表示迭代需要的时间,每执行完之后,剩下的数量机n-3(n/10-6);O(n)表示给所有列排序的时间,一列只有5个元素,显然是常量时间,一共有 n/5 列所有的就是O(n)

对于迭代的部分有

T(n)<cn/5+c+cn7/10+6c+O(n)
    <cn+7c+an-cn/10

若7c+an-cn/10<=0

70c+10an-cn<=0
c>=70c/n+10a
当n>=140时,有
c>=c/2+10a
即c>=20a,成立

有T(n)<cn ,此时总耗时为O(n)。