目录：

一、何为递归式

二、求解递归式的三种方法简介

三、如何使用主定理求解递归式

四、主定理的证明

五、参考

一、何为递归式

递归式是形如T(n)=aT(n/b)+f(n)的一种分解形式，其中a>=1,b>1,f(n)是渐进正函数，该递归式描述的是这样一种算法的运行时间：它将规模为n的问题分解为a个子问题，每个子问题规模为n/b，a个子问题递归地进行求解，每个花费时间T(n/b)。函数f(n)包含了问题分解和子问题解合并的代价。[1]

二、求解递归式的三种方法简介

求解递归式的方法主要有三种：1、代入法；2、递归树方法；3、主定理（The master theorem）

其中代入法求解递归式需要先猜测出递归式的解，然后用归纳法证明其正确性，这需要解题的经验和直觉，希望你拥有这种能力。用递归树方法求解递归式应该是一种相当好的方法，它可以帮助我们快速准确的猜测递归式的解，它也是证明主定理的基础。主定理则为我们总结好了直接得出递归式解的方法，如果你只想知道递归式的解，那么直接使用它就行了，这样它的证明也就不用看了。当然，能使用它是重点。

三、如何使用主定理求解递归式

先给出使用主定理得出递归式的解的不考虑特殊情况的方法，这能使我们能快速的求出递归式的解。

首先判断f(n)和n^(logb^a)的关系：

1、 如果f(n)则T(n)=O(n^(logb^a))

2、 如果f(n)=n^(logb^a)则T(n)=O(n^(logb^a)lgn)

3、 如果f(n)>n^(logb^a)则T(n)=f(n)

我们先来试验一下：

例如：T(n)=9T(n/3)+n

那么f(n)=n，n^(logb^a)=n^(log3^9)=n^2，前者小于后者，因此符合第一种情况，故T(n)=O(n^2)，也就是说该递归式的时间复杂度为O(n^2)

例如：T(n)=T(2n/3)+1

那么f(n)=1，n^(log(3/2)^1)=n^0=1，两者相等，因此符合第二种情况，故T(n)=O(n^(logb^a)lgn)=O(nlgn)

例如：T(n)=3T(n/4)+nlgn

那么f(n)=nlgn，n^(log4^3)=n^0.793，前者大于后者，因此符合第三种情况，故T(n)=f(n)=O(nlgn)

对于一般的递归式的解我们可以大胆的使用这种简化版的主定理来求，但是科学即具有严谨性，如果我们想要准确的求出任何递归式的解，那么就需要使用严谨的主定理：

a≥1，b>1为常数，f(n) 为函数，T(n) 为非负整数。则有以下结果（分类讨论）：

1、若对于常数ε>0有f(n)((logb^a)-ε)则T(n)=O(n^(logb^a))

2、如果f(n)=n^(logb^a)则T(n)=O(n^(logb^a)lgn)

3、若对于常数ε>0有f(n)>n^(logb^a+ε)，且对于某个常数c<1和足够大的n有af(n/b)<=cf(n),则T(n)=f(n)

对于准确的主定理来说，我们还需要注意一些细节:我们不仅仅是直接判断f(n)和n^(logb^a)的关系，而是要判断f(n)和n^(logb^a)是不是相差n^ε，也就是说两者相差的是不是一个多项式意义上的差值。举例来说：

对于：T(n)=2T(n/2)+nlgn

那么f(n)=nlgn，n^(log(2)^2)=n，前者小于后者，但是它不是严格意义上符合第三种情况，因为nlgn和n相差lgn，不是多项式意义上的小于，因此它不符合主定理的第三种情况。

四、主定理的证明

再列一次主定理的三种情况：

a≥1，b>1为常数，f(n) 为函数，T(n) 为非负整数。则有以下结果（分类讨论）：

1、若对于常数ε>0有f(n)((logb^a)-ε)则T(n)=O(n^(logb^a))

2、如果f(n)=n^(logb^a)则T(n)=O(n^(logb^a)lgn)

3、若对于常数ε>0有f(n)>n^(logb^a+ε)，且对于某个常数c<1和足够大的n有af(n/b)<=cf(n),则T(n)=f(n)

对于T(n)=aT(n/b)+f(n)形式的递归式，我们先讨论n是b的幂的情况：根据递归式画出递归树：

 因此：

令:

则对于第一种情况：

我们可以求得:

由于b和ε都是常数，因此g(n)=O(n^(logb^a))，此时T(n)前一部分是紧确到的n^(logb^a)，因此T(n)=n^(logb^a)，故第一种情况得证。

第二、三种情况类似，分别求出g(n)的值，带入即可。

对于n非b的幂的情况和这种情况证明相似。

对于主定理的直观理解：第一种情况相当于递归树的总代价是由叶子结点的总代价决定的；第二种情况相当于递归树的总代价均匀分布在各层；第三种情况相当于递归树的总代价是由根结点的总代价决定的。

五、参考

1、《算法导论》第三版