分治(Divide-and-Conquer)¶
统计信息：字数 4973 阅读10分钟
分治法，字面意思是“分而治之”，就是把一个复杂的1问题分成两个或多个相同或相似的子问题，再把子问题分成更小的子问题直到最后子问题可以简单地直接求解，原问题的解即子问题的解的合并，这个思想是很多高效算法的基础，例如排序算法(快速排序，归并排序)，傅里叶变换(快速傅里叶变换)等。
分治法的基本思想：将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。
分治策略：对于一个规模为n的问题，若该问题可以容易的解决(比如规模n较小)则直接解决，否则将其分解为k个规模较小的子问题，这些子问题互相独立且与原问题形式相同，递归地解决这些子问题，然后将各个子问题的解合并得到原问题的解。
如果原问题可以分割成k个子问题，1<k<=n，且这些子问题均可解并且利用这些子问题的解求出原问题的解，那么分治方法就是可行的。由分治法产生的子问题往往是原问题的较小模式，这就为使用递归技术提供了方便。反复应用分治手段，可以使子问题与原问题类型一致而其规模却不断缩小，最终使子问题缩小到很容易直接求出其解。这自然导致递归过程的产生。分治与递归经常同时应用在算法设计之中。
分治法使用场景¶
- 该问题的规模缩小到一定的程度就可以容易的解决。
- 该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质。
- 利用该问题分解出的子问题的解可以合并为该问题的解。
- 该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。
第一条特征是绝大多数问题可以满足的，问题的复杂性一般是随着问题规模的增加而增加；第二条特征是应用分治法的前提。它是大多数问题可以满足的，此特征反映了递归思想的应用。第三条特征是关键，能否利用分治法完全取决于问题是否具有第三条特征，如果具备了第一条和第二条，而不具备第三条特征，则可以考虑使用贪心法或者动态规划法。第四条关系到分治法的效率，如果各个子问题是不独立的则分治法要做寻多不必要的工作，重复的解决公共的子问题，此时虽然可用分治法，但一般使用动态规划法较好。
分治法的基本步骤¶
- 分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题
- 解决：若子问题规模较小而容易被解决则直接解，否则递归地解各个子问题
- 合并：将各个子问题的解合并为原问题的解
分治法的复杂性分析¶
一个分治法将规模为n的问题分成k个规模为n/m的子问题去解。设分解阈值 ，且最小子解规模为1的问题消耗一个单位时间。设将原问题分解为k个子问题以及用merge将K个子问题的解合并为原问题的解需用f(n)个单位时间，用T(n)表示该分治法解规模为|P|=n的问题所需的计算时间：
可以使用分治法求解的一些经典问题¶
二分搜索法
又叫做二分查找，折半查找，它是一种效率较高的查找方法。
线性表为有序表，先确定待查找记录所在的范围，然后逐步缩小范围直至找到或找不到该记录的位置。
-
先确定中间位置：
;
-
将待查找的key值与data[middle].key的值比较，相等则查找成功并返回该位置，否则须确定新得查找区间，继续二分查找，
-
- 如果data[middle].key大于key，由于data为有序线性表，可知data[middle...right].key均大于key，因此若表中存在关键字等于key的节点，则一定在位置middle左边的子表中。
- 反之，data[middle].key小于key，若表中存在关键字等于key的节点，则一定在位置middle右边的子表中，下一次查找对新的区域进行查找。
和动态规划一样，作为一种解决问题的算法思想，仅仅知道其概念是远远不够的，需要出培养这种思维方式，所以必须要有针对性的勤刷题，培养出一种解决问题的思维方式，这样以后遇到类似的问题才能迎刃而解。