减而治之(Decrease and conquer)
什么是“减而治之”？
为求解一个大规模的问题，可以将其划分为两个问题，其一平凡，另一规模缩减 ，分别求解子问题，由子问题的解得原问题的解
比如说，对于一个数组A的求和问题，可以设计如下的算法
sum( int A[], int n ) {
return
n < 1?
0 : sum(A, n - 1) + A[n - 1];
}
当规模缩减到一定程度后，抵达递归基，返回0
复杂度分析
1. 递归跟踪
绘出计算过程中出现过的所有递归实例（及其调用关系） ，那么它们各自所需时间之总和，即为整体运行时间
上例中，共计n+1个递归实例(分析)，各自只需O(1)时间 故总体运行时间为：
T(n) =O(1) × (n+1) =O(n)
2.递推方程
对于大规模的问题、复杂的递归算法，递归跟踪不再适用 此时可采用另一抽象的方法…
在本例中，有T(n)=T(n-1) + O(1),T(0)=O(1)
则，T(n) = T(n-2)+O(2) = T(n-3)+O(3) = T(n-n)+O(n)=O(n)
可以看到，两种分析方法的出来复杂度都为O(n)
分而治之(Divide and conquer)
什么是“分而治之”？
为求解一个大问题，可以将其划分为若干子问题，规模大体相当（可理解为将大问题等分），分别求解子问题，由子问题的解得原问题的解
对于数组A的求和问题，利用分而治之的思想可以设计出下面的算法
sum( int A[], int lo, int hi ) {//区间范围A[lo, hi)
if ( hi - lo < 2 ) return A[lo];
int mi = (lo + hi) >> 1;
return sum( A, lo, mi ) + sum( A, mi, hi );
} //入口形式为sum( A, 0, n )
复杂度分析
1.递归跟踪
对于上述算法，分析可知，其复杂度
T(n)=O(1) × (1+2¹+2²+...+2^㏒n) = O(1) × (2^logn - 1) = O(n)
更快捷地，作为几何级数，其复杂度与末项同阶，因此由分析图可知，其末项共有n项[(0,0)，(1,1,) … (n,n)]，因此其复杂度为O(n)
2.递推方程
为求解sum(A,lo,hi),
需求解 sum(A, lo, mi) 和 sum(A, mi+1, hi) => T(n/2)
进而将子问题累加 =>O(1)
递归基sum(A, lo, lo) => O(1)
递推关系：T(n)=2·T(n/2) + O(1) ===> T(n) = O(n)