1、第一种，代入法（数学归纳）
这里需要用到数学归纳法
对于递归式
T(n) = 4T(n/2) + n
函数增长：
当n乘2的时候，T将乘以4
先考虑求其渐进上界
猜测，为theta(n^3)的时候，满足情况
对k<n
T(k)<=ck^3 (T(k) ∈ O(n^3))
设置一个常量g(n)来替代ck^3 （ g(n) ∈ O(n^3)) ）
用数学归纳法证明：
1* T(1)=O(1)
T(1)=c =O(1)
2* 假设T(n/2) = O((n/2)^3) +n
3 T(n) = 1/2g(n) +n
= g(n) + (n – 1/2g(n))
后部为余项
n -1/2g(n) = n – cn^3 <0 (n>1)
∴ T(n) <= g(n)
= O(n^3) （非对称相等）
猜测，为theta(n^2)的时候，满足情况
同理 设置 g(n) = O(n^2)
用数学归纳法证明：
1* T(1)=O(1)
2* 假设T(n/2) = O((n/2)^2) + n
3 T(n) = 4T(n/2) +n
= g(n) +n
= g(n) – (-n)
(-n)为余项。此时无法证明-n为非负数
所以需要在原来的假设上进行改进
对T(k)进行更低阶的展开 以凑得一个非负的余项（想法：扩展系数到余项）
【注意这里使用了更强的归纳法，所以需要证明的结论更强了。
在归纳的时候需要归纳到的式子的主部已经变了。这里容易忽略】
对k<n
假设 T(k)<=c1*k^2 – c2*k (T(k) ∈ O(n^2))
即令g(n)=c1n^2 – c2n
T(n) = 4*T(n/2)+n
=4(c1(n/2)^2 – c2(n/2) +n)
=c1n^2 – (2c2 -4)n
=c1n^2 – c2n – (c2-1)*n n>0)
余项为(c2-1)*n
∴当c2-1>0即c2>1时
T(n)<=g(n)
=O(n^2)
对基本情况
为使T(1) = c1- c2 =O(1)成立
即 对于∀c2>1,Ec1>c2
∴c1需要足够大
综上所述，当c1足够大,c2>1,T(n)=O(n^2)
证毕
对于渐进下界Omega同理可证
所以有个很关键的地方，就是要进行合理的猜测。
可以通过经验猜测，也可以通过第二种方法递归树法来猜测
2、递归树法
这个方法不太严谨，但很常用（一般要通过代入法来证明）
ATT：
注意并理解递归树的画法（和式画法），理解递归式每一项的意义
理解非递归代价，递归代价，总代价。
对于式T(n)=aT(n/b)+f(n)中，f(n)即为非递归代价，n为当层规模，比如第3层所有结点的非递归代价和即为a^2 * f(n/b^3) ，单个结点的非递归代价为 f(n/b^3)。如果算上递归代价，就还需要计算该结点下递归子树的总代价。
f(n)不再递归，反应了该节点的非递归部分的代价。
aT(n/b)反应了函数增长，我们可以在其中看出横向增长(子问题数目）和递归规模（子问题规模）。
注意层数=高度+1 完全N叉树的叶节点=N^高度
网站上不方便画图emmm
所以，图略
分析递归树：
对于T(n)=cn^2+3T(n/4)
纵向分析：
子问题的规模为上一步的1/4
最终问题规模会到达1 （代价:T(1)）
深度为i的结点对应规模为 n/(4^i) 的子问题
所以当触底，子问题规模为1时 ，即 n/(4^i)=1， 递归树有log4(n)+1层（深度为0,1,2…log4(n)）
横向分析：
对于第i层，结点数为3^i
所以对于第i层的代价为 3^i * (n/(4^i))^2
所以对于最后一层，即i=log4(n)，代入即可得 最后一层的代价为 n^log4(3) * T(1)
T(1)为常数,n为常数
所以最后一层的代价为theta(n^log4(3))
经过以上分析，我们可以知道每一层的代价为一个等比级数，用等比级数求和公式即可求出整颗树的总代价。
由于有时候在表示渐进上界的时候并不需要如此严格(精确度不需要这么高），所以可以放缩为比较好处理的级数
3、主方法
主定理(master method)适用于一种形式的递归式
T(n)=aT(n/b)+f(n)
（公式比较复杂，等安装了插件之后再写数学表达式，网页不方便表示）
定理的证明：通过三个引理来证明
1*使用递归树求得代价公式（为一个等比级数和与叶结点代价和之和），
2*考虑f(n)的三种情况，在等比级数上进行变形，推导出简化渐进上界
3*将变形后的等比级数和所求得的简化渐进上界与原来的叶节点代价和相加，得到最终的渐进上界
（具体推导过程略，网站暂时上不方便写太多公式）
主定理对于快速求解非常重要，需要牢记结论
