主定理可以用来分析递归算法的时间复杂度(也叫渐进复杂度)。在以前,我们知道快速排序的时间复杂度是 $ \Theta (N \ast \log_2 N )$ ,我们也知道它不稳定,但是我们仿佛不知道这个 $ \Theta (N \ast \log_2 N )$ 是怎么来的……学习了主定理,我们就可以证明了~

这个“主定理”名字真的十分霸气:Master Theorem……


在算法分析中,主定理(Master Theorem)提供了用渐近符号(大O符号)表示许多由分治法得到的递推关系式的方法。
——维基百科

[warning]本文中有大量 KaTeX 公式,请确保浏览器支持,否则卡到超乎你想象。[/warning]

主定理的内容

如果有一个问题规模为 $n$,递推的子问题数量为 $a$,每个子问题的规模为 $\frac n b$(假设每个子问题的规模基本一样),递推以外进行的计算工作为 $f(n)$(比如归并排序,需要合并序列,则 $f(n)$ 就是合并序列需要的运算量),那么对于这个问题有如下递推关系式:

$$T(n)=aT \Big (\frac n b \Big) +c(n^d)$$

其中 $a \geqslant 1, b>1$。

拿最简单的归并排序来说,每次对 $(1,n)$ 一段排序,就分成两半,左右分别处理,然后进行合并。问题规模就是排序序列长度,即 $n$;每次我们把数组分成两部分,则 $b=2,a=2$;显然合并操作里 $d=1$。

那么根据主定理,可以得到问题的复杂度是:

$$ \begin{cases} T(n) = \Theta (n^d log_2(n)) &\text{if } (a = b^d) \\ T(n) = \Theta (n^d ) &\text{if } (a < b^d) \\ T(n) = \Theta (n^{log_b(a)}) &\text{if } (a > b^d) \end{cases} $$

应用举例

快速排序

显然每次问题规模减半,那么 $a=2,b=2,d=1$。$a=b^d$,符合第一种情况:

$$ T(n)=\Theta (n \log_2(n)) $$

神奇!

归并排序

和快速排序差不多,$a=2,b=2,d=1$,符合第一种情况:

$$ T(n)=\Theta (n \log_2(n)) $$

二分查找

每次问题规模减半,差别在于没有“数组合并”这样的操作,并且每次都会选出一更优,子问题数量为 1。$a=1,b=2,d=0$。$a=b^d$,第一种情况:

$$ T(n)=\Theta(\log_2(n)) $$

二叉树遍历

这里指的是深度优先搜索进行遍历二叉树。

每次问题规模减半,子问题数量为 2,不需要进行什么额外操作,$a=2,b=2,d=0$,那么是 $a> b_d$。则

$$ T(n)=\Theta(n) $$

证明

本 juruo 表示不会。回去看看《算法导论》,学习一个。

可以参考这篇文章


题外话:关于时间复杂度的表示

关于维基百科上的主定理的定义用到了一大堆 $\Theta$(Theta), $\Omega$(Omega), $O$(Omicron)这样的符号,在网上查了半天完全没理解是什么意思(包括知乎上一群大佬激烈的讨论,所有人都说:“以上答案基本都是错的”!!!)……

维基百科上的意思是:

$O$:多项式地小于
$\Omega$:多项式地大于

时间复杂度词条里还说了:

相同大小的不同输入值仍可能造成算法的运行时间不同,因此我们通常使用算法的最坏情况复杂度,记为 $T(n)$,定义为任何大小的输入 $n$ 所需的最大运行时间。另一种较少使用的方法是平均情况复杂度,通常有特别指定才会使用。
时间复杂度可以用函数 $T(n)$ 的自然特性加以分类,举例来说,有着 $T(n) = O(n)$ 的算法被称作“线性时间算法”;而 $T(n) = O(Mn)$ 和 $Mn= O(T(n))$ ,其中 $M ≥ n > 1$ 的算法被称作“指数时间算法”。

可能意思是我们平常用的 $\Theta$ 或者 $O$ 大多指的是最坏情况复杂度吧,这个用得比较多一点 🌚

引用一篇洛谷上文章的说明:

$T(n)$表示时间复杂度,我们可以这么表示时间复杂度:
$T(n)=$ 下面的任意一个符号(一个单项式):

$\Theta$,读音:theta,等于的意思。
$O$,读音:big-oh,小于等于的意思。
$\omicron$,读音:small-oh,小于的意思。
$\Omega$,读音:big omega,大于等于的意思。
$\omega$,读音:small omega,大于的意思。

如果你不能完全理解的话,在目前我们参加的NOIP中,你可以把它们都理解为成 $O$。(逃)

嗯,那么按照这位大佬的思路,我们都理解成 $O$ 吧 🌚


参考

主定理 - 维基百科,自由的百科全书
主定理的证明及应用举例 - CSDN博客
时空复杂度分析及master定理 - Chanis - 洛谷博客
时间复杂度 - 维基百科,自由的百科全书