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

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

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的适用性有限，在这里我们更愿意讨论所走的步数，而不是这个数字的界限。

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

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

我喜欢don neufeld的答案，但我想我可以加上O(nlog n)

使用简单分治策略的算法可能是O(log n)最简单的例子是在排序列表中查找某个东西。你不需要从头开始扫描。你走到中间，你决定是向后走还是向前走，跳到中途，直到你找到你要找的东西。

如果您查看快速排序或归并排序算法，您将看到它们都采用将列表分成两半，对每一半排序(使用相同的算法，递归地)，然后重新组合两半的方法。这种递归分治策略是O(nlog n)

If you think about it carefully, you'll see that quicksort does an O(n) partitioning algorithm on the whole n items, then an O(n) partitioning twice on n/2 items, then 4 times on n/4 items, etc... until you get to an n partitions on 1 item (which is degenerate). The number of times you divide n in half to get to 1 is approximately log n, and each step is O(n), so recursive divide and conquer is O(n log n). Mergesort builds the other way, starting with n recombinations of 1 item, and finishing with 1 recombination of n items, where the recombination of two sorted lists is O(n).

至于抽大麻写一个O(n!)算法，除非你别无选择。上面提到的旅行推销员问题被认为是这样一个问题。

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

不用，用Prolog就行。如果您在Prolog中编写排序算法，只需描述每个元素都应该比前一个元素大，并让回溯为您进行排序，那么它将是O(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