算法时间复杂度–大O表示法

算法的时间复杂度表示法–大O表示法是一种特殊的表示法,指出了算法的速度有多快。我们经常要使用别人编写的算法,在这种情况下,知道这些算法的速度大有裨益。本文介绍大O表示法是什么,并使用它列出一些最常见的算法运行时间。


算法的运行时间以不同的速度增加

Bob要为NASA编写一个查找算法,这个算法在火箭即将登陆月球前开始执行,帮助计算着陆地点。

这个示例表明,两种算法的运行时间呈现不同的增速。Bob需要做出决定,是使用简单查找还是二分查找。使用的算法必须快速而准确。一方面,二分查找的速度更快。Bob必须在10秒钟内找出着陆地点,否则火箭将偏离方向。另一方面,简单查找算法编写起来更容易,因此出现bug的可能性更小。Bob可不希望引导火箭着陆的代码中有bug!为确保万无一失,Bob决定计算两种算法在列表包含100个元素的情况下需要的时间。

假设检查一个元素需要1毫秒。使用简单查找时,Bob必须检查100个元素,因此需要100毫秒才能查找完毕。而使用二分查找时,只需检查7个元素(log2100大约为7),因此需要7毫秒就能查找完毕。然而,实际要查找的列表可能包含10亿个元素,在这种情况下,简单查找需要多长时间呢?二分查找又需要多长时间呢?请务必找出这两个问题的答案,再接着往下读。

Bob使用包含10亿个元素的列表运行二分查找,运行时间为30毫秒(log21000000000大约为30)。他心里想,二分查找的速度大约为简单查找的15倍,因为列表包含100个元素时,简单查找需要100毫秒,而二分查找需要7毫秒。因此,列表包含10亿个元素时,简单查找需要30×15=450毫秒,完全符合在10秒内查找完毕的要求。Bob决定使用简单查找。这是正确的选择吗?

不是。实际上,Bob错了,而且错得离谱。列表包含10亿个元素时,简单查找需要10亿毫秒,相当于11天!为什么会这样呢?因为二分查找和简单查找的运行时间的增速不同。
图片.png

也就是说,随着元素数量的增加,二分查找需要的额外时间并不多,而简单查找需要的额外时间却很多。因此,随着列表的增长,二分查找的速度比简单查找快得多。Bob以为二分查找速度为简单查找的15倍,这不对:列表包含10亿个元素时,为3300万倍。有鉴于此,仅知道算法需要多长时间才能运行完毕还不够,还需知道运行时间如何随列表增长而增加。这正是大O表示法的用武之地。

大O表示法指出了算法有多快。例如,假设列表包含n个元素。简单查找需要检查每个元素,因此需要执行n次操作。使用大O表示法,这个运行时间为O(n)。单位秒呢?没有——大O表示法指的并非以秒为单位的速度。大O表示法让你能够比较操作数,它指出了算法运行时间的增速。

再来看一个例子。为检查长度为n的列表,二分查找需要执行logn次操作。使用大O表示法,这个运行时间怎么表示呢?O(logn)。一般而言,大O表示法像下面这样。
图片.png

这指出了算法需要执行的操作数。之所以称为大O表示法,是因为操作数前有个大O。这听起来像笑话,但事实如此!

下面来看一些例子,看看你能否确定这些算法的运行时间。

理解不同的大O运行时间

图片.png

算法一

一种方法是以每次画一个的方式画16个格子。记住,大O表示法计算的是操作数。在这个示例中,画一个格子是一次操作,需要画16个格子。如果每次画一个格子,需要执行多少次操作呢?

图片.png

画16个格子需要16步。这种算法的运行时间是多少?

算法二

请尝试这种算法——将纸折起来。

图片.png

在这个示例中,将纸对折一次就是一次操作。第一次对折相当于画了两个格子!再折,再折,再折。

图片.png

折4次后再打开,便得到了漂亮的网格!每折一次,格子数就翻倍,折4次就能得到16个格子!
图片.png

你每折一次,绘制出的格子数都翻倍,因此4步就能“绘制”出16个格子。这种算法的运行时间是多少呢?请搞清楚这两种算法的运行时间之后,再接着往下读。

