分治法分为三个步骤：
Divide - 将一个问题拆分成若干个子问题（规模更小）
Conquer - 通过递归的方法分别解决第一步中的每个子问题
Combine - 将各个子问题的结果合并起来得到整个问题的结果
典型的分治法算法
归并排序（Merge sort之前介绍过）
T(n) = 2T(n/2) + n | 满足主定理Case2
=》T(n) = Θ(nlgn)二分查找（Binary search）
在一个已经排序的数组中找到x
把x于数组的中间节点比较，有三种结果：
1.x=middle，返回结果
2.x<middle，左半边数组进行递归查找
3.x>middle，同理右半边数组进行递归查找
T(n) = T(n/2) + Θ(1) =》 T(n) = Θ(lgn)乘方问题（Power the number
给定x，n>0，求解xn
if n是偶数，xn = xn/2 * xn/2
if n是基数，xn = x(n-1)/2 * x(n-1)/2 * x
T(n) = T(n/2) + Θ(1) =》 T(n) = Θ(lgn)-
斐波那契数列
0 1 1 2 3 5 8 13 ...
朴素算法：Fn = Fn-1 + Fn-2
算法效率为Ω(φn)，指数级别的，递归子问题的规模没有明显减小，并且又重复计算的部分
自底向上算法：计算 0 1 1 2 3 5... 直到Fn
避免了重复计算，算法效率提高到了Θ(n)
递归平方算法：
定理
问题的求解即成为了矩阵的乘方问题，算法效率于是提高到了Θ(lgn)
-
矩阵乘法nxn阶矩阵
有两个矩阵A[ij]、B[ij]，求解C=A*B
Cij=Σ(Aik * Bkj) | k <- 1 to n
朴素算法：需要三层循环(i\j\k分别从1到n循环计算，见文末补充)，算法的效率为Θ(n3)
分治算法：将矩阵分成四个相同大小
分解矩阵
r=ae+gb
s=af+bh
t=ce+dg
u=cf+dh
T(n) = 8T(n/2) + Θ(n2) | 分成递归八个乘法，每个小问题是原来的1/2，加上4次矩阵加法运算
=> T(n) = Θ(n3) 效率并没有提高
Strassen算法:
主定理方法可知必须想办法将2中递归式中的系数8减少。Strassen提出了一种将系数减少到7（log27<3）的分治法方案
P1=a(f-h)
P2=(a+b)h
P3=(c+d)e
P4=d(g-e)
P5=(a+d)(e+h)
P6=(b-d)(g+h)
P7=(a-c)(e+f)
r=P5+P4-P2+P6
s=P1+P2
t=P3+P4
u=P5+P1-P3-P7
问题转变成递归7次乘法和18次加减法
T(n) = 7T(n/2) + Θ(n2) =》 T(n) = Θ(nlg7) = Θ(n2.81)
效率提高，并且因为是指数级增长，当n更大时提升效率明显
～现在理论上矩阵乘法的效率最好的是：Θ(n^2.376…)。但是在这众多的优化算法中，Strassen算法却是最简单的～
补充：矩阵乘法nxn阶矩阵朴素算法
for i ← 1 to n
do for j ← 1 to n
do c[i][j] ← 0
for k ← 1 to n
do c[i][j] ← c[i][j] + a[i][k]⋅ b[k][j]
