分治算法
简要理解
分治算法由三部分组成：
- 分：递归解决较小的问题（基本情况除外）
- 治：从子问题的解构建原问题的解
Tips：
- 传统上，在代码中至少含有两个递归调用的例程叫做分治算法，正文中只有一个递归调用的例程不是分治算法。
- 我们一般坚持子问题不相交，基本上要不重叠。
分治算法解决问题的特点：
- 原问题规模通常比较大，不易直接解决，但问题缩小到一定程度能够较容易的解决。
- 问题可以分解为若干规模较小，求解方式相同（似）的子问题，且子问题之间求解是独立的，互不影响的。
- 合并问题分解的子问题可以得到问题的解
分治算法与递归的关系
分治重要的是一种思想，注重的是问题分，治，合并的过程，而递归是一种方式（工具），这种方式通过方法自己调用自己形成一个来回的过程，分治就是利用了多次这样的来回过程。
经典示例
- 快速排序 快速排序的本质就是对基准数的两边分别递归进行查找交换，在这里，其满足分治算法中分：递归解决较小的问题：把整个数组的查找交换，分成对每个基准数的左右的查找交换的小问题。治：从子问题的解构建原问题的解：在对每个基准数左右进行排序后，整个大问题就已经排好了，就解决了原问题。
- 最近点对 在二维坐标轴上有若干个点坐标，让你求出最近的两个点的距离，我们通常采用分治的方法来处理这种问题，按照x或者y的维度进行考虑，将数据分成两个区域，先分别计算(按照同方法)左右区域内最短的点对。然后根据这个两个中较短的距离向左和向右覆盖，计算被覆盖的左右点之间的距离，找到最小那个距离与当前最短距离比较即可。然后在每个区域的内部我们在进行像上面一样的操作