答案如下:算法1的运行时间为O(n),算法2的运行时间为O(logn)。


大O表示法指出了最糟情况下的运行时间

假设你使用简单查找在电话簿中找人。你知道,简单查找的运行时间为O(n),这意味着在最糟情况下,必须查看电话簿中的每个条目。如果要查找的是Adit——电话簿中的第一个人,一次就能找到,无需查看每个条目。考虑到一次就找到了Adit,请问这种算法的运行时间是O(n)还是O(1)呢?

简单查找的运行时间总是为O(n)。查找Adit时,一次就找到了,这是最佳的情形,但大O表示法说的是最糟的情形。因此,你可以说,在最糟情况下,必须查看电话簿中的每个条目,对应的运行时间为O(n)。这是一个保证——你知道简单查找的运行时间不可能超过O(n)。


一些常见的大O运行时间

下面按从快到慢的顺序列出了你经常会遇到的5种大O运行时间。

> O(log n),也叫对数时间,这样的算法包括二分查找。

> O(n),也叫线性时间,这样的算法包括简单查找。

> O(n * log n),这样的算法是一种速度较快的排序算法。

> O(n2),这样的算法是一种速度较慢的排序算法。

> O(n!),这样的算法包括接下来将介绍的旅行商问题的解决方案是一种非常慢的算法。

假设你要绘制一个包含16格的网格,且有5种不同的算法可供选择,这些算法的运行时间如上所示。如果你选择第一种算法,绘制该网格所需的操作数将为4(log 16 = 4)。假设你每秒可执 行10次操作,那么绘制该网格需要0.4秒。如果要绘制一个包含1024格的网格呢?这需要执行10(log 1024 = 10)次操作,换言之,绘制这样的网格需要1秒。这是使用第一种算法的情况。

第二种算法更慢,其运行时间为O(n)。即要绘制16个格子,需要执行16次操作;要绘制1024个格子,需要执行1024次操作。执行这些操作需要多少秒呢?

下面按从快到慢的顺序列出了使用这些算法绘制网格所需的时间:
图片.png

还有其他的运行时间,但这5种是最常见的。

这里做了简化,实际上,并不能如此干净利索地将大O运行时间转换为操作数,但就目前而 言,这种准确度足够了。等你学习其他一些算法后,第4章将回过头来再次讨论大O表示法。当 前,我们获得的主要启示如下:

> 算法的速度指的并非时间,而是操作数的增速;

> 谈论算法的速度时,我们说的是随着输入的增加,其运行时间将以什么样的速度增加;

> 算法的运行时间用大O表示法表示;

> O(log n)比O(n)快,当需要搜索的元素越多时,前者比后者快得越多。


旅行商

阅读上文时,你可能认为根本就没有运行时间为O(n!)的算法。事实上不是的。下面就是一个运行时间极长的算法。这个算法要解决的是计算机科学领域非常著名的旅行商问题,其计算时间增加得非常快,而有些非常聪明的人都认为没有改进空间。

有一位旅行商,他需要前往5个城市:

图片.png

这位旅行商(姑且称之为Opus吧)要前往这5个城市,同时要确保旅程最短。为此,可考虑前往这些城市的各种可能顺序。

图片.png

对于每种顺序,他都计算总旅程,再挑选出旅程最短的路线。5个城市有120种不同的排列方式。因此,在涉及5个城市时,解决这个问题需要执行120次操作。涉及6个城市时,需要执行720次操作(有720种不同的排列方式)。涉及7个城市时,需要执行5040次操作!
图片.png

推而广之,涉及n个城市时,需要执行n!(n的阶乘)次操作才能计算出结果。因此运行时间为O(n!),即阶乘时间。除非涉及的城市数很少,否则需要执行非常多的操作。如果涉及的城市数超过100,根本就不能在合理的时间内计算出结果——等你计算出结果,太阳都没了。

这种算法很糟糕!Opus应使用别的算法,可他别无选择。这是计算机科学领域待解的问题之一。对于这个问题,目前还没有找到更快的算法,有些很聪明的人认为这个问题根本就没有更巧妙的算法。面对这个问题,我们能做的只是去找出近似答案。