篇首语：本文由小编为大家整理，主要介绍了主定理相关的知识，希望对你有一定的参考价值。
《目录》
- 使用主定理求解递归式
- ? 算例 ?
- 证明主定理
使用主定理求解递归式
主定理是分治算法分析中非常重要的定理。
如，我们要处理一个 规模为 的问题通过分治，得到 个规模为 的问题，分解子问题和合并子问题的时间是 ：
在上面这个式子里，我们得要求 (如果 时，递推无意义)， 是渐进意义上的正数。
回顾一下， 和 的含义：
- 个子问题，即 是原问题分为子问题的个数；
- 每个子问题的规模是 ；
- 分治算法共三部分，分治合，而 就是分+合的时间。
和 ，向下取整和向上取整的细节，并不会影响主定理的推导，具体的数学证明，略。
如果对分治算法不熟悉，建议先看《递推式分析》。
而后呢，根据上面的式子我们会得到三种情况：
- 若有实数大于零()，，则 ；
- 若 ，则 ；
- 若有实数大于零()，，且有一个实数小于一()，使得较大的 ，满足 ，这时候则 。
这三种情况看起来很复杂，搞清楚他们之间的关系，快速记忆就简单了。
对于三种情况的每一种，我们将函数 与 比较，俩个函数较大者将决定递归式的解。
- 若函数 更大，如情况1，则解是 ；注意 小于 是渐进意义上的，要差一个因子量级 。
- 若函数 更大，如情况3，则解是 ；注意 大于 是渐进意义上的，要差一个因子量级 ，还要满足 ；
- 若俩个函数相等，如情况2，则乘上一个对数因子，解为 ；
- 上面的三种情况并未覆盖 的所有可能性，情况1、情况2 之间存在间隙， 可能小于 但不是多项式意义上的小于；情况2、情况3 之间也存在间隙， 可能大于 但不是多项式意义上的大于；若函数 在这俩个间隙中，或者是 情况3 中要求的 条件不成立，就不能使用主方法来解决递归式。
首先，得明白一个基准函数：。
有了基础函数之后，就可以根据 TA 来判定情形之间的关系。
那我们该如何记忆这个基准函数呢 ？？
原来的函数是：， 为底数，如果化为对数形式也是以 为底()；
原函数是一个多项式， 和 都是常数，算出来肯定也是一个具体的数值。
所以，我们要记这样一个基准多项式(基准函数)：，次方(即 )是取对数的。
接下来，是以上三种情况的判定：
- 是弱于基准的(渐进意义上)，；
- 是等于基准的(渐进意义上)，；
- 是强于基准的(渐进意义上)，。
? 算例 ?
算例1： (乐高铺积木)
分析，，基准函数是 ，因为 ，所以基准函数是 。
那 又是什么呢 ？？？
， 比基准函数 要弱，我们取一个实数() ，即 。
得到 .
算例2： (二分查找)
分析，，基准函数是 ，因为 ，所以基准函数是 。
那 又是什么呢 ？？？
，基准函数也是 ， = 基准函数，再乘上一个 ，即 。
算例3： (归并排序)
分析，，基准函数是 ，因为 ，所以基准函数是 。
那 又是什么呢 ？？？
，基准函数也是 ， = 基准函数，最后 。
算例4： (Strassen 算法)
分析，，基准函数是 ，大概是 。
那 又是什么呢 ？？？
，基准函数是 在这基础上减去 0.1 即俩者相等 ，最后 。
算例5： (摘自《算法导论》)
分析，，基准函数是 ，大概是 。
那 又是什么呢 ？？？
， 比 要强， (取 0.1 依然比 大)， 。
强的话，再看看是否满足 。
把 代入：。
得到 ， ，满足条件，因此 。
证明主定理
已经知道了基准(函数)怎么使用，可我们还不知道为什么会得到若干个渐进记号，我们会使用递归树来证明。
假设 ，每一次除以 ，除 次会为 1。
举个例子，
我们想知道的是，。
从上面的式子看出 ：
- 即基准函数；
- 注重的是 基准函数 和 的强弱关系；
- 是递归树的高度。
在递归树上证明时，我们写的简单些，直接把结点 f(m) 调用开销画上去。
- 第一层的代价是：；
- 第二层的代价是：；
- 第三层的代价是：；
- 负一层的代价是：。
整个递归树高度是 ，总的代价是：。
这些项会造成什么影响 ？
对于 的影响，我们要分析三种情况：
总个的表达式：
- 第一种情况：，，我们求的就是这个项 ：。
思考一下，我们能不能这个式子化为等比数列 ？
无关的项： 提出来，里面是 。
，，。
得出，。
- 第二种情况：，，我们求的就是这个项 ：。
把 提出来，里面是 。
，消掉后 这个求和就是对一求和，那是多少个一呢 ？
一共 个一，这个结果也等同于 。
- 第三种情况：，，我们求对就是这个项：
这个证明会麻烦一些，因为多了一个条件：。
形成一个 的等比数列，而 在里头保持不变，可以挪出来。
而这些等比数列最终加起来也不会超过 ，因此 乘的，也是一个常数项，总时间是 。
以上是关于主定理的主要内容，如果未能解决你的问题，请参考以下文章
