分治法的思想是什么？

给定一个问题集合，大小为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坐标来作为一条边会出现问题 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个节点 i = i − 1( mod p) // move left anti-clockwise 左边p个节点 return (ai, bj ) as upper tangent 复制代码 复制