深入浅出理解主定理原理(Master theorem)如何计算递归时间复杂度

缘起

网络上有很多关于主定理的文章, 其中很多都是到了如何使用就算完事了. 但是主定理本身看起来却有些繁琐. 毕竟一个定理还分三条, 还有一些条件.
其实主定理背后的思想非常简单;
背公式总是痛苦的, 若能理解, 那么便可以长久记忆下来.

本文章不会出现主定理证明. 但是需要读者了解递归, 分治, 渐进符号.
非常建议你拿着草稿纸，想不明白就跟着我写一写。本文尽量不提非必要的数学公式，不提证明。

好,为什么用主定理?

(如果你只想看原理, 点我跳到原理)

主定理, 简单的说就是用来快速计算存在递归的分治算法时间复杂度的一套公式.

首先我们需要一个递归关系式, 大概长这样

$T(n)=aT(n/2)+f(n)$, 有条件哦, $a,b \geq 1$ 并且是常数.

我们先来看一个例子, 我相信你知道归并排序(MergeSort).

总体说一下这个算法:
1.总共有n个元素
2.我们每次把一个数组拆成两个小数组(a=2), 每个大小约为原来一半(n/2, 故b=2)
3.我们会对当前得到的, 已经被排序过的两个n/2的数组拿回来, 所以要对n/2 *2也就是n个元素进行处理.

于是我们可以轻松得到归并排序的关系式:
(我建议你找笔和纸出来写一下再看答案)

$T(n)=2T(n/2)+n$

如果我们不使用主定理

通常情况下, 我们需要代入公式. 你可以画个递归树, 我们总共会递归下去$\log n$次

$T(n)=2T(n/2)+n=2(2T((n/2)/2)+n/2)+n$

一直代入下去, 再整理一下,

$T(n)=n+2(n/2+2(n/4+\cdots+n/2^{\log_2n}))\cdots)$

$T(n)=n+2^{\log n}\frac{n\cdot \log n}{2^{\log n}}$, 约去$2^{\log n}$, 结果是$T(n)=n+n\log n=\mathbb{O}(n\log n)$. 不难理解, 因为这里有$\log n$层, 每层都是n, 所以就是$\log n$乘n.

不使用主定理的情况下, 我们需要使用数学工具. 归并排序在这个情况下不算特别麻烦. 后面我会提到正常情况下不使用主定理如何处理.

那我们使用主定理呢?

首先确定一下$f(n)=\Theta(n^{\log_b a})=\Theta(n^{\log_2 2})=\Theta(n)$
好, 符合第二种情况, 直接套公式:$T(n)=O(n^{\log_b a}\cdot \log(n))=O(n\log n)$
(别急, 马上我们就看什么是第二种情况)

使用主定理, 快, 并且简单.

如何理解主定理

先搬出我们的主定理吧.

1.如果$f(n)=O(n^{\log_b (a)-\epsilon})$, 若存在$\epsilon >0$, 那么$T=(n^{\log_b (a)})$
2.如果$f(n)=\Theta (n^{\log_b (a)})$, 那么$T(n)=O(n^{\log_b(a)} \cdot \log(n))$
3.如果$f(n)=\Omega(n^{\log_b (a)+\epsilon})$, 若存在$\epsilon>0$, 并且 对于一个常数 $c< 1$， $af(n/b)\leq cf(n)$, 并且 $n \rightarrow \infty$, 那么便适用$T(n)=\Theta(f(n))$

晕吗? 怎么那么多$\Theta(n^{\log_b a})$?

我们这里不得不结合一个递归树来说明
依旧使用$T(n)=2T(n/2)+n$

                    f(n)
                /            \
        f(n/b)                f(n/b)
        /        \                /        \
f(n/b^2) f(n/b^2) f(n/b^2) f(n/b^2)
    /    \        /    \        /    \        /    \
    ......(很多次递归以后)
    O(1)O(1)......O(1)O(1)O(1)O(1)

我们可以发现这棵递归树可以被分成两个部分, 上面的都是f(n)构成的, 而最下面的叶子节点都是O(1).

其实这里用O(1)是因为笔记本里的代码块部分Latex不好显示, 准确的说是Theta(1)

重点! 主定理到底在做什么?

事实上主定理就是对比这两个部分的时间复杂度罢了:

到底是上面那些f(n)操作加起来更耗时, 还是最下层所有叶节点的O(1)加起来更耗时?

这个问题，我们大概可以如此表述:$T(n)=p\cdot f(n)+k\cdot O(1)$. 但是这里的因为其来源p其实增长不快.这里就先把它忽略作为一个常数, 所以$p\cdot f(n)=O(f(n))$(本文结尾会展开谈一下原因). 所以此时重点在这里的$k\cdot O(1)$的k.

好, 刚刚说到重点是那个$k\cdot O(1)$的k, 那么我们怎么知道k是多少呢?

不难发现这个树每层会分叉a个子节点, 而这棵树总共大约有$\log_b n$层, 那么就大约有$a^{\log_b n}$个叶节点, 也就是说$\Theta(a^{\log_b n})$. 可是我们更习惯于在评估一个幂函数的大O符号中用n作为底数, 所以我们可以使用换底公式, 故$\Theta(n^{\log_b a})$

$n^{\log_b a}$? 再看看主定理的公式, 眼熟吗?

