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

增长量级

函数的增长量级

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

相关文章

来自专栏数据和云

性能优化:认识B*Tree 索引分裂(二)

黄玮(Fuyuncat) 黄玮(Fuyuncat),资深 Oracle DBA,从事Oracle数据库管理、维护与开发工作十余年,有丰富的大型数据库设计、开发...

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

【V课堂】数据挖掘知识脉络与资源整理(五)–缺失值处理

简介: 缺失值是指粗糙数据中由于缺少信息而造成的数据的聚类,分组,删失或截断。它指的是现有数据集中某个或某些属性的值是不完全的。数据挖掘所面对的数据不是特地为某...

2848
来自专栏AI科技大本营的专栏

AI 技术讲座精选:数学不好,也可以学习人工智能(六)——巧用数学符号

【AI100 导读】欢迎阅读《数学不好,也可以学好人工智能》系列的第六篇文章。如果你错过了之前的五部分,一定记得把它们找出来看一下!这篇文章作者会帮你学习数学符...

3358
来自专栏AILearning

【机器学习实战】第14章 利用SVD简化数据

第14章 利用SVD简化数据 <script type="text/javascript" src="http://cdn.mathjax.org/mathj...

2307
来自专栏大闲人柴毛毛

10分钟搞懂蚁群算法

蚂蚁几乎没有视力,但他们却能够在黑暗的世界中找到食物,而且能够找到一条从洞穴到食物的最短路径。它们是如何做到的呢? 蚂蚁寻找食物的过程 单只蚂蚁的行为及其简单...

2.7K14
来自专栏数据派THU

一文带你入门图论和网络分析(附Python代码)

本文从图的概念以及历史讲起,并介绍了一些必备的术语,随后引入了networkx库,并以一个航班信息数据集为例,带领读者完成了一些基本分析。

1472
来自专栏机器之心

谷歌微软等科技巨头数据科学面试107道真题:你能答出多少?

选自Learndatasci 机器之心编译 参与:李泽南 来自 Glassdoor 的最新数据可以告诉我们各大科技公司最近在招聘面试时最喜欢向候选人提什么问题。...

2557
来自专栏一名叫大蕉的程序员

社区发现有啥鸟用No.14

当当当,同学们说要听算法,那今天就说说算法,关于社区发现的一系列算法。 最近一段时间工作上使用到了社区发现,虽然只是小小一部分。但是呢,工作量还是不小的,在网上...

2897

使用粒子群优化器来解决旅行商人问题

粒子群优化器,作为一种使用人工智能来解决问题的方式,在解多元、恒变的方程式方面有很大的优势。在本文中我们主要讲的是通过修改算法来解决一些问题,例如使用离散固定值...

2247
来自专栏TensorFlow从0到N

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

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

2633

扫码关注云+社区