这一讲介绍主定理的应用。我们先看看求解递推
方程的例子。这是一个递推方程，它满足主定理的
函数的要求。这个9是a，这个3是b，
我们就可以用主定理来求解这个方程。首先我们看到把它的条件
分析一下。a等于9，b等于3，fn呢就正好是n， 计算一下，n的log以b为里的a，
就是log以3为里的9，正好是n平方，而这个fn呢是n的一次方， 一次方和n平方来相比，
它比它低一个n的一次方，这个时候取ε等于1就可以了。
所以它满足主定理的第一种情况和条件。
就可以得到它的解就是n平方，就是这个 n的log以b为底的a，这是第一个结果。
下边我们看看第二个方程，这个方程呢，它也是 主定理所满足的这个方程格式。
可以考虑用主定理来求解，分析一下，在这个方程中a是1，
b是2分之3，fn是1，那计算一下n的log以b为底
的a，就是log2分之3为底的1， 那这个情况呢，正好是n的0次方等于1，和fn同阶。
同阶呢，它正好满足主定理的第二种情况， 它的解就是用这个函数乘以logn，
就是等于logn。下边我们看看第三个例子。
这个例子呢是，也是a是3，b是4，然后这个是函数fn，
它也满足主定理的条件， 我们具体的解应该由这几个参数来决定。
先看看a等于3，b等于4，这是f函数，是nlogn，
log以b为底的
a就是log以4为底的3，n的log以b为底的a加上ε，
正好是n的log以4为底的3呢，log以4为底的3呢是0.793。
不到1，比1小。那在这个情况下，我们取ε等于0.2，
这个才是n的0.993，还比n的1次方要低。
所以满足这个主定理的第三个条件，就是这个函数nlogn， 存在的这个ε等于0.2，使得
n的log以4为底的3，加上ε，作为nlogn的下阶。
这样根据主定理的第三种情况我们就可以知道 这个算法的解可以计算出来。
除了这个条件以外还有第二个条件，就是那个不等式的验证。下边我们就
来看看是不是还满足那个不等式的验证，只有满足了不等式的验证，
我们才可以用主定理的第三个结果。
要使得这个不等式成立，我们带入f函数。
f函数呢是nlogn，这个b呢是4，a是3， 所以带入是f
b分之n，就是4分之n，log4分之n， 这是a，正好是左部，右半部呢，就是cnlogn，
要使得这个不等式成立，我们来看看存不存在这样的c？
这里边只要c大于4分之3就可以了，因为这个左边化简了是4分之3
乘以log4分之n，而右边化简了，如果c要是等于4分之3的话，
它正好是4分之3乘以logn，已经大于等于左边了。我们只要取一个
大于等于4分之3的这样一个c，要求它小于1，那就取4分之3就可以了。
所以只要c取成4分之3，上面的这个不等式就可以对所有充分大的n都成立，
这就相当于主定理的第三种情况，两个条件都满足了 我们就可以计算出来方程的解就是nlogn。
这是第三个例子。
下边我们看到具体的一些算法分析的例子。这个是二分检索算法。
根据这个算法呢，我们可以知道a等于1，b等于2，
n的log以b为底的a呢，正好是常数1，跟fn是同阶的。
主定理的第二种情况满足，所有它的解呢就是logn。
这就比迭代要方便的多了，我们直接可以计算出算法的时间
复杂度。二分归并排序也是满足主定理的一个方程。
对于这个方程来讲，它里边的a是2，b是2， 那么n的log以b为底的a呢，正好是n，
和这个函数，和这个fn这个函数是同阶的 函数，同阶的函数呢，这个情况下
它正好还是主定理的第二种情况，这个解就是nlogn。
因此我们也可以不迭代直接用主定理求解。
下边看一个不能使用主定理的例子。
观察一下这个方程，这个方程a和b都是2，
n的log以b为底的a呢正好是n的一次方，
fn呢是nlogn，看起来nlogn比这个n
阶要高，但是它高的是一个logn函数， 它并没有高一个n的ε次方。
因为我们都知道幂函数，n的ε次方，比这个logn函数
要增长的快，它不是同一个层次的函数。
下边我们看到，就是说对于这个就不成立了。
就是你找不到n的1加ε次方这样一个函数
可以作为它的下阶，因为n的ε不管这个ε多小，
它都要比logn函数要增长的快，就是在n充分大的时候，
所以这个条件就不成立了。那就是说主定理
在第三种情况下的这个条件不成立。
下边我们再看一下，这个不等式这个条件怎么样呢？
有没有这样的c小于1，使得这个不等式成立呢？ 我们来观察一下。
先把左边带入这个函数，它应该是2倍的2分之n乘以
log2分之n，这个函数化简以后是nlogn减1，
而右边这个cfn呢是cnlogn， 那么把这两个函数比较一下，这个c呢。
要求是小于1的，如果要小于1的话，
这个大于等于号，这个符号就不成立了。因为这个小于等于1的话，这个可能是零点几
的n乘logn，不可能对所有充分大的n。都比左边这个n乘logn减1要大。
好，所以这个不等式呢，也找不到c使得它成立。
在这样的条件下，两个条件都不成立，
肯定不能使用主定理的结果，所以这个方程的解
不能够用主定理来求，怎么办呢？我们 可以考虑用递归树，按照递归树的生成，根
就是它那个nlogn，然后左边是二分之n子问题的解。
这也是2分之n子问题的解，那就是再经过一步迭代，
把这个地方用2分之n带进来以后就是左边这个函数。
把它这个n用2分之n带进来就是这个函数。
这是第二层的两个节点。然后再下一层呢， 把这个n要是用它的2分之n带进来就是这个结果
和这个结果，这个也是。这就是不断地生长这棵树的过程。
生长完了以后呢我们可以看到这个结果。
这个第一行是nlogn， 第二行这两个加起来是n乘以logn减1，
第三行这四项加起来是n乘以logn减2， 那么这样一直下去最后是n乘logn减掉
k减1，就是减k加1，这就是它的这样的每一行的值。
然后把这些个值全部加起来就是递归树上所有量的和也就是方程的解。
把刚才那些个值都列到这，这是根，这是第一
层的，第二层的，一直到最后一层的。把这些个都加起来
我们发现nlogn会出现多少次呢？出现
logn次，就是它出现logn次，所以把这些个
正好是k乘吧，k就是logn了，所以它 一共是nlogn再乘logn次，就是n乘logn平方，
然后后边的这些个项，这地方出现一倍的n，这地方出现两倍的n，
这地方出现k减1减掉k减1再乘一倍的n，所以把这个n拿出来，
这多个1，这多个2，最后一项多出一个k减1，
这正好是等差数列的和。
把这个和计算出来，它就应该等于2分之k乘k减1。这是对这个数列求和的结果。
求和的结果以后，然后把这项的k用
跟n，用n来替回去，因为n是等于2的k次方了，所以这样替回去以后呢，
正好化简的结果应该是2分之1的n乘log n平方。一倍的n乘logn平方再减掉2分之1的呢，最后
还剩一个2分之1的n乘logn平方，也就是大On乘logn平方。
因为2分之1那个常数呢是不重要的。
这一讲呢主要介绍了主定理来求解 递推方程，给出了一些应用的例子。
在主定理求解递推方程的时候，很重要的是判定它的条件。
因为主定理的解有三种可能的情况，这个条件判定很重要。
另外我们用一些具体的例子看到了怎么样用主定理 来做算法复杂度的分析。
Wanling QuProfessor
