分治法(Divide and Conquer)怎么用？
分治法的思想是什么？
给定一个问题集合，大小为n,将它划分成a个大小为 n/b 的小问题，然后组合每个子问题的结果，递归的解决每个小问题，直到最后的问题被解决
a >=1 b>1 。 解决时间为 T(n)=aT(n/b)+O(合并需要的时间)
使用分治法去解决Convex Hull
convex hull定义
可以定义到更高维，这里添加的是更简单的条件
在二维平面上给定一个集合S
假如任意两个点x坐标不同,y坐标不同，同时不会出现三点共线的情况，定义能够包含全部点的最小多边形为ConvexHux,简写为CH(S) 定义它的边界为按照顺时针顺序开始的双向列表
暴力方式来解决convex hull问题
连接任意的两个点，构建一条边，然后看是否所有的点都在这条边的某一侧，如果都在一侧，那么它就是，否则不是。
分治法解决方案
先按照x轴坐标给所有的点排序，这样的耗时为O(nlgn) 选定一个点的横坐标x，将所有的点分成两部分:CH(A)和CH(B),分别解决CH(A)和CH(B)，然后再合并C(A)和CH(B)
怎么去合并
同样的可以按照粗暴的思路来解决，就是去看所有的两个CH的所有顶点连线，然后看是否所有的点都在它的一侧。 注意：找到两边都只最大的y坐标来作为一条边会出现问题
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)，整个过程耗时为:
合并之后如何删掉不该有的连线？
使用分治法解决找到数组中所有元素数值大小的中间值
最明显的方式就是先排序，然后就直接获取了，排序算法的时间为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的值?
将S分成5列，这样它就是有多行数据，一共5列的二维数组，把每列进行排序，最大的元素在上头，最后x的取值为所有列中间取值的中间的值
方便画有行列交换
经过这么划分，可以看到
- 小于X的取值元素数量至少为：3(n/10-2)
- 大于X的取值元素数量至少为：3(n/10-2)
这里取 n/10的上边界。可以看到一共有 n/5 行，而有一半的行都会存在小于X的数，每行都会有3个，除了包含X的那一行和不足5个元素的最后一行
可以得到整个的耗时为
所有的除法全部上取整
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)。