一、概念： 在计算机科学中，分治法是建基于多项分支递归的一种很重要的算法范式。字面上的解释是“分而治之”，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，直到最后子问题可以寄简单的直接求解，原问题的解即子问题的解的合并。
这个技巧是很多高校算法的基础，如排序算法（快速排序、归并排序）、傅立叶转换（快速傅立叶变换）
思路：
1.分解：把原问题分解为若干个规模较小，相对独立，与原问题形式相同的子问题。
2. 解决：若子问题规模较小且易于解决时，则直接解。否则，递归地解决各子问题。
3.合并：讲各子问题的解合并为原问题的解。
分治算法是按照下列方案来工作的：
1）将问题的实例划分为几个较小的实例，最好具有相等的规模（事实上，一般来说就是这样来分的，而且分为2个实例的居多，注意是递归的分！！！）
2）对这些较小的实例求解（一般使用递归的方法，但在问题规模足够小的时候也可以采用采用另一个算法（停止递归））
3）如果有必要的话，合并这些较小问题的解，以得到原始问题的解（事实上，一个分治算法的精华就在于合并解的过程）
不要忽视这三句话！！！它是许多分治算法经验的总结，有助于在分析问题中考虑如何去使用分治算法，提请注意括号里我的注释！！！
形象的表示一下，截张图：
总结：
1）分治的思想：一般递归来实现，划分子问题，合并子问题的解。
2）主定理，要很熟悉，常见的递推式应该一眼判断其复杂度。
3）合并排序，快速排序，折半查找，二叉遍历树相关特性，这些都是数据结构的经典内容，之前也都写过了，代码参见前面的相关文章。
这里再次复习，从不同的视角来看它们都是如何用用到了分治的策略。这些内容应当非常熟练。
1）分治的思想：一般递归来实现，划分子问题，合并子问题的解。
2）主定理，要很熟悉，常见的递推式应该一眼判断其复杂度。
3）合并排序，快速排序，折半查找，二叉遍历树相关特性，这些都是数据结构的经典内容，之前也都写过了，代码参见前面的相关文章。
这里再次复习，从不同的视角来看它们都是如何用用到了分治的策略。这些内容应当非常熟练。