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

增长量级

函数的增长量级

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

相关文章

来自专栏数据分析

[数据清洗]- Pandas 清洗“脏”数据(二)

概要 了解数据 分析数据问题 清洗数据 整合代码 了解数据 在处理任何数据之前,我们的第一任务是理解数据以及数据是干什么用的。我们尝试去理解数据的列/行、记录、...

2854
来自专栏Spark学习技巧

SparkSql的Catalyst之图解简易版

一,基本介绍 一言不合就上图。 ? 由上图可以看出Catalyst的作用尤为重要。MLPipelines Structured Streaming,GraphF...

1778
来自专栏java 成神之路

高亮标红

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

Day5网络流

算法 无源汇上下界可行流 ?  先强制流过l的流量 从s到每个正权点连流量为l的流量  从每个负权点向t连-l的流量 如果容量为0,则不连边 有源汇上下界最大流...

2839
来自专栏吉浦迅科技

DAY34:阅读算术指令

1323
来自专栏Spark学习技巧

第2篇:数据库关系建模

第二篇:数据库关系建模 前言 ER建模环节完成后,需求就被描述成了ER图。之后,便可根据这个ER图设计相应的关系表了。 但从ER图到具体关系表的建立还需要经过两...

3026
来自专栏开发 & 算法杂谈

动态数据竞争检测方法实验分析(一)

之前的文章大致介绍了一下我们的动态数据竞争检测平台如何构建,这篇文章主要是在动态数据竞争检测平台上实现了之前介绍的数据竞争检测方法,我们扩展了其中的一些方法使得...

1772
来自专栏TensorFlow从0到N

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

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

2553
来自专栏ACM算法日常

确定比赛名次(拓扑排序) - HDU 1285

这次先讲理论,因为拓扑排序在日常工作中用的并不多,甚至于很多人可能忘了计算机中存在这样一种排序。我大概的整理一下拓扑排序的定义和应用,以便看了这...

672
来自专栏趣学算法

数据结构 第2讲 算法复杂性

该内容来源于本人著作《趣学算法》在线章节:http://www.epubit.com.cn/book/details/4825

772

扫描关注云+社区