深入浅出理解主定理原理(Master theorem)

date

Oct 16, 2024

slug

master-theorem

status

Published

缘起

网络上有很多关于主定理的文章, 其中很多都是到了如何使用就算完事了. 但是主定理本身看起来却有些繁琐. 毕竟一个定理还分三条, 还有一些条件.

其实主定理背后的思想非常简单;

背公式总是痛苦的, 若能理解, 那么便可以长久记忆下来.

本文章不会出现主定理证明. 但是需要读者了解递归, 分治, 渐进符号.

非常建议你拿着草稿纸，想不明白就跟着我写一写。本文尽量不提非必要的数学公式，不提证明。

好,为什么用主定理?

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

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

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

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

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

于是我们可以轻松得到归并排序的关系式:

(我建议你找笔和纸出来写一下再看答案)

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

如果我们不使用主定理

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

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

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

T(n)=n+2(n/2+2(n/4+⋯+n/2log2n))⋯)

T(n)=n+2lognn⋅logn2logn, 约去2logn, 结果是T(n)=n+nlogn=O(nlogn). 不难理解, 因为这里有logn层, 每层都是n, 所以就是logn乘n.

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

那我们使用主定理呢?

首先确定一下f(n)=Θ(nlogba)=Θ(nlog22)=Θ(n)

好, 符合第二种情况, 直接套公式:T(n)=O(nlogba⋅log(n))=O(nlogn)

(别急, 马上我们就看什么是第二种情况)

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

如何理解主定理

先搬出我们的主定理吧.

1.如果f(n)=O(nlogb(a)−ϵ), 若存在ϵ>0, 那么T=(nlogb(a))

2.如果f(n)=Θ(nlogb(a)), 那么T(n)=O(nlogb(a)⋅log(n))

3.如果f(n)=Ω(nlogb(a)+ϵ), 若存在ϵ>0, 并且对于一个常数 c<1， af(n/b)≤cf(n), 并且 n→∞, 那么便适用T(n)=Θ(f(n))

晕吗? 怎么那么多Θ(nlogba)?

我们这里不得不结合一个递归树来说明

依旧使用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).

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

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

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

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

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

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

nlogba? 再看看主定理的公式, 眼熟吗?

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

第一种情况

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

我们的k, 即nlogba的增长速度大于了f(n), 那么T(n)=O(nlogba). 之所以引入ϵ只是为了说明增长速度大罢了.

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

第二种情况

一样耗时

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

因此这个时候两个的时间复杂度都得算进去T(n)=O(nlogba⋅logn)

第三种情况

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

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

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

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

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

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

尾声：进一步谈谈p

上文说到我们直接忽略p. 因为p被限制增长不可能超过O(f(n))

由于p的来源，在第一种和第二种情况它不可能超过k，第三种情况我们不得不面对p。所以第三种情况的限制中我们直接限制了p不可能超过O(f(n))

关于T(n)=p⋅f(n)+k⋅O(1)的p的计算,来自本文章草稿.

通常在不使用主定理的情况下会使用.

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

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

总结

其实整个主定理的核心是到底是递归树上面那些f(n)操作加起来更耗时, 还是最下层所有叶节点的O(1)加起来更耗时?

公式我们如此写T(n)=p⋅f(n)+k⋅O(1)

由于O(1)没啥好说的，

所以进一步地，主定理在讨论：上面公式里p,f(n)和k三个变量的增长速度。只不过主定理直接用条件限制了p。所以我们关注的重点就仅在f(n)和k上了。

最后的最后，虽然主定理可以让你快速确定递归时间复杂度, 然而其有一定局限性.

比如T(n)=2nT(n/2)+n, 这就不可以计算. a必须是一个常数. 当然这些你可以根据我上面说的自己玩玩，就不展开了。

https://blog.restkhz.com/post/how-master-theorem-works