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

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

2018 年 9 月 16 日 08:35


文章目录

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

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


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

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

主定理的内容

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

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

其中 a1,b>1a \geqslant 1, b>1

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

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

{T(n)=Θ(ndlog2(n))if (a=bd)T(n)=Θ(nd)if (a<bd)T(n)=Θ(nlogb(a))if (a>bd)\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=2,b=2,d=1a=bda=b^d,符合第一种情况:

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

神奇!

归并排序

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

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

二分查找

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

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

二叉树遍历

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

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

T(n)=Θ(n)T(n)=\Theta(n)

证明

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

可以参考这篇文章


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

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

维基百科上的意思是:

OO:多项式地小于
Ω\Omega:多项式地大于

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

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

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

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

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

Θ\Theta,读音:theta,等于的意思。
OO,读音:big-oh,小于等于的意思。
ο\omicron,读音:small-oh,小于的意思。
Ω\Omega,读音:big omega,大于等于的意思。
ω\omega,读音:small omega,大于的意思。

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

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


参考

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


暂无评论


发表新的评论

所有评论都将经过博主审核。请勿填写无意义邮箱或发表无关评论、广告等,否则会被视为垃圾评论。

提交评论即表明你同意本网站使用 Cookie,并允许本站在后台记录你的邮箱、IP 地址等必要信息。这些信息不会被透露给其他用户。(提交一次评论后,本提示将不再展示)