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

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

你可能会发现把它形象化很有用:

同样，在LogY/LogX尺度上，函数n1/2, n, n2都看起来像直线，而在LogY/X尺度上，2n, en, 10n是直线和n!是线性的(看起来像n log n)

Big-O背后的“直觉

想象一下，当x趋于无穷时，x上的两个函数f(x)和g(x)之间的“竞争”。

现在，如果从某一点开始(某个x点)，一个函数的值总是比另一个高，那么我们称这个函数比另一个“快”。

例如，对于每x > 100，你看到f(x) > g(x)，那么f(x)比g(x)“快”。

在这种情况下，我们可以说g(x) = O(f(x))F (x)对g(x)提出了某种“速度限制”，因为最终它超过了它，并将其永远甩在后面。

这并不完全是大o符号的定义，它还指出，对于某个常数C, f(x)只需要大于C*g(x)(这只是另一种说法，你不能通过将g(x)乘以常数因子来帮助g(x)赢得竞争- f(x)最终总是会赢)。正式的定义也使用绝对值。但我希望我能让它更直观。

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

非正式地，我们写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数量。)

有一件事由于某种原因还没有被提及:

当你看到像O(2^n)或O(n^3)这样的算法时，这通常意味着你将不得不接受一个不完美的问题答案，以获得可接受的性能。

在处理优化问题时，像这样的正确解决方案很常见。在合理的时间内给出一个近乎正确的答案，总比在机器腐烂成灰尘很久之后才给出一个正确答案要好。

以国际象棋为例:我不知道正确的解决方案是什么，但它可能是O(n^50)或更糟。从理论上讲，任何计算机都不可能真正计算出正确答案——即使你用宇宙中的每个粒子作为计算元素，在宇宙生命周期内尽可能短的时间内执行一项操作，你仍然会剩下很多零。(量子计算机能否解决这个问题是另一回事。)

还记得乌龟和兔子的寓言吗?

从长远来看，乌龟赢了，但从短期来看，兔子赢了。

这就像O(logN)(乌龟)vs O(N)(野兔)。

如果两种方法的大o值不同，那么它们中的一种会在N的水平上获胜，但大o值没有说明N的大小。