简明解释算法中的大O符号

伯乐在线导读:2009年1月28日Arec Barrwin在StackOverflow上提问,“有没有关于大O符号(Big O notation)的简单解释?尽量别用那么正式的定义,用尽可能简单的数学来解释”。在经过众多热心网友的修改更新后,最佳回复的得分已高达 3234 分,详细内容,请见下文。

最佳回复所给出的大O符号的最简单定义如下:

大O符号是一种算法复杂度的相对表示方式。

这个句子里有一些重要而严谨的用词:

  • 相对(relative):你只能比较相同的事物。你不能把一个做算数乘法的算法和排序整数列表的算法进行比较。但是,比较2个算法所做的算术操作(一个做乘法,一个做加法)将会告诉你一些有意义的东西;
  • 表示(representation):大O(用它最简单的形式)把算法间的比较简化为了一个单一变量。这个变量的选择基于观察或假设。例如,排序算法之间的对比通常是基于比较操作(比较2个结点来决定这2个结点的相对顺序)。这里面就假设了比较操作的计算开销很大。但是,如果比较操作的计算开销不大,而交换操作的计算开销很大,又会怎么样呢?这就改变了先前的比较方式;
  • 复杂度(complexity):如果排序10,000个元素花费了我1秒,那么排序1百万个元素会花多少时间?在这个例子里,复杂度就是相对其他东西的度量结果。

在你阅读了本文剩余部分后,再回来重读上面的文字吧。

我所能想到的大O符号最好的例子就是做算术。拿两个数字(123456和789012)举例。我们在学校里学到的基本算术操作是:

  • 加法;
  • 减法;
  • 乘法;
  • 除法。

它们中每一个都是一次操作或一个问题。为它们求解的方法就被叫做算法(algorithm)

加法是最简单的了。你把加数排成行,按列加上每个数字,把所加得的数的末位数字写到结果里。所加得的数的十位及其以上的数字转入下一列的计算中。

让我们假设在算法中,加上这些数是计算开销最大的操作。合乎情理的说,为了把这两个数加起来我们必须要加6次数字(并且可能进位到第7次)。如果我们把两个100位数相加,我们必须做100次加法操作。如果我们把两个10,000位数相加,我们必须做10,000次加法操作。

看到这里的模式了吗?复杂度complexity,就是操作的数量),对于加法中较大数的数字个数n,是直接成比例的。我们称这为O(n)或者线性复杂度(linear complexity)

除了借位替代了进位,减法也是相似的。

乘法就不同了。你把乘数排成行,取放在下面的乘数的第1个数字,把它逆序乘以上面乘数的每一个数字。下面乘数的其余数字也这样做。所以为了乘我们的两个6位数乘数,我们必须做36次乘法操作。我们还需要做10或11次列的加法操作来得到最终结果。

如果我们有两个100位数相乘,我们需要做10,000次乘法操作和200次加法操作。两个100万位数相乘,我们需要做1万亿(1012)次乘法操作和200万次加法操作。

作为n平方的算法衡量尺度,这就是O(n2),即平方复杂度(quadratic complexity)。现在是时候介绍另一个重要概念了:

我们只关心复杂度最重要的部分。

敏锐的人可能已意识到,我们可以把操作次数表示为:n2 + 2n。但正如你所看到的,我们的两个100万位数相乘的例子,第二个 2n 无关紧要(在那个阶段,2n只占操作总量的0.0002%)。

有人注意到我们在这里假设场景为最坏的情况。当我们做6位数乘法时,如果其中一个是4位数另一个是6位数,那么我们只需做24次乘法操作。然而,对于那个’n’,我们仍然计算最坏情况,即乘数都是6位数的情况。因此,大O符号是关于一个算法的最坏情况的。

电话簿

我所能想到的下一个最棒的例子就是电话簿,通常叫做白页电话簿或者其它类似名字,因国而异。但我要谈论的是这种电话薄,这种电话薄把人按这样的顺序排列:姓、缩写或名、地址、然后是电话号码。

telephone-book

现在,如果你要指示计算机在一个包含1,000,000个名字的电话簿中查找”John Smith”的电话号码,你会怎么做?忽略也许你能猜测出S从电话簿哪里开始的事实(假设你不能猜测),你会怎么做?

一种典型的实现也许是,打开电话簿的正中间,取第500,000条记录,把它和”Smith”进行比较。如果这恰好就是”Smith,John”,那我们真幸运。然而,”John Smith”更有可能在其前面或后面。如果在后面,那么我们把电话簿后面一半从中间划分开,然后重复之前的过程;如果在前面,那么我们把第一半从中间划分开,然后重复之前的过程。以此类推。

