文章目录
主定理可以用来分析递归算法的时间复杂度(也叫渐进复杂度)。在以前,我们知道快速排序的时间复杂度是 ,我们也知道它不稳定,但是我们仿佛不知道这个 是怎么来的……学习了主定理,我们就可以证明了~
这个“主定理”名字真的十分霸气:Master Theorem……
在算法分析中,主定理(Master Theorem)提供了用渐近符号(大O符号)表示许多由分治法得到的递推关系式的方法。
——维基百科
[warning]本文中有大量 KaTeX 公式,请确保浏览器支持,否则卡到超乎你想象。[/warning]
主定理的内容
如果有一个问题规模为 ,递推的子问题数量为 ,每个子问题的规模为 (假设每个子问题的规模基本一样),递推以外进行的计算工作为 (比如归并排序,需要合并序列,则 就是合并序列需要的运算量),那么对于这个问题有如下递推关系式:
其中 。
拿最简单的归并排序来说,每次对 一段排序,就分成两半,左右分别处理,然后进行合并。问题规模就是排序序列长度,即 ;每次我们把数组分成两部分,则 ;显然合并操作里 。
那么根据主定理,可以得到问题的复杂度是:
应用举例
快速排序
显然每次问题规模减半,那么 。,符合第一种情况:
神奇!
归并排序
和快速排序差不多,,符合第一种情况:
二分查找
每次问题规模减半,差别在于没有“数组合并”这样的操作,并且每次都会选出一更优,子问题数量为 1。。,第一种情况:
二叉树遍历
这里指的是深度优先搜索进行遍历二叉树。
每次问题规模减半,子问题数量为 2,不需要进行什么额外操作,,那么是 。则
证明
本 juruo 表示不会。回去看看《算法导论》,学习一个。
可以参考这篇文章。
题外话:关于时间复杂度的表示
关于维基百科上的主定理的定义用到了一大堆 (Theta), (Omega), (Omicron)这样的符号,在网上查了半天完全没理解是什么意思(包括知乎上一群大佬激烈的讨论,所有人都说:“以上答案基本都是错的”!!!)……
维基百科上的意思是:
:多项式地小于
:多项式地大于
在时间复杂度词条里还说了:
相同大小的不同输入值仍可能造成算法的运行时间不同,因此我们通常使用算法的最坏情况复杂度,记为 ,定义为任何大小的输入 所需的最大运行时间。另一种较少使用的方法是平均情况复杂度,通常有特别指定才会使用。
时间复杂度可以用函数 的自然特性加以分类,举例来说,有着 的算法被称作“线性时间算法”;而 和 ,其中 的算法被称作“指数时间算法”。
可能意思是我们平常用的 或者 大多指的是最坏情况复杂度吧,这个用得比较多一点 :new_moon_with_face:
引用一篇洛谷上文章的说明:
表示时间复杂度,我们可以这么表示时间复杂度:
下面的任意一个符号(一个单项式):,读音:theta,等于的意思。
,读音:big-oh,小于等于的意思。
,读音:small-oh,小于的意思。
,读音:big omega,大于等于的意思。
,读音:small omega,大于的意思。如果你不能完全理解的话,在目前我们参加的NOIP中,你可以把它们都理解为成 。(逃)
嗯,那么按照这位大佬的思路,我们都理解成 吧 :new_moon_with_face:
参考
主定理 - 维基百科,自由的百科全书
主定理的证明及应用举例 - CSDN博客
时空复杂度分析及master定理 - Chanis - 洛谷博客
时间复杂度 - 维基百科,自由的百科全书