讨厌算法的程序员 | 第四章 时间复杂度

增长量级

函数的增长量级

上一篇算法分析基础中,我们分析了插入排序,知道了其最好情况下的运行时间为T(n) = an + b,最差情况下的运行时间为T(n) = an2 + bn + c。表达式中的常量a、b和c(实际上都是依赖每行代码的执行时间ci)进一步抽象了每行代码的执行时间,而凸显出输入规模n与运行时间T的关系。

然而这样还不够,还有进一步抽象的空间:即人们真正感兴趣的是运行时间随输入规模增长的增长率或增长量级。也就是说,当n越来越大时,T的增长是何种量级?我们知道,当n的值很大时,低阶项对T的贡献就没那么重要了,同时,最重要的高阶项的常量系数对T的贡献也没那么重要了。

对于插入排序最差情况来说,当忽略掉低阶项以及高阶项的常数系数,就只剩下了n2。插入排序最差情况的运行时间,可记做T(n) = Θ(n2),其中Θ称作渐进记号,这种简化成为渐进分析。

渐进分析强调的是,对于足够大的输入,运行时间中的倍增常量和低阶项被输入规模本身的影响所支配。尽管有时在一个小输入下,一个运行时间具有较低增长量级的算法(比如T(n) = 5n)),比一个运行时间具有较高增长量级的算法(比如T(n) = n2),需要更多的时间。

时间复杂度

《算法导论》中的整个第一部分(第1章到第5章),一直没有发现“时间复杂度”这个我们非常熟悉的名词及定义(英文版未考证),尽管书中一步步引导出的“算法运行时间”,以及“渐进记号”其实就是在说“时间复杂度”。到了第二部分(第6章),又开篇冒出了“时间复杂度”这个词,反而有点不适。这可能与中文版是由7个人翻译的有关。

刚好手边有程杰的《大话数据结构》一书,这里引用下其对“时间复杂度”的定义,算是有个交待。

在进行算法分析时,语句总的执行次数T(n)是关于问题规模n的函数,进而分析T(n)随n的变化情况并确定T(n)的数量级。算法的时间复杂度,也就是算法的时间度量,记作:T(n) = Ο(f(n))。它表示随问题规模n的增大,算法执行时间的增长率和f(n)的增长率相同,称作算法的渐进时间复杂度,简称为时间复杂度。其中f(n)是问题规模的函数。

渐进记号

细心的读者可能发现了,上面的增长量级一节与时间复杂度一节分别用到了两种不同的渐进符号,Θ和Ο,前者发音Theta,后者发音Omicron,它们都是希腊字母。

通常所说的算法时间复杂度不都是用的后一种Ο么(有时也叫大Οmicron)?

到这里,《算法导论》的厉害之处就彰显无余了。它不仅介绍了Θ和Ο,还介绍了Ω(大Omega),ο(小Omicron),ω(小Omega)5种不同的渐进记号,每种记号都体现了不同的渐进分析方法。

出于实用性的考虑,这里只简单说下Θ与Ο的异同。对其余渐进符号,用到之处会再解释。

对于T(n) = an2 + bn + c, 既可以记作T(n) = Θ(n2),也可以记作 T(n) = Ο(n2)。

对于T(n) = an + b, 既可以记作T(n) = Θ(n),也可以记作T(n) = Ο(n),还可以记作T(n) = Ο(n2)。

这是因为Θ是一种紧确性的表示,而Ο是一种非紧确性、只描述了上限的表示。

《算法导论》中的翻译的这个词“紧确”,还是很形象的。我再说的直白点,就是绘制出的函数图形,是否比较“贴合”。

我们看到的大部分书中都是在用Ο(大Omicron)表示时间复杂度,但通常都是选择了一个紧确性的函数。比如说,T(n) = an + b,T(n) = Ο(n),T(n) = Ο(n2)都对,但是会选择前者T(n) = Ο(n)。

原文发布于微信公众号 - 人工智能LeadAI(atleadai)

原文发表时间:2017-09-25

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏牛客网

滴滴java新锐实习一面

1500
来自专栏平凡文摘

十年之后再看“面向对象”

1053
来自专栏好好学java的技术栈

“365算法每日学计划”:01打卡

如果有小伙伴很少接触到这种题目的话,可能会觉得有点陌生,不知道从何下手,可能一开始我们能想到“最笨”的方法,但是也觉得挺有“娱乐性”的方法。

2353
来自专栏PPV课数据科学社区

【学习】在R语言中使用正则表达式

有时候我们要处理的是非结构化的数据,例如网页或是电邮资料,那么就需要用R来抓取所需的字符串,整理为进一步处理的数据形式。R语言中有一整套可以用来处理字符...

2824
来自专栏杨光的专栏

千亿关系链下的新增共同好友计算

本文介绍一种千亿关系链下的日新增共同好友挖掘算法 --NTE 算法。该算法基于分治的思想,将新增共好友计算问题,转换为更易于运算与实现的三角形计算问题。

8310
来自专栏CSDN技术头条

代码审查拯救世界?

代码审查是指阅读代码来检查源代码与编码标准的符合性以及代码质量的活动。现在,越来越多的团队倡导要进行代码审查活动,而本文作者通过一幅漫画,来诠释其对代码审查的理...

2046
来自专栏TensorFlow从0到N

讨厌算法的程序员 4 - 时间复杂度

增长量级 ? 函数的增长量级 上一篇算法分析基础中,我们分析了插入排序,知道了其最好情况下的运行时间为T(n) = an + b,最差情况下的运行时间为T(n...

2703
来自专栏数据结构与算法

2017 五一 清北学堂 Day1模拟考试结题报告

预计分数:100+50+50 实际分数:5+50+100 =.= 多重背包 (backpack.cpp/c/pas) (1s/256M) 题目描述 提供一个背包...

3225
来自专栏老九学堂

程序员揭秘:火爆朋友圈的左右脑年龄测试,真相只是一个随机函数!

最近,老九的朋友圈已经被左右脑测试刷爆了,老九也去测试了一下,只需要进入相应入口并回答几个设定的问题后,就会出现左右脑两个年龄测试结果。 ? 有不少小伙伴晒出自...

3656
来自专栏牛客网

美团点评2019届机器学习/数据挖掘算法实习生一面

3.14网申的(北京,基础研究部门),3.20笔试。二十多天没消息,然后今天(4.12)下午接到美团面试电话,当然是前两天约好的,面试官大概迟到了十多分钟。 Q...

3906

扫码关注云+社区