主定理与递归程序时间复杂度的计算

文章目录

• 主定理的内容
• 应用举例
  • 快速排序
  • 归并排序
  • 二分查找
  • 二叉树遍历
• 证明
• 题外话：关于时间复杂度的表示
• 参考

主定理可以用来分析递归算法的时间复杂度（也叫渐进复杂度）。在以前，我们知道快速排序的时间复杂度是 $\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$ 大多指的是最坏情况复杂度吧，这个用得比较多一点 :new_moon_with_face:

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

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

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

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

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

参考

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