学步园

这是在Stackoverflow的关于 “算法复杂度” 的经典问答。

将此文翻译并分享下。

问: by Arec Barrwin

 

答: by cletus

注意，所有人几乎都会混淆大O符号（有上界）和Theta符号（有两个边界）。从我的经验来看，这是实际上是典型的非学术性设置讨论。对于造成的任何不明确、含糊的地方，我表示歉意。

我能给出的最简单的大O符号的定义如下：

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

在这个句子里有几个重要的、特意选出的词：

·      相对：你只能用苹果和苹果比较。不能用一种乘法运算的算法和整数分类的算法比较。但是两个算术运算（一个乘法，一个加法）算法的对比是有意义的；

·      表示：大O（最简单的形式）减少了单变量算法之间的对比。变量是基于观察和假设而选出来的。例如，分类算法是典型的基于对比运算（对比两个节点，确定他们的相对顺序）的对比。这里假设对比是昂贵的。但如果对比是廉价的，而交换是昂贵的，会怎样？它改变了对比；且

·      复杂度：如果我需要1秒钟将10000个元素分类，那么我需要多久将1百万个元素分类？这个例子里的复杂度是对另一些东西的相对测量。

当你读完剩下的部分的时候，再回来读一遍上面的内容。

 

我能想到的最好的大O符号的例子是做运算。选两个数字（123456和789012）。我们在学校学到的最基本的算术运算符是：

·      加法;

·      减法;

·      乘法;
和

·      除法.

这些每一个都是一个运算或一个问题。解决这些问题的方法被称为算法。

加法是很简单的。将数字（右对齐）列出来，在一列写下加法运算结果的最后一位。运算结果的‘十位’上的数字要进位到下一位。

 

我们假设这些数字相加在这个算法中是最昂贵的运算。显然将两个数字相加，我们必须将六位加到一起（可能进位到第7位）。如果我们将两个100位的数字相加，我们要做100次加法。如果我们两个10000位的数字，我们要做10000次加法。

 

看出这个模式了吗？复杂度（运算的次数）是与较大数字的位数n成正比的。我们称其为O(n)或者线性复杂度。

 

减法很相似（除了你可能会借位，不再是进位）。

 

乘法就不一样了。把数字都列出来，取下面数字的第一位，上面数字的每一位依次与其相乘，剩下的每一位都是这样。所以两个6位的数字相乘，我们需要做36次乘法。最终结果可能需要多达10或11位。

 

如果我们有两个100位的数字，我们需要做10000次乘法和200次加法。对于两个一百万位的数字，我们需要一万亿（10¹²）次的乘法和两百万次的加法。

 

算法与N次方成正比，也就是O(n²)或二次复杂度。这正是个介绍另一个重要概念的好时机：

 

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

 

聪明的人会发现，我们可以将运算的次数表示为n² + 2n。但是从我们那个两个一百万位的数字的例子中，你可以看出第二个数（2n）不是很重要（因为在此例中仅占所有运算次数的0.0002%）。

 

可能有人注意到我们在这里假设的是最糟糕的情况。当我们乘以6位数的数字时，如果其中一个是4位，另一个是6位，那么我们只需要做24次运算。我们仍然按最糟糕的情况计算n，例如当两个数字都是6位数字时。因此大O符号是关于算法的最糟糕的情况。

 

电话本

 

我能想到的下一个很好的例子是电话本，一般我们叫它白页或者其他类似的名字，但是每个国家的电话本都不同。我所指的是那种按姓氏列排列，姓氏后面是姓名中的大写字母或者名字，或许还有地址和电话号码。

 

现在如果你使用电脑在有1000000个名字的电话本中查找“John Smith”的电话号码，你会怎么做？忽略你可以猜测以S开头的姓氏从哪一页开始的事实（我们假设你不能这么做），你会怎么做？

 