这种算法叫做二分搜索(binary search)。不论你是否意识到,它在编程中每天都用到。

因此,如果你想要在包含100万名字的电话簿中查找一个名字,事实上,通过这种算法,最多20次,你能找到任何名字。在比较搜索算法中,我们决定把比较操作作为我们的’n’。

  • 对于有3个名字的电话簿,最多需2次比较。
  • 对于有7个名字的电话簿,最多需3次比较。
  • 对于有15个名字的电话簿,最多需4次比较。
  • 对于有1,000,000个名字的电话簿,最多需20次比较。

这简直好得难以置信,不是吗?

用大O术语就是O(log n),即对数复杂度(logarithmic complexity)。现在问题中的对数可以是ln(底数为e),log10,log2 或者以其它为底数,这无关紧要,它仍然是O(log n),正如O(2n2) 和 O(100n2) 都记为 O(n2)。

现在,值得花时间说明一下,对于算法,大O符号能够被用于决定3种情况:

  • 最好情况(Best Case):在电话簿的搜索中,最好情况是我们比较了1次就找到了名字。这就是O(1),即常数复杂度(constant complexity)
  • 期望情况(Expected Case):正如上面讨论过的,复杂度是O(log n);
  • 最坏情况(Worst Case):也是O(log n)。

通常我们不关心最好情况。我们对期望和最坏情况感兴趣。有时,期望情况更重要,有时最坏情况更重要。

回到电话簿的例子上来。

如果你有一个电话号码,想要查找名字,要怎么做呢?警察有一个相反(按电话号码排列)的电话簿,但是对于一般公众,这样的查询会被拒绝,是吧?技术上,你能在普通电话簿中查找一个号码。要怎么做呢?

你从第一个名字开始比较号码。如果吻合,很棒,如果不吻合,你移到下一条记录。你必须这样做,因为电话簿是无序(unordered)的(电话号码的排列是无序的)。

因此,查找一个名字:

  • 最好情况(Best Case):O(1);
  • 期望情况(Expected Case):O(n)(对应500,000);
  • 最坏情况(Worst Case):O(n)(对应1,000,000)。

旅行商问题

这是计算机科学中值得提到的一个相当有名的问题。在这个问题中,有N个城镇,每个城镇通过道路与1个或多个其它城镇相连,道路的路程是确定的。旅行商问题就是找出访问每个城镇的最短路线。

听起来很简单?再想想。

如果有3个城镇A、B、C,两两之间都有道路,那么你可以这样走:

  • A -> B -> C
  • A -> C -> B
  • B -> C -> A
  • B -> A -> C
  • C -> A -> B
  • C -> B -> A

好吧,事实上,实际路线比上面的少,因为一些路线是等价的(例如,A -> B -> C 和 C -> B -> A 是等价的,因为它们使用同一条路线,只是方向相反)。

所以,事实上,这里有3条可能的路径。

  • 增加到4个城镇,你有12条可能的路径(如果我没记错)。
  • 5个城镇,60条可能的路径。
  • 6个城镇,360条可能的路径。

这是一个被叫做阶乘(factorial)的数学运算函数。大体上:

  • 5! = 5 * 4 * 3 * 2 * 1 = 120
  • 6! = 6 * 5 * 4 * 3 * 2 * 1 = 720
  • 7! = 7 * 6 * 5 * 4 * 3 * 2 * 1 = 5040
  • 25! = 25 * 24 * … * 2 * 1 = 15,511,210,043,330,985,984,000,000
  • 50! = 50 * 49 * … * 2 * 1 = 3.04140932 * 1064

所以旅行商问题的大O符号表示是O(n!),即阶乘(factorial)或组合复杂度(combinatorial complexity)

当你有200个城镇的时候,使用传统计算机,那么全世界已经没有足够的时间来解决这个问题了。

现在,有一些要思考的东西。

多项式时间

另一个我想要快速提及的要点是,任何复杂度为O(na)的算法被称为有多项式复杂度(polynomial complexity),或可以在多项式时间(polynomial time)内解决。

传统计算机能解决可以在多项式时间内解决的难题。世界上有些东西就建立在这一基础上。公钥加密是个极好例子。找到一个很大的数的两个素因子是困难的,如果不困难,那么我们就不能使用公钥加密系统了。

总之,这就是我对大O符号的解释(希望是清楚明白的英文解释)。

2 14 收藏 4 评论

关于作者:行云流水

(新浪微博:@Elldodo) 个人主页 · 我的文章 · 3

相关文章

可能感兴趣的话题



直接登录
最新评论
跳到底部
返回顶部