主定理的定义
分治法的三个步骤是：分、治、合，时间复杂度 容易用递推式表示。
递推式的求解有三种方法：代入法、递归树法和主定理。主定理是一种无脑推导的求解方法。对应的一般递推式形如
其中各参赛的含义：
-
：把原问题分解为 个子问题，
-
：每个子问题的规模是原问题的 ，所以 ，但 不一定是整数。
-
：分与合所花费的时间
主定理的三种情况
-
若存在常数 使得 ，则 。
-
若 ，则 。
-
若存在常数 使得 ，且满足正则条件（存在常数 有 ），则 。
这是书上对主定理的准确描述。用容易理解的方法，就是用 和 基准 进行比较。基准就是 ，记住是以就是递推式中的分子为底。
-
若 弱于 基准，那么结果就等于基准，即 ；
-
若 等于基准，结果就是基准乘以 ，即 ；
-
若 强于基准，结果就以 为主，即 ；
这里的强弱关系不是普通的大于和小于，而是多项式意义上的大于和小于。
使用主定理
练习 4.5-1-a
基准为 ，，显然对应的是情况 1， 弱于基准。
只要取 ，
所以 。
练习 4.5-1-b
对应情况 2， 等于基准，所以 。
练习 4.5-1-c
，对应的是情况 3。这个时候还有检验正则条件。
故存在这样的 ， 使条件成立，所以满足情况 3， 。
练习 4.5-1-d
对应的也是情况 3，直接检验正则条件：
满足正则条件，故 。
练习 4.5-3
基准为 ，初看 强于基准，应检验正则条件：
最后一步因为当 时 ，所以 ，不满足正则条件的 的要求。所以本题不能用主定理。解的形式见习题 4.6-2。
证明主定理
其实会使用主定理其实就够了，证明的思路有利于帮助我们理解和记忆主定理。
首先分析递推式
为了方便，只证明原命题的一个子集：，也就是 是 的幂，其中 、、 都是正整数。
画出递归树，那么递归树的高度为 ，深度为 的节点的代价和为 。
主定理递归树
那么总代价
其中 为叶子节点的代价， 为其他内部节点的代价。
分析内部节点的代价
对应主定理的三种情况， 有三种渐近界。
情况 1，若存在常数 使得 ，推出 ，所以 。
情况2，，每一层和都是 ，一共有 层，推出 。
情况3，，则 ，得到 。
总结
主定理在于记忆和使用，递推式 ，比较基准 与 的大小，较大的为递推式的解，如果一样大，那就要再乘以一个 。要注意的有：
-
基准 底对应的是分母。
-
这里的大小比较是多项式意义上的大小，可以理解为比较的是“无穷大的阶”。
-
主定理适用于大部分情况，但也例外，特别是注意正则性条件。
网友评论