解递归式的三种方法
代数法
1.猜答案
2.呈现表达式
3.数学归纳法求解
例子如下：T(n) = 4T(n / 2) + n且T(1) = θ(1)
tip:容易猜错
递归树法
画出递归树，然后根据主观结论计算
例子如下：T(n) = T(n / 4) + T(n / 2) + n^2且T(1) = θ(1)
tip:不够严谨，没有证明
主方法
递归式符合T(n) = aT(n / b) +f(n)且a>=1，b>1(子问题要越来越小)，f(n)渐进趋正(对于n足够大，f(n)总是正的，即存在某特定n0当n>=n0时f(n)大于0)
主定理有三种情况，接下来会讲：
第一种情况
f(n) = O((n^logb(a) - ε))且ε > 0，则T(n) = θ(n^logb(a))
第二种情况
f(n) = θ(n^logb(a) * lgk * n)且k >= 0，则T(n) = θ(n^logb(a) * lg(k+1) * n)
第三种情况
f(n) = Ω(n^(logb(a) + ε))且ε > 0 & af(n / b) <= (1 - ε')f(n)即f(n)在递归中不断变小 且ε' > 0，则T(n) = θ(f(n))
证明
使用递归树法来证明三种情况
tip:限制颇多，有且仅有一个子问题
