递归式分治法总结
一、递归式介绍
分治法其实在很多地方都会看到，比如归并排序、快速排序等都是运用分治法解决。
而每个分治法问题通常都能够用“递归式”表示。
比如归并排序的递归式如下：
当然一般的书中通常都会写成：
这样写的原因是简化思想，即后一种表示假设“n是2的幂次”。并且这两种表示的结果都是一样的。
递归式要注意：一定不要忘了边界条件，即n=1时的T(1)值，虽然通常来说T(1)=1。
递归式的性质：
现在我们来证明这个结论：第一个递归式和第二个递归式的结果一样。
第二个递归式通过主定理就能够得出，因此不证明了。
第一个递归式我们用代换法验证。
第一步：证明T(n)=O(nlgn)
 |
第二步是证明T(n)=Ω(nlgn)
 |
因此得证。
递归式的三种解法：
(1)Substitution Method：主要用于验证假设的解是否正确。（注意要证明边界条件）
(2)Recursive Tree：用于估算递归式的解。
(3)Master Method：用于解一些简单的递归式的解。（主定理的证明是用递归树证明的，可以不必深究）
通常：简单的递归式用主定理做，烦的递归式先用递归树估计，再用代换法验证。
递归树因为比较简单，因此这里不做讲解。
主定理我就简单的列出公式：
注意：在(1)、(2)、(3)之间是有空隙的。
比如当出现：T(n)=2T(n/2)+nlgn时就不能使用第三种情况，因为f(n)=nlgn，他不是多项式大于n，因此不是第三种情况，但是能用第二种情况。
接下来我们举一个例子来更明确怎么解递归式。（出自算法导论4-4(f)）
二、分治法介绍
定义：将原问题分解为多个独立的子问题，分别进行求解，且子问题的形式和原问题一致，只是规模减少了。
分治法一个比较容易遗忘的是：Base case，即什么时候递归，而什么时候停止。比如BinarySearch的Base case是p<=q，当开始位置大于结束位置时就停止。
分治法的三个步骤：
(1)Divide：将原问题分解为多个子问题。
(2)Conquer：对子问题递归求解。
(3)Combine：将子问题合并为原问题的解。
比如归并排序：
Divide步骤是 m=(p+q)/2
Conquer步骤是 merge_sort (A,p,m)和merge_sort(A,m+1,q)
Combine步骤是merge(A,p,m,q)
比如二分查找：
Divide步骤是 m= (p+q)/2
Conquer步骤是BinarySearch(A,p,m-1)或BinarySearch(A,m+1,q)
Combine步骤是NIL。
而假设Divide需要f(n)时间，Combine需要g(n)时间，分解为a个大小为n/b的子问题，则递归式表示为：T(n)=aT(n/b)+f(n)+g(n)
最后给出一个分治法的例子：
问题：给定一个大小为n的数组，且数组的数据分布为先上升再下降，即一开始数据是严格增大的，后来数据是严格下降的，我们需要用O(lgn)查找到数组中的最大值。
思路：每次在数组中央取两个数a和b，如果a<b，则说明还处在上升阶段，则最大值在A[b...n]中；如果a>b，则说明已经在下降阶段，则最大值在A[1...a]。
伪代码：