一种典型的做法可能是打开中间部分，取第500000个名字与“Smith”对比。如果恰巧他正是“Smith, John”，那么我们的运气真是太好了。但是更可能是“John Smith”这个名字在此之前或之后。如果在这之后，我们再打开后一半电话本的中间部分，再重复一次上面的操作。如果在这之前，我们打开前一半电话本的中间部分，再重复一次上面的操作。以此类推。

 

这称为二分搜索法，而且无论你有没有了解它，每天的编程工作都要用到它。

 

所以如果你想要在有一百万个名字的电话本中找到一个名字，实际上你可以通过这种方法最多20次就能找到你想要找的任何一个名字。在对比搜索算法中，这个对比次数就是我们的‘n’。

·      对于一本只有3个名字的电话本，（最多）只需要2次对比。

·      对于7个名字的电话本最多需要3次。

·      对于15个名字的电话本最多需要4次。

·      …

·      对于1000000个名字的电话本最多只需要20次。

这非常好，不是吗？

 

在大O符号术语中，这是O(log n)或者对数复杂度。现在问题中的对数可能在自然对数、log₁₀, log₂或者以其他为底的对数中。是不是O(log n)不是太重要，比如O(2n²)和O(100n²)都是O(n²)。

 

从这点上值得这样解释，大O符号可以应用于确定算法的这三种情况：

·      最好的情况：在搜索电话本时，最好的情况是在第一次对比时就找到了那个名字。这是O(1)或常量复杂度；

·      预期的情况：如我们在上面讨论的是O(log n);且

·      最糟糕的情况：这也是O(log n)。

一般我们不太关心最好的情况。我们对预期的和最糟的情况更有兴趣。有时候其中一个或另一个更为重要。

 

让我们回到电话本的例子上来。

 

如果你有一个电话号码，想找到此号码所有人的姓名，你该怎么做？警察倒是有一个通过电话查姓名的电话本，但不向公众开放。或者他们向公众开放？从技术层面上来说，你可以在一本普通的电话本中通过电话号码反查出姓名。但是怎么做？

 

你从第一个姓名开始，与这个号码对比。如果它恰巧就是这个号码，那就太棒了，如果不是，再继续对比下一个。你不得不这么做，因为电话本是乱序的（以电话号码来看）。

所以要找到一个姓名：

·      最好的情况：O(1)；

·      预期的情况：O(n)（对于500000）；

·      最糟糕的情况：O(n)（对于1000000）。

 

旅行推销员

 

在计算机科学里这是个非常有名的问题，值得一提。在这个问题中，你有N个城镇。每一个城镇都通过一定距离的道路连接到另外一个或多个其他城镇。旅行推销员的问题就是寻求一条走访所有城镇的最短的路。

 

听起来很简单？再想想。

 

如果你有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是一样的，因为他们走的是同样的路，只不过反过来了）。

 

实际上只有三种可能：

·      去4个城镇，（如果我没记错的话）有12个可能。

·      5个城镇，有60个可能。

·      6个城镇就成了360个可能。

这个数学运算的方法称为阶乘。基本上是这样的：

·      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 × 10⁶⁴

所以旅行推销员问题的大O符号是O(n!)或者阶乘或者组合复杂度。

 

当你有200个城镇的时候，在整个宇宙中都不会足够的时间让传统计算机解决这个问题。

 

想一想。

 

多项式时间

 

另外一个我想很快提一下的是，任何有O(n^a)复杂度的算法据说有多项式复杂度或者是可以用多项式时间解决的。

O(n)、 O(n²)等都是多项式时间。许多问题不能用多项式时间解决。世界上使用某些事物正因为此。公钥密码学是一个主要的例子。找到一个很大的数的两个质因数在计算上是非常困难的。如果不这么做，我们就不能使用公钥密码系统。

 

不管怎样，这就是我的大O符号（修改的）解释（希望是简明）。

点击原文链接

此文在CC-By-SA 3.0许可证下使用