理解算法的时间复杂度

发表于 更新于
如果不曾遇见过你,我本可以忍受孤独.
### 关于大O符号 我所能想到的大O符号最好的例子就是做算术。拿两个数字（123456和789012）举例。我们在学校里学到的基本算术操作是： 加法； 减法； 乘法； 除法。 它们中每一个都是一次操作或一个问题。为它们(加法，减法，乘法，除法)求解的方法就被叫做算法（algorithm）。

加法

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

1
2
3
4
5
   123456
 +
   789012
------------
   912468   我们一共操作了6次

让我们假设在算法中，加上这些数是计算开销最大的操作。合乎情理的说，为了把这两个数加起来我们必须要加6次数字（并且可能进位到第7次）。如果我们把两个100位数相加，我们必须做100次加法操作。如果我们把两个10,000位数相加，我们必须做10,000次加法操作。
6位数相加就必须要加6次数字（并且可能进位到第7次）—最坏的情况
复杂度（complexity，就是操作的数量），对于加法中较大数的数字个数n，是直接成比例的。我们称这为O(n)或者线性复杂度（linear complexity）。

乘法

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

1
2
3
4
5
6
7
8
9
10
  23
x
  34
-------
   2
  9
  9
 6 
 782
// 4次 乘法操作， 3次加法操作

如果我们有两个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符号是关于一个算法的最坏情况的。

电话簿

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

现在，如果你要指示计算机在一个包含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）。

http://blog.jobbole.com/55184/#article-comment
https://stackoverflow.com/questions/487258/what-is-a-plain-english-explanation-of-big-o-notation/487278#487278