The Divide-and-Conquer Strategy

分治策略是一种设计高效算法的有力范型。该方法首先将问题划分成两个较小的子问题,每个子问题除了输入规模较小以外,其他都与原问题是一样的。然后分别解决这两子问题,最后子问题的解合并成为原问题的最终解。

 
 

一般地,分治算法由三步组成:

步骤1:如果问题规模较小,那么使用某种方法直接解决它;否则,划分问题成两个子问题,最好以相同的规模划分。

步骤2:对子问题使用分治算法递归地解决这两个子问题。

步骤3:合并子问题的解成为原问题的解。

 
 

时间复杂度计算公式:


 
 

2维极大点问题

最近点对问题

凸包问题


http://www.csie.ntnu.edu.tw/~u91029/ConvexHull.html

先按极坐标排序,再按graham 扫描凸包,扫描抛弃某一点,可以用向量积判断

 
 

分治构造Voronoi图


 
 

 
 

 
 

 
 



分类: 算法

发表评论

电子邮件地址不会被公开。 必填项已用*标注