告诉你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.

堂。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%的情况下，线性时间意味着只查看一次每个输入。

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

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

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

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

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

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

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

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