分治法的基本思想

概念：在计算机科学中，分治法是一种很重要的算法。字面上的解释是“分而治之”，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。这个技巧是很多高效算法的基础。
精髓：
分--将问题分解为规模更小的子问题;
治--将这些规模更小的子问题逐个击破;

合--将已解决的子问题合并，最终得出"母"问题的解;

设计思想及策略：
思想：将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。
策略：对于一个规模为n的问题，若该问题可以容易地解决（比如说规模n较小）则直接解决，否则将其分解为k个规模较小的子问题，这些子问题互相独立且与原问题形式相同，递归地解这些子问题，然后将各子问题的解合并得到原问题的解。这种算法设计策略叫做分治法。
如果原问题可分割成k个子问题，1<k≤n ，且这些子问题都可解并可利用这些子问题的解求出原问题的解，那么这种分治法就是可行的。由分治法产生的子问题往往是原问题的较小模式，这就为使用递归技术提供了方便。在这种情况下，反复应用分治手段，可以使子问题与原问题类型一致而其规模却不断缩小，最终使子问题缩小到很容易直接求出其解。

分治法的基本思想是将一个规模为n的问题分解为k个规模较小的子问题，这些子问题互相独立且与原问题相同。递归地解这些子问题，然后将各个子问题的解合并得到原问题的解。它的一般的算法设计模式如下：

divide-and-conquer(P)
{
if(|P|<=n0) adhoc(P);
divide P into smaller subinstances P1,P2,...,Pk;
for(i=1;i<=k;i++)
yi=divide-and-conquer(Pi);
return merge(y1,...,yk);
}
其中，|P|表示问题P的规模。n0为一阀值，表示当问题P的规模不超过n0时，问题已容