分治法的设计思想

        分治者，分而治之也①.分治法（divide and conquer method)将一个难以直接解决的大问题划分成一些规模较小的子问题，分别求解各个子问题，再合并子问题的解得到原问题的解。一般来说，分治法的求解过程由以下三个阶段组成： （1)划分：把规模为n的原问题划分为k个（通常k=2)规模较小的子问题。 

（2)求解子问题：各子问题的解法与原问题的解法通常是相同的，可以用递归的方法求解各个子问题，有时递归处理也可以用循环来实现。

（3)合并：把各个子问题的解合并起来，合并的代价因情况不同有很大差异，分治算法的效率很大程度上依赖于合并的实现。         人们从大量实践中发现，在用分治法设计算法时，最好使子问题的规模大致相同。也就是将一个问题划分成规模相等的k个子问题，这种使子问题规模大致相等的做法是出自一种平衡子问题（balancing sub-problem)的启发式思想，它几乎总是比子问题规模不等的做法要好。另外，在用分治法设计算法时，最好使各子问题之间相互独立，这涉及分治法的效率，如果各子问题不是独立的，则分治法需要重复求解重叠的子问题，此时虽然也可以用分治法，但一般用动态规划法较好。下图所示是分治法的典型情况。

【问题】运用分治法求解一维数组求和问题

输入：待求和数列a[ ]，待求和区间[l,r]

输出：a[l]至a[r]的和

求解步骤：

（1）划分：

        取待处理区间的中间坐标m=(l+r)/2

        原问题即划分为两个区间[l,m],[m+1,r]

(2)求解：

        对前半个区间求和得到lsum

        对后半个区间求和得到rsum

（3）合并：

        合并两个子问题的解 SUM=lsum+rsum

【算法描述】

输入：待求和数列a[ ]，待求和区间[l,r]

输出：a[l]至a[r]的和

过程：divideSum(int a[],int l,int r)

1.如果l==r,表示求和区间只有一个元素，返回该数据，算法结束；

2.计算划分中点：m=(l+r)/2

3.调用divideSum( a ,  l , m )，求得前半区间的和lsum;

4.调用divideSum( a ,  m+1 , r )，求得后半区间的和rsum;

5.SUM=lsum+rsum,得到原问题的解，返回该值，算法结束。

【算法分析】

设待求和的个数为n

时间复杂度：O(n)

 n/2表示问题规模为n\2，2T（n/2）表示有两个规模为n\2的子问题，+1表示最后的合并

【算法实现】

C语言代码如下：

输出结果：