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

增长量级

函数的增长量级

上一篇算法分析基础中,我们分析了插入排序,知道了其最好情况下的运行时间为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)。

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏数据派THU

放弃“for循环”,教你用这种算法 !(附代码)

原文标题:Why you should forget ‘for-loop’ for data science code and embrace vectoriz...

27360
来自专栏精讲JAVA

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

一起帮里有人问“面向对象”的问题。但我创建“一起帮”的目的是帮人解决“具体的”“实务性的”问题,“面向对象”太过于抽象,所以没批准发布。后来在QQ群里讨论,看他...

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

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

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

30140
来自专栏顶级程序员

为什么Python是入行人工智能的首选语言?

在所有编程语言里,Python并不算萌新,从1991年发布第一个版本,至今已经快30年了。

23440
来自专栏数据派THU

一文读懂PyTorch张量基础(附代码)

本文介绍了PyTorch Tensor最基础的知识以及如何跟Numpy的ndarray互相转换。

11330
来自专栏平凡文摘

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

12230
来自专栏韩伟的专栏

字节的奥秘

在数码产品中,最常见的名词就是“字节”了。不管是U盘容量、手机存储空间,还是网络带宽,下载速度,都会涉及所谓“字节”这个单位。但到底“字节”是一个什么东西呢?本...

37140
来自专栏小小挖掘机

数据城堡参赛代码实战篇(一)---手把手教你使用pandas

小编们最近参加了数据城堡(http://www.pkbigdata.com/)举办的“大学生助学金精准资助预测”比赛,分组第19名的成绩进入了复赛,很激动有木有...

37540
来自专栏杨光的专栏

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

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

1K00
来自专栏恰童鞋骚年

自己动手写游戏:坦克撕逼大战

START:最近在公交车上无聊,于是用平板看了看下载的坦克大战的开发教程,于是在晚上回家后花了两天模仿了一个,现在来总结一下。

21360

扫码关注云+社区

领取腾讯云代金券