主定理（master theorem）
在前面讲到的Big-Oh算法复杂度分析的文章时，我曾经提到过主定理，既然主定理是奠定算法分析尤其是递归算法的理论基石，那么就有必要拿出来单独讲一讲，即使我们是属于拿来主义的工程派，理解使用工具的理论根据也是有益无害的吧？当然在最后我们会总结几个工程常用的分析算法复杂度的例子。
什么是主定理
主定理来源于算法导论，是在第四章介绍分治法时适时引出的。
wikipedia这样说
主定理的描述是这样的：
令$a \geq 1$, $b > 1$的常数， $f(n)$为一个函数， $T(n)$的递归定义式如下：
$$T(n) = aT(n/b) + f(n)$$,
这里我们解释$n/b$为 $n/b$的最近的整数，即向上取整或者是向下取整。
那么我们根据$f(n)$的情况会有下面三个$T(n)$的函数渐进边界。
- 如果存在常数$\varepsilon$ $f(n) = O(n^{log_b^{a-\varepsilon}})$ 我们有
$$T(n) = \Theta(n^{log_b^a})$$ - 如果 $f(n) = \Theta(n^{log_b^a})$， 那么我们有
$$T(n) = \Theta(n^{log_b^a}lg^n)$$ - 如果存在常数$\varepsilon$使得 $f(n) = \Omega(n^{log_b^{a+\varepsilon}})$， 并且如果存在常数 $c < 1$ 以及当$n$足够大的时候，使得 $af(n/b) \leq cf(n)$
注意到定理中讨论的情况其实有个关键的分割点是讨论 $f(n)$ 与 $n^{log_b^a}$ 的大小关系。
第一种情况其实是$f(n)$小于 $n^{log_b^a}$的情况
第二种情况是等于的情况
第三种情况是大于的情况
用主定理搞事情
首先是
二分查找
由于是已经排好序的列表，二分查找在算法描述上实际上是在查找的时候将原问题（在长度为n的列表查找）分解为通过比较pivot的大小（操作复杂度$O(1)$）转化为一个更小的子问题（在长度为n/2的列表查找），很自然的我们有二分查找的递归表达式$$T(n) = T(n/2) + O(1)$$
下面我们使用主定理，首先看下$f(n)$ 实际上$f(n) = O(n^0)$, 其次我们看下$a = 1, b = 2$ $log_2^1 = 0$ 也就是 第二种等于的情况，因此我们有 $T(n) = O(n^{log_2^1}log^n) = O(log^n)$
归并排序
从归并算法的描述来看，选择pivot后将原问题（长度为n的排序问题）转化为 两个长度为$n/2$的子问题，和一个两个排好序的列表的合并问题（时间复杂度为：$O(n)$）。自然地我们有归并排序的递归表达式为 $$T(n) = 2T(n/2) + O(n)$$
下面我们使用主定理， 首先$f(n)=O(n^1)$ ， $a = 2, b = 2$ $log_2^2 = 1$ 也就是第二种等于的情况， 因此我们有 $T(n) = O(n^{log_2^2}log^n) = O(nlog^n)$
二叉树遍历
从算法描述上看，二叉树遍历实际是将一整棵二叉树遍历问题分解为分别遍历左子树($O(n/2)$)，右子树($O(n/2)$)，以及根节点（$O(1)$）的子问题，因此递归表达式为$$T(n) = 2T(n/2) + O(1)$$
下面我们使用主定理， 首先$f(n) = O(n^0)$， $a =2, b = 2$ $log_2^2 = 1$ 也就是第一种情况，因此我们有$$T(n) = O(n^{log_2^2}) = O(n)$$
