分治算法思想

分治算法的基本思想是将一个计算复杂的问题分为若干个子问题来进行求解，然后综合各个小问题得到复杂问题的最终答案；如果这些子问题还是比较大，难以解决，可以再把它们分 成若干个更小的子问题，直至可以直接求出答案为止。

算法思路 

分治算法的思路是：对于一个规模为N的问题，若该问题可以容易地解决（比如说规模N较小），则直接解决，否则将其分解为M个规模较小的子问题，这些子问题互相独立，并且与 原问题形式相同，递归地解这些子问题，然后将各子问题的解合并得到原问题的解。这种算法设计策略叫做分治法。

如果求解的问题可以分割成M个子问题（1<M≤N），且这些子问题都可解，并可利用这些子问题的解求出原问题的解，那么这种分治法就是可行的。

一般具有以下特征的问题可使用分治法来求解：

1、求解问题可以分解为若干个规模较小的相同问题； 

2、求解问题的规模分解到一定的程度，就能够很容易地求解； 

3、合并子问题的解可以得到求解问题的解；

4、由求解问题所分解出的各个子问题是相互独立的。

编程经验 由分治法产生的子问题往往是原问题的较小模式，这就为使用递归技术提供了方便。在这种情况下，反复应用分治手段，可以使子问题与原问题类型一致而其规模却不断缩 小，最终使子问题缩小到很容易直接求出其解。这样就可以使用上节介绍的递归算法来编写程序，分治与递归算法经常同时应用在算法设计之中，并由此产生许多高效算法。

使用分治法设计程序时，一般可按以下步骤进行： 

（1）分解，将要求解的问题划分成若干规模较小的同类问题； 

（2）求解，当子问题划分得足够小时，用较简单的方法解决，得到子问题的解； 

（3）合并，按求解问题的要求，将子问题的解逐层合并，即可构成最终的解。