对分治策略的分析见文章[递归分析]http://aisakaki.com/?p=406
1、分解（分）
2、解决（治）
3、合并
一些使用分治策略的算法
①归并排序
T(n)=2T(n/2)+Θ(n)
2为子问题数目，n/2为子问题规模，Θ(n)为附加计算量（分治法运行时间）
通过主定理case2，可以得到其T(n)=O(nlgn)
②二分查找
分：二分
治：比较。只在一个子数组中递归
T(n)=1*T(n/2)+Θ(1)
1个子问题
③乘方问题
求x^n
如果用朴素方法，那么T(n)=O(n)
如果采用分治策略，那么T(n)=T(n/2)+Θ(1)=O(lgn) (master method) <O(n)
*注意奇偶n的处理，但其递归式不变
只有一个子问题，画递归树的话就是一条链
④非不拉几数列
Fn=Fn-1 + Fn-2 if n>=2
Fn=0 if n=0
Fn=1 if n=1
1*若采用朴素的递归方式，不停计算Fn-1,Fn-2,触底就返回，那么
T(n)=Ω(φ^n) φ=(1+√5)/2 （φ为黄金比例，神奇）
子问题的规模仅仅缩小到了n-1，递归树非常庞大
复杂度为指数级，代价很高，所以此种方法不好。
最理想的算法复杂度为多项式级
2*事实上，在建立非不拉几递归树的时候，会发现很多公共子树，这些子树重复计算，产生了大量冗余。
如果考虑从底向上计算（线性。依次计算F(1),F(2),F(3),….)，那么其复杂度会是O(n)
3*有一个更简单的办法（数学），F(n)=φ^n/√5并取整至最接近的整数，复杂度即为③中的问题，为O(lgn)
由于φ为浮点数，所以这样不精确且对运算要求极高，在现有机器上无法运行
4*第二种数学方法
Fn-1 Fn = 1 1 ^n
Fn Fn-2 = 1 0
（左右皆为矩阵，右边是矩阵的n次幂，待安装数学公式插件再修改）
证明：数学归纳法。比较简单，证略。
其复杂度为O(lgn)
⑤矩阵乘法
朴素方法：三层循环，i对应左行，j对应右列，k对应遍历每个元素。T(n)=O(n^3)
分治方法1：
利用分块矩阵，将母矩阵变成2*2的矩阵
A= A11 A12
A21 A22
B=B11 B12
B21 B22
C=C11 C12
C21 C22
由此可以写得四个表达式
c11=A11B11 + A12B21
C12=A11B12+A12B22
C21=A21B11+A22B22
C22=A21B12+A22B22
由此可得每次递归需要将有八个递归子问题（乘），并加上4次矩阵加法时间
（8个规模为n/2的矩阵乘法（递归）和4个规模为n/2（即合并起来为一个规模为n）的矩阵加法（非递归，常数）
所以其递归表达式为 T(n)=8T(n/2)+Θ(n^2)
由主定理得，T(n)=Θ(n^3)
此方法效率依然很低，和朴素方法没什么区别。
思考：为什么效率低？
因为矩阵乘法是Θ(n^3)级复杂度，而一次递归将产生8个子问题，每个子问题皆矩阵乘法
而矩阵加法是Θ(n^2)级复杂度。所以为了使递归树变小，我们应尽量减少矩阵乘法，多做矩阵加法。
比如，一次递归产生8个子矩阵乘法问题，递归树太“茂盛”了，我们能否减小到7个？
通过这种思考下去，就想到了第二种方法
分治方法2：Strassen方法
该算法具体内容见https://blog.csdn.net/qwertyuer/article/details/44255087
该算法下，T(n)=7T(n/2)+Θ(n^2)=Θ(n^lg7)<Θ(n^3)
分：将AB 矩阵分为8个子矩阵
治：中间计算过程
合：将子问题的解合并为原问题的解
未完待续
