一、基本概念
分而治之是计算机科学中一个非常重要的算法。从字面上解释就是“分而治之”，就是把一个复杂的问题分成两个或两个以上相同或相似的子问题，再把子问题分成更小的子问题.直到子问题可以简单直接求解，而原问题的解就是子问题解的组合。这项技能是许多高效算法的基础，例如排序算法(快速排序、合并排序)、傅里叶变换(快速傅里叶变换).任何能用计算机解决的问题所需的计算时间都与其规模有关。问题规模越小，直接解决越容易，解决的时间也越少。例如，对于n个元素的排序问题，当n=1时，不需要计算。当n=2时，只要进行一次比较，就可以排列顺序。当n=3时，只需进行三次比较。当n较大时，问题就不那么容易处理了。直接解决一个大规模的问题有时是相当困难的。
二、基本思想及策略
分而治之法则的设计思路是：把一个很难解决的大问题直接分割成一些同样大小的小问题，从而逐个进行分而治之。各个击破的策略是：对于规模N的一个问题，如果问题很容易解决(比如规模N比较小)，就直接解决；否则会分解成k个较小的子问题，这些子问题相互独立，形式与原问题相同，然后将这些子问题递归求解，再将每个子问题的解进行组合，得到原问题的解。这种算法设计策略称为分治法。
如果把原问题分成k个子问题，1kn，并且这些子问题可以求解，并且这些子问题的解可以用来寻找原问题的解，那么这种分治法是可行的。分治法生成的子问题往往是原问题的较小模型，这为使用递归技术提供了便利。在这种情况下，反复应用分治法可以使子问题在类型上与原问题保持一致，但其规模不断缩小，最终使子问题缩小到容易直接找到其解的地步。这自然会导致递归过程。分治和递归就像孪生兄弟一样，经常同时用于算法设计，从而产生了许多高效的算法。
00-1010各个击破法一般可以解决具有以下特点的问题：
1)把规模缩小到一定程度，问题很容易解决。
2)问题可以分解成几个较小的相同问题，即问题具有最优子结构性质。
3)该问题分解的子问题的解可以组合成该问题的解；
4)该问题分解的子问题是相互独立的，即子问题不包含共同的子子问题。
第一个特点是大部分问题都能得到满足，因为问题的计算复杂度一般会随着问题规模的增加而增加；
第二个特点是应用分治法的前提，大多数问题都能满足。这个特点体现了递归思想的应用。
第三个特点是关键。能否采用各个击破的方法，完全取决于问题是否有第三个特点。如果第一个和第二个特征可用，但第三个特征不可用，可以考虑贪心法或动态规划法。
第四个特点与分治法的效率有关。如果每个子问题不是独立的，分治法就要做很多不必要的工作，重复求解常见的子问题。虽然此时可以使用分治法，但动态规划法一般更好。
00-1010分而治之的方法在每一级递归上都有三个步骤：
Step1分解：将原问题分解成几个相互独立、形式与原问题相同的子问题；
第二步求解：如果子问题规模小，容易解决，直接求解；否则，递归求解每个子问题。
第三步合并：将每个子问题的解合并到原问题的解中。
其一般算法设计模式如下：
分而治之(临)
1.if |P|n0
2.然后返回
3.将P分解成更小的子问题P1，P2，Pk
4.对于i1到k
5.do yi 分治(Pi) Recursi
其中|P|代表问题P的规模；N0是一个阈值，意味着当问题P的规模不超过n0时，很容易直接解决问题，不需要继续分解。ADHOC(P)是分治法的基本子算法，用于直接求解小规模问题P。因此，当P的尺度不超过n0时，直接用算法ADHOC(P)求解。合并算法(y1，y2，yk)是分治法中的合并子算法，用于合并对应的解Y1，Y2，P2 P1的YK，把P的Pk转化为P的解。
00-1010一种分治法将规模n的问题分成规模n/m的k个子问题来解决。假设分解阈值n0=1，adhoc解的规模为1，需要1个单位时间。让它用f(n)个单位时间把原问题分解成k个子问题，把k个子问题的解合并成原问题的解。T(n)表示分而治之方法解决规模|P|=n的问题所需的计算时间，则：
T(n)=k T(n/m) f(n)
用迭代法求方程的解：
递归方程及其解只给出n等于m的幂时T(n)的值，但如果认为T(n)足够光滑，则可以由n等于m的幂时T(n)的值来估计T(n)的增长率，一般假设T(n)单调上升，从而当minmi 1时，T(mi)T(n)T(mi 1)。
三、分治法适用的情况
用分治法求解的一些经典问题（1）二分搜索
（2）大整数乘法
（3）Strassen矩阵乘法
（4）棋盘覆盖
（5）合并排序
（6）快速排序
（7）线性时间选择
（8）最接近点对问题
（9）循环赛日程表
（10）汉诺塔
七、依据分治法设计程序时的思维过程
实际上就是类似于数学归纳法，找到解决本问题的求解方程公式，然后根据方程公式设计递归程序。
1、一定是先找到最小问题规模时的求解方法
2、然后考虑随着问题规模增大时的求解方法
3、找到求解的递归函数式后（各种规模或因子），设计递归程序即可。