1.如果$f(n)=O(n^{\log_b (a)-\epsilon})$, 若存在$\epsilon >0$, 那么$T=(n^{\log_b (a)})$
2.如果$f(n)=\Theta (n^{\log_b (a)})$, 那么$T(n)=O(n^{\log_b(a)} \cdot \log(n))$
3.如果$f(n)=\Omega(n^{\log_b (a)+\epsilon})$, 若存在$\epsilon>0$, 并且 对于一个常数 $c< 1$， $af(n/b)\leq cf(n)$, 并且 $n \rightarrow \infty$, 那么便适用$T(n)=\Theta(f(n))$

回到之前我们提到的那个式子$T(n)=p\cdot f(n)+k\cdot O(1)$, 我们把k代入, 就成了$T(n)=p\cdot f(n)+n^{\log_b a}$. 那么这个T(n)岂不就是对比这两项哪个随n增长更快了?

第一种情况

下层所有叶节点的O(1)加起来更耗时

我们的k, 即$n^{\log_b a}$的增长速度大于了f(n), 那么$T(n)=O(n^{\log_b a})$. 之所以引入$\epsilon$只是为了说明增长速度大罢了.

第一种情况下k代表的最终处理问题的最小子任务明显占了主导.

第二种情况

一样耗时

第二种情况就是最小子任务和分割过程一样, 没有谁明显的占据了主导低位.也就是说$f(n)=\Theta(n^{\log_b a})$

因此这个时候两个的时间复杂度都得算进去$T(n)=O(n^{\log_b a}\cdot \log n)$

第三种情况

上面那些f(n)操作加起来更耗时

第三种情况正好与第一种情况相反, 代表分治过程占了主导地位.

哦,对了. 另外还有更多的条件.为什么要求:

对于一个常数 $c< 1$,$af(n/b) \leq cf(n)$, 并且 $n \rightarrow \infty$, 那么便适用$T(n)=\Theta(f(n))$

因为, 当分治过程占主导时, 你不能让子问题的耗时增长速率大于其本身, 那这就不算是分治了. 这是教材上的简单解释。

当然，我们不会止步于此，还记得那个p的问题吗? 从另一个角度说其实这里是在限制p。

如果你想知道具体原因，下面我会说。

尾声：进一步谈谈p

上文说到我们直接忽略p. 因为p被限制增长不可能超过$O(f(n))$
由于p的来源，在第一种和第二种情况它不可能超过k，第三种情况我们不得不面对p。所以第三种情况的限制中我们直接限制了p不可能超过$O(f(n))$

关于$T(n)=p\cdot f(n)+k\cdot O(1)$的p的计算,来自本文章草稿.
通常在不使用主定理的情况下会使用.

如果你乐意, 通常情况下我们这里的$p\cdot f(n)$的p是这样计算的:
我们可以先把上面的非叶节点,也就是所有的f(n)加起来. 这个公式看起来有点点复杂, 但是放心, 并没有那么重要.

$\sum_{j=0}^{\log_b (n)-1}a^j f(n/b^j)$

然后我们可以用一个变形的”等比数列求和公式”算出来. 事实上这个n也不重要, 可以提取出来.

$\sum_{i=0}^k r^i=\frac{r^{k+1}-1}{r-1}$

至于为什么要公式变形会更好, 因为我们的递归树有$\log_b n$层, 去掉最后下面一层后是$\log_b n-1$. 而上面公式的项数k就是$\log_b n-1$, 这里公式变形后正好可以抵消掉那个1.

回到上文p的问题，你可以动手写一下，根据主定理的第三条中的规定，$c< 1$， $af(n/b)\leq cf(n)$，我们会发现这里其实就是在约束公比r足够小，你可以自己带进去手算，再用一次换底，得到这里的p不管怎么样其增长速度也不可能超过$f(n)$。

比如: 对于$3T(n/4)+cn^2$,$a=3,b=4$，注意由于$cn^2$，b是带入下次递归的，所以分母是$b^2$，得到的公比r是(3/16)。带入得出的p是：$\frac{(3/16)^{\log_4 n}-1}{(3/16)-1}$,你换底那个log，得到$O(n^{\log_4 (3/16)})$，这绝对小于那个$O(f(n))$，也就是$O(n^2)$。至于p与k的对比读者可以自己研究一下。

总结

其实整个主定理的核心是到底是递归树上面那些f(n)操作加起来更耗时, 还是最下层所有叶节点的O(1)加起来更耗时?
公式我们如此写$T(n)=p\cdot f(n)+k\cdot O(1)$
由于$O(1)$没啥好说的，
所以进一步地，主定理在讨论：上面公式里p,f(n)和k三个变量的增长速度。只不过主定理直接用条件限制了p。所以我们关注的重点就仅在f(n)和k上了。

最后的最后，虽然主定理可以让你快速确定递归时间复杂度, 然而其有一定局限性.
比如$T(n)=2^nT (n/2) + n$, 这就不可以计算. a必须是一个常数. 当然这些你可以根据我上面说的自己玩玩，就不展开了。

同样我的水平也有一定局限性. 我希望能帮到各位读者, 如果有错误或者疑问, 感谢你的提出. 欢迎给我发送邮件restkhz(at)restkhz.com,直接留言也行.