不，O(n)算法并不意味着它将对每个元素执行操作。大o符号给了你一种方法来谈论你的算法的“速度”独立于你的实际机器。

O(n)表示算法花费的时间随着输入的增加而线性增长。O(n²)意味着你的算法花费的时间是你输入的平方。等等。

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

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(x!)吗?

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

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

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

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

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

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

考虑多位数加法。很好的老式铅笔和纸的补充。就是你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 log n)，请记住log n意味着log-base-2 (n)。然后看看每一部分:

O(n)是，当你对集合中的每一项进行操作时。

O(log n)是指操作的次数与取2的指数相同，以得到项目的数量。例如，二分搜索必须将集合切成log n的一半。

O(nlogn)是一个组合——你在对集合中的每一项进行二分搜索。高效的排序通常是对每个项目进行一次循环，并在每个循环中进行良好的搜索，以找到放置相关项目或组的正确位置。因此是n * log n。