大多数Jon Bentley的书(例如Programming Pearls)都以一种非常实用的方式涵盖了这些内容。他的这次演讲中就包括了一个这样的快排分析。

虽然与这个问题并不完全相关，但Knuth提出了一个有趣的想法:在高中微积分课上教授Big-O符号，尽管我觉得这个想法相当古怪。

假设你有一台可以解决一定规模问题的计算机。现在想象一下，我们可以将性能提高几倍。每加倍一次，我们能解决多大的问题?

如果我们能解决一个两倍大的问题，那就是O(n)

如果我们有一个非1的乘数，那就是某种多项式复杂度。例如，如果每加倍一次，问题的规模就会增加约40%，即O(n²)，而约30%则是O(n³)。

如果我们只是增加问题的规模，它是指数级的，甚至更糟。例如，如果每翻一倍意味着我们可以解决一个大1的问题，它就是O(2^n)。(这就是为什么使用合理大小的密钥实际上不可能强制使用密码密钥:128位密钥需要的处理量大约是64位密钥的16万亿倍。)

我会试着为一个真正的八岁男孩写一个解释，除了专业术语和数学概念。

比如O(n²)的运算会怎样?

如果你在一个聚会上，包括你在内有n个人。需要多少次握手才能让每个人都和其他人握手，因为人们可能会在某个时候忘记他们握手的人是谁。

注意:这近似于产生n(n-1)的单形，这足够接近于n²。

如果一个操作是O(nlog (n))这是什么意思?

你最喜欢的球队赢了，他们站在队伍里，队伍里有n名球员。你需要和每个玩家握手多少次，假设你要和每个玩家握手多次，多少次，玩家的号码n中有多少位数字。

注意:这将产生n * log n的10次方。

有人必须吸可卡因才能写出O(x!)吗?

你是一个富二代，你的衣柜里有很多衣服，每种衣服有x个抽屉，抽屉一个挨着一个，第一个抽屉里有一件衣服，每个抽屉里有和左边抽屉一样多的衣服，所以你有一顶帽子，两顶假发，…(x-1)条裤子，然后是x件衬衫。现在，用每个抽屉里的一件物品，你能装扮出多少种风格呢?

注意:这个例子表示一个决策树中有多少个叶结点，其中子结点数=深度，通过1 * 2 * 3 *完成。* x

big - o符号对代码的重要意义在于，当它所操作的“事物”数量增加一倍时，它将如何扩展。这里有一个具体的例子:

Big-O       |  computations for 10 things |  computations for 100 things
----------------------------------------------------------------------
O(1)        |   1                         |     1
O(log(n))   |   3                         |     7
O(n)        |  10                         |   100
O(n log(n)) |  30                         |   700
O(n^2)      | 100                         | 10000

快速排序是O(nlog (n))而冒泡排序是O(n²)当排序10个东西时，快速排序比冒泡排序快3倍。但当对100个东西进行排序时，速度要快14倍!显然，选择最快的算法很重要。当您访问具有数百万行的数据库时，这可能意味着您的查询在0.2秒内执行，而不是花费数小时。

另一件需要考虑的事情是，糟糕的算法是摩尔定律无法帮助的事情。例如，如果你有一个O(n^3)的科学计算，它一天可以计算100个东西，处理器速度翻倍一天只能计算125个东西。然而，计算到O(n²)，你每天要做1000件事情。

澄清: 实际上，Big-O并没有说不同算法在同一特定大小点上的性能比较，而是说同一算法在不同大小点上的性能比较:

                 computations     computations       computations
Big-O       |   for 10 things |  for 100 things |  for 1000 things
----------------------------------------------------------------------
O(1)        |        1        |        1        |         1
O(log(n))   |        1        |        3        |         7
O(n)        |        1        |       10        |       100
O(n log(n)) |        1        |       33        |       664
O(n^2)      |        1        |      100        |     10000

log(n) means logarithmic growth. An example would be divide and conquer algorithms. If you have 1000 sorted numbers in an array ( ex. 3, 10, 34, 244, 1203 ... ) and want to search for a number in the list (find its position), you could start with checking the value of the number at index 500. If it is lower than what you seek, jump to 750. If it is higher than what you seek, jump to 250. Then you repeat the process until you find your value (and key). Every time we jump half the search space, we can cull away testing many other values since we know the number 3004 can't be above number 5000 (remember, it is a sorted list).

N log(N)表示N * log(N)

只是为了回应我上面帖子的一些评论:

Domenic - I'm on this site, and I care. Not for pedantry's sake, but because we - as programmers - typically care about precision. Using O( ) notation incorrectly in the style that some have done here renders it kind of meaningless; we may just as well say something takes n^2 units of time as O( n^2 ) under the conventions used here. Using the O( ) adds nothing. It's not just a small discrepancy between common usage and mathematical precision that I'm talking about, it's the difference between it being meaningful and it not.

我知道很多很多优秀的程序员都准确地使用这些术语。说“哦，我们是程序员，所以我们不在乎”会降低整个企业的成本。

一个接一个-嗯，不完全是，尽管我同意你的观点。对于任意大的n，它不是O(1)这是O()的定义。它只是表明O()对于有界n的适用性有限，在这里我们更愿意讨论所走的步数，而不是这个数字的界限。