告诉你8年前的log(n)意味着你必须把一个长度为nlog的东西切成两半的次数，让它变成大小为n=1:p

O(nlogn)通常是排序 O(n²)通常是比较所有元素对

这可能太数学化了，但这是我的尝试。(我是数学家。)

如果某个东西是O(f(n))，那么它在n个元素上的运行时间将等于A f(n) + B(以时钟周期或CPU操作为单位)。理解这些常量A和B是非常关键的，它们来自特定的实现。B本质上代表你的操作的“常量开销”，例如你所做的一些预处理不依赖于集合的大小。A表示实际项目处理算法的速度。

关键在于，你可以使用大O符号来计算某物的可伸缩性。所以这些常数并不重要:如果你想弄清楚如何从10个项目扩展到10000个项目，谁会关心开销常数B呢?类似地，其他问题(见下文)肯定会超过乘法常数A的重要性。

So the real deal is f(n). If f grows not at all with n, e.g. f(n) = 1, then you'll scale fantastically---your running time will always just be A + B. If f grows linearly with n, i.e. f(n) = n, your running time will scale pretty much as best as can be expected---if your users are waiting 10 ns for 10 elements, they'll wait 10000 ns for 10000 elements (ignoring the additive constant). But if it grows faster, like n2, then you're in trouble; things will start slowing down way too much when you get larger collections. f(n) = n log(n) is a good compromise, usually: your operation can't be so simple as to give linear scaling, but you've managed to cut things down such that it'll scale much better than f(n) = n2.

实际上，这里有一些很好的例子:

O(1): retrieving an element from an array. We know exactly where it is in memory, so we just go get it. It doesn't matter if the collection has 10 items or 10000; it's still at index (say) 3, so we just jump to location 3 in memory. O(n): retrieving an element from a linked list. Here, A = 0.5, because on average you''ll have to go through 1/2 of the linked list before you find the element you're looking for. O(n2): various "dumb" sorting algorithms. Because generally their strategy involves, for each element (n), you look at all the other elements (so times another n, giving n2), then position yourself in the right place. O(n log(n)): various "smart" sorting algorithms. It turns out that you only need to look at, say, 10 elements in a 1010-element collection to intelligently sort yourself relative to everyone else in the collection. Because everyone else is also going to look at 10 elements, and the emergent behavior is orchestrated just right so that this is enough to produce a sorted list. O(n!): an algorithm that "tries everything," since there are (proportional to) n! possible combinations of n elements that might solve a given problem. So it just loops through all such combinations, tries them, then stops whenever it succeeds.

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

我是这样向我那些不懂技术的朋友描述的:

考虑多位数加法。很好的老式铅笔和纸的补充。就是你7-8岁时学的那种。给定两个三位数或四位数，你很容易就能求出它们加起来是多少。

如果我给你两个100位的数字，然后问你它们加起来是多少，即使你必须使用铅笔和纸，计算出来也会非常简单。一个聪明的孩子可以在几分钟内做这样的加法。这只需要大约100次操作。

现在，考虑多位数乘法。你可能在八九岁的时候就学会了。你(希望)做了很多重复的练习来学习它背后的机制。

Now, imagine I gave you those same two 100-digit numbers and told you to multiply them together. This would be a much, much harder task, something that would take you hours to do - and that you'd be unlikely to do without mistakes. The reason for this is that (this version of) multiplication is O(n^2); each digit in the bottom number has to be multiplied by each digit in the top number, leaving a total of about n^2 operations. In the case of the 100-digit numbers, that's 10,000 multiplications.

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

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

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

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

好吧，这里有一些非常好的答案，但几乎所有的答案似乎都犯了同样的错误，这是一个普遍的常见用法。

非正式地，我们写f(n) = O(g(n))如果，直到一个比例因子，对于所有n大于某个n0, g(n)大于f(n)。也就是说，f(n)的增长速度并不比g(n)快，或者从上到下以g(n)为界。这并没有告诉我们f(n)增长有多快，除了它保证不会比g(n)差。

一个具体的例子:n = O(2^n)我们都知道n的增长速度比2^n慢得多，所以我们可以说它的上界是指数函数。在n和2^n之间有很大的空间，所以它不是一个很紧的边界，但它仍然是一个合理的边界。

为什么我们(计算机科学家)使用边界而不是精确?因为a)边界通常更容易证明，b)它为我们提供了一种表达算法属性的简便方法。如果我说我的新算法是O(n.log n)，这意味着在最坏的情况下，它的运行时间将在n个输入上以n.log n为界，对于足够大的n(尽管请参阅下面我的评论，当我可能不是指最坏情况时)。

如果相反，我们想说一个函数的增长速度与其他函数一样快，我们用theta来说明这一点(我将T(f(n))写成markdown表示\ (f(n))。T(g(n))是上下以g(n)为界的缩写，直到一个比例因子且渐近。

这是f (n) = T (g (n)) < = > f (n) = O (g (n))和g (n) = O (f (n))。在我们的例子中，我们可以看到n != T(2^n)因为2^n != O(n)。

为什么要担心这个呢?因为在你的问题中，你写了“一个人必须吸可卡因才能写出一个O(x!)?”答案是否定的——因为基本上你写的所有东西都会以阶乘函数为界。快速排序的运行时间是O(n!) -这不是一个严格的界限。

这里还有另一个微妙的维度。通常我们用O(g(n))表示最坏情况的输入，这样我们就得到了一个复合语句:在最坏情况下运行时间不会比g(n)步的算法差，同样是模缩放，而且n足够大，但有时我们想讨论平均情况甚至最佳情况的运行时间。

香草快速排序就是一个很好的例子。在最坏的情况下是T(n²)(实际上至少需要n²步，但不会多很多)，但在平均情况下是T(n.log n)，也就是说期望的步数与n.log n成正比。在最好的情况下也是T(n.log n) -但你可以改进它，例如，检查数组是否已经排序在哪种情况下，最佳运行时间将是T(n)。

How does this relate to your question about the practical realisations of these bounds? Well, unfortunately, O( ) notation hides constants which real-world implementations have to deal with. So although we can say that, for example, for a T(n^2) operation we have to visit every possible pair of elements, we don't know how many times we have to visit them (except that it's not a function of n). So we could have to visit every pair 10 times, or 10^10 times, and the T(n^2) statement makes no distinction. Lower order functions are also hidden - we could have to visit every pair of elements once, and every individual element 100 times, because n^2 + 100n = T(n^2). The idea behind O( ) notation is that for large enough n, this doesn't matter at all because n^2 gets so much larger than 100n that we don't even notice the impact of 100n on the running time. However, we often deal with 'sufficiently small' n such that constant factors and so on make a real, significant difference.

例如，快速排序(平均成本T(n.log n))和堆排序(平均成本T(n.log n))都是具有相同平均成本的排序算法——但快速排序通常比堆排序快得多。这是因为堆排序比快速排序对每个元素做了更多的比较。

这并不是说O()符号是无用的，只是不精确。对于小n来说，这是一个相当钝的工具。

(作为本文的最后一个注意事项，请记住O()表示法只是描述任何函数的增长——它不一定是时间，它可以是内存、分布式系统中交换的消息或并行算法所需的cpu数量。)