分治算法(算法篇)

算法之分治算法

分治算法

概念：

• 分治算法也是一种思想策略，分治算法就是将大问题不断地分成小问题解决后再重新构建原问题地解。一般地分治算法的时间复杂度为O(NlogN)
• 分：递归解决较小的问题；治：然后，从子问题的解构建原问题的解。分治算法中我们一直坚持子问题是不相交的(即基本不重叠)

最近点问题

概念:

• 对于平面内存在一个点集P，找到点集P中的最小距离的点对(两个点的距离在点集中所有点产生的距离中最短)。
• 如果按照简单地方法解决就需要嵌套循环导致时间复杂度为O(N²)，但是这个时间复杂度太大了，因此我们就是用到分治

解决方法：

• 将点集P按照x轴进行排序。

  • 对于每个递归操作，将点集P分成两个点集P_L和P_R，找出d_L,d_c,d_R，求这之间的最小值，然后递归返回解得到最终问题的解。

• d_L是在点集P_L最短距离的点对的距离，d_c是跨越点集P_L和P_R的最短距离的点对的距离，d_R是在点集P_R最短距离的点对的距离。

• d_c的求法：令 δ=min(d_L，d_R)，如果出现d_c更小的情况，则d_c的两个点必然在分割线的左右各δ的距离之内，我们将这个区域叫做一条带。我们将在带的区域内的点按照y轴排序，如果两个点的y轴坐标相差大于δ，则d_c>δ，因此就可以不进行判断直接跳过，处理下一对点对。伪代码如下：

  //先将带区域内的点按照y轴排序
  //NumPoint为带区域的点集的点个数
  for(int i=0;i<NumPoint;i++){
      for(int j=i+1;j<Numpoint;j++){
          //判断点对的y轴距离是否大于δ
          if(diff(pi.y,pj.y)>δ){
              break;
          }else if(diff(pi,pj)<δ){    //判断pi到pj的距离是否小于δ
              δ=diff(pi,pj);
          }
      }
  }
  

选择问题

概念：

• 选择问题要求我们找出含N个元素的表S中的第k个最小的元素。
• 该问题的解法虽然使用了分治算法的策略，但是他在分之后只需要求解一个子问题，也不需要合并子问题求解，换句话来说，这个问题就是将大问题不断地分找到属于这个问题地解。

具体做法：

• 每次递归操作，选取一个枢纽元v，将集合S根据枢纽元分成S1，S2两个集合，S1的元素小于枢纽元，S2的元素大于枢纽元
• 如果k<=|S1| –|S1|为集合S1的元素个数，就递归集合S1求解集合S中的第k个最小元素。
• 如果k=|S1|+1，则枢纽元就是第k个最小元素。
• 否则，在S中的第k个最小元素是S2中的第(k-|S1|-1)个最小元素。

五分化中项法：

• 这也是一个选取枢纽元的方法，这个算法的性能更高

概念：

• 把N个元素分成向下取整(N/5)组，5个元素一组，忽略(最多4个)剩余的元素
• 找出每组的中项(中间值)，得到向下取整(N/5)个中项的表M
• 求出M的中项，将其作为枢纽元v返回