分治的原理

当我们要求解一个数据规模为 n 且 n 取值又相当大的问题时，直接求解往往是非常困难的。如果在将这 n 个输入分成 k 个不同子集合的情况下，能得到k个不同的可分别求解的子问题，其中 1＜k ≤ n ，求出了这些子问题的解之后，还可找到适当的方法把它们合并成整个问题的解，那么，具备上述特性的问题可考虑使用分治策略求解。

1．分治的原理

所谓分治法就是将问题分而治之。有将问题一分为二，也有将问题一分为三或一分为N等份。对每一等份分别进行解决后，原问题就可以很快得以解决。因此一个问题能否用分治法解决，关键是看该问题是否能将原问题分成n个规模较小而结构与原问题相似的子问题。递归地解决这些子问题，然后合并其结果就得到原问题的解。当 n=2 时的分治法又称二分法。

2．分治的步骤

(1)分解(divide)：将原问题分成一系列子问题。

(2)解决(conquer)：递归地解各子问题。若子问题足够小，则可直接求解。

(3)合并(combine)：将子问题的结果合并成原问题的解。

3．分治的具体过程

使用分治策略的问题常常要借助递归结构，逐层求解，当问题规模达到某个简单情况时，解容易直接得出，而不必继续分解。 其框架如下：

if 问题不可分 then
    begin
        直接求解；
        返回问题的解；
    end
else
    begin
        从原问题中划出含1/n运算对象的子问题1；
        递归调用分治过程，求出解1；
        从原问题中划出含1/n运算对象的子问题2；
        递归调用分治过程，求出解2；
        …………
        从原问题中划出含1/n运算对象的子问题n；
        递归调用分治法过程，求出解n；
        将解1、解2、……、解n组合成整个问题的解；
    end;

由此我们可以看出，分治算法的时间是这样确定的：解决子问题所需的工作总量（由子问题的个数、解决每个子问题的工作量决定），合并所有子问题所需的工作量。

典型例子：qsort( ) ,快速排序