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

比如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

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

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

堂。neufeld的答案非常好，但我可能会分两部分解释它:首先，大多数算法都属于O()的粗略层次结构。然后，你可以看看每一种算法，得出那种时间复杂度的典型算法是怎么做的。

出于实际目的，似乎唯一重要的O()是:

O(1) "constant time" - the time required is independent of the size of the input. As a rough category, I would include algorithms such as hash lookups and Union-Find here, even though neither of those are actually O(1). O(log(n)) "logarithmic" - it gets slower as you get larger inputs, but once your input gets fairly large, it won't change enough to worry about. If your runtime is ok with reasonably-sized data, you can swamp it with as much additional data as you want and it'll still be ok. O(n) "linear" - the more input, the longer it takes, in an even tradeoff. Three times the input size will take roughly three times as long. O(n log(n)) "better than quadratic" - increasing the input size hurts, but it's still manageable. The algorithm is probably decent, it's just that the underlying problem is more difficult (decisions are less localized with respect to the input data) than those problems that can be solved in linear time. If your input sizes are getting up there, don't assume that you could necessarily handle twice the size without changing your architecture around (eg by moving things to overnight batch computations, or not doing things per-frame). It's ok if the input size increases a little bit, though; just watch out for multiples. O(n^2) "quadratic" - it's really only going to work up to a certain size of your input, so pay attention to how big it could get. Also, your algorithm may suck -- think hard to see if there's an O(n log(n)) algorithm that would give you what you need. Once you're here, feel very grateful for the amazing hardware we've been gifted with. Not long ago, what you are trying to do would have been impossible for all practical purposes. O(n^3) "cubic" - not qualitatively all that different from O(n^2). The same comments apply, only more so. There's a decent chance that a more clever algorithm could shave this time down to something smaller, eg O(n^2 log(n)) or O(n^2.8...), but then again, there's a good chance that it won't be worth the trouble. (You're already limited in your practical input size, so the constant factors that may be required for the more clever algorithms will probably swamp their advantages for practical cases. Also, thinking is slow; letting the computer chew on it may save you time overall.) O(2^n) "exponential" - the problem is either fundamentally computationally hard or you're being an idiot. These problems have a recognizable flavor to them. Your input sizes are capped at a fairly specific hard limit. You'll know quickly whether you fit into that limit.

就是这样。还有很多其他的可能性在这些之间(或大于O(2^n))，但它们在实践中不经常发生，它们与这些中的任何一个在性质上没有太大的不同。三次算法已经有点牵强了;我之所以把它们包括进来，是因为我经常遇到它们，值得一提(例如矩阵乘法)。

这类算法到底发生了什么?我认为你有一个很好的开始，尽管有很多例子不符合这些特征。但对于上述情况，我认为通常是这样的:

O(1) - you're only looking at most at a fixed-size chunk of your input data, and possibly none of it. Example: the maximum of a sorted list. Or your input size is bounded. Example: addition of two numbers. (Note that addition of N numbers is linear time.) O(log n) - each element of your input tells you enough to ignore a large fraction of the rest of the input. Example: when you look at an array element in binary search, its value tells you that you can ignore "half" of your array without looking at any of it. Or similarly, the element you look at gives you enough of a summary of a fraction of the remaining input that you won't need to look at it. There's nothing special about halves, though -- if you can only ignore 10% of your input at each step, it's still logarithmic. O(n) - you do some fixed amount of work per input element. (But see below.) O(n log(n)) - there are a few variants. You can divide the input into two piles (in no more than linear time), solve the problem independently on each pile, and then combine the two piles to form the final solution. The independence of the two piles is key. Example: classic recursive mergesort. Each linear-time pass over the data gets you halfway to your solution. Example: quicksort if you think in terms of the maximum distance of each element to its final sorted position at each partitioning step (and yes, I know that it's actually O(n^2) because of degenerate pivot choices. But practically speaking, it falls into my O(n log(n)) category.) O(n^2) - you have to look at every pair of input elements. Or you don't, but you think you do, and you're using the wrong algorithm. O(n^3) - um... I don't have a snappy characterization of these. It's probably one of: You're multiplying matrices You're looking at every pair of inputs but the operation you do requires looking at all of the inputs again the entire graph structure of your input is relevant O(2^n) - you need to consider every possible subset of your inputs.

这些都不严谨。尤其是线性时间算法(O(n)):我可以举出很多例子，你必须看所有的输入，然后是一半，然后是一半，等等。或者反过来——将输入对折叠在一起，然后对输出进行递归。这些不符合上面的描述，因为你不是只看一次每个输入，但它仍然是线性时间。不过，在99.2%的情况下，线性时间意味着只查看一次每个输入。

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

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

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

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

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

不用，用Prolog就行。如果您在Prolog中编写排序算法，只需描述每个元素都应该比前一个元素大，并让回溯为您进行排序，那么它将是O(x!)也称为“排列排序”。