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

/ 0评 /

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

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


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

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

主定理的内容

如果有一个问题规模为 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=1a=b^d,符合第一种情况:

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

神奇!

归并排序

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

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

二分查找

每次问题规模减半,差别在于没有“数组合并”这样的操作,并且每次都会选出一更优,子问题数量为 1a=1,b=2,d=0a=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 - 洛谷博客
时间复杂度 - 维基百科,自由的百科全书


知识共享许可协议 本文章采用 知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议 进行许可。
欢迎转载,如有错误欢迎指出。
本文链接:https://skywt.cn/posts/master-theorem/


发表评论

电子邮件地址不会被公开。 必填项已用*标注