算法-五大常用算法：分治算法（Divide-and-Conquer）

亦凉 2023-10-05 20:43 28阅读 0赞

分治法，字面意思是“分而治之”，就是把一个复杂的1问题分成两个或多个相同或相似的子问题，再把子问题分成更小的子问题直到最后子问题可以简单地直接求解，原问题的解即子问题的解的合并，这个思想是很多高效算法的基础，例如排序算法(快速排序，归并排序)，傅里叶变换(快速傅里叶变换)等。

分治法的基本思想：将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。

分治策略：对于一个规模为n的问题，若该问题可以容易的解决(比如规模n较小)则直接解决，否则将其分解为k个规模较小的子问题，这些子问题互相独立且与原问题形式相同，递归地解决这些子问题，然后将各个子问题的解合并得到原问题的解。

如果原问题可以分割成k个子问题，1<k<=n，且这些子问题均可解并且利用这些子问题的解求出原问题的解，那么分治方法就是可行的。由分治法产生的子问题往往是原问题的较小模式，这就为使用递归技术提供了方便。反复应用分治手段，可以使子问题与原问题类型一致而其规模却不断缩小，最终使子问题缩小到很容易直接求出其解。这自然导致递归过程的产生。分治与递归经常同时应用在算法设计之中。

## 分治法使用场景 ##

1.  该问题的规模缩小到一定的程度就可以容易的解决。
2.  该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质。
3.  利用该问题分解出的子问题的解可以合并为该问题的解。
4.  该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。

第一条特征是绝大多数问题可以满足的，问题的复杂性一般是随着问题规模的增加而增加；第二条特征是应用分治法的前提。它是大多数问题可以满足的，此特征反映了递归思想的应用。第三条特征是关键，能否利用分治法完全取决于问题是否具有第三条特征，如果具备了第一条和第二条，而不具备第三条特征，则可以考虑使用贪心法或者动态规划法。第四条关系到分治法的效率，如果各个子问题是不独立的则分治法要做寻多不必要的工作，重复的解决公共的子问题，此时虽然可用分治法，但一般使用动态规划法较好。

## 分治法的基本步骤 ##

分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题  
解决：若子问题规模较小而容易被解决则直接解，否则递归地解各个子问题  
合并：将各个子问题的解合并为原问题的解

## 分治法的复杂性分析 ##

一个分治法将规模为n的问题分成k个规模为n/m的子问题去解。设分解阈值 \[公式\] ，且最小子解规模为1的问题消耗一个单位时间。设将原问题分解为k个子问题以及用merge将K个子问题的解合并为原问题的解需用f(n)个单位时间，用T(n)表示该分治法解规模为|P|=n的问题所需的计算时间： T ( n ) = k T ( n / m ) + f ( n ) T(n)=kT(n/m)+f(n) T(n)=kT(n/m)\+f(n)

## 可以使用分治法求解的一些经典问题 ##

二分搜索  
大整数乘法  
Strassen矩阵乘法  
棋盘覆盖  
合并排序  
快速排序  
线性时间选择  
最接近点对问题  
循环赛日程表  
汉诺塔

## 二分搜索法 ##

又叫做二分查找，折半查找，它是一种效率较高的查找方法。

线性表为有序表，先确定待查找记录所在的范围，然后逐步缩小范围直至找到或找不到该记录的位置。

先确定中间位置： m i d d l e = ( l e f t + r i g h t ) / 2 middle=(left+right)/2 middle=(left\+right)/2 ;  
将待查找的key值与data\[middle\].key的值比较，相等则查找成功并返回该位置，否则须确定新得查找区间，继续二分查找，  
如果data\[middle\].key大于key，由于data为有序线性表，可知data\[middle…right\].key均大于key，因此若表中存在关键字等于key的节点，则一定在位置middle左边的子表中。  
反之，data\[middle\].key小于key，若表中存在关键字等于key的节点，则一定在位置middle右边的子表中，下一次查找对新的区域进行查找。  
和动态规划一样，作为一种解决问题的算法思想，仅仅知道其概念是远远不够的，需要出培养这种思维方式，所以必须要有针对性的勤刷题，培养出一种解决问题的思维方式，这样以后遇到类似的问题才能迎刃而解。

--------------------

参考资料：  
[五大常用算法之一：分治算法][Link 1]

[Link 1]: https://www.cnblogs.com/xsyfl/p/6921687.html