用主方法求解递归式

主方法为如下形式的递归式提供了一种“菜谱”式的求解方法，如下所示

其中a≥1和b>1是常数，f(n)是渐近正函数。为了使用主方法，需要牢记三种情况，但随后你就可以很容易地求解很多递归式，通常不需要纸和笔的版主。

  主方法依赖于下面的定理

  定理4.1(主定理)    令a≥1和b>1是常数，f(n)是一个函数，T(n)是定义在非负整数上的递归式：

  那么T(n)有如下渐近界：

主定理不能适合于这样的递归式：T(n)=2T(n/2)+nlgn，因为该递归式落入了情况2和情况3之间的间隙。

例子：

T(n) = 9T(n/3) + n

满足第一点：所以T(n) = O(n^2)

例二：

T(n) = T(2n/3) + 1

满足第二点,所以 T(n) = O(lgn)

例三：

T(n) = 3T(n/4)+n*lgn

满足第三点，所以T(n) = n*lgn