我在问更多关于这对我的代码意味着什么。我能从数学上理解这些概念，只是很难理解它们在概念上的含义。例如，如果有人要对一个数据结构执行O(1)操作，我知道它必须执行的操作数量不会增长，因为有更多的项。O(n)操作意味着您将对每个元素执行一组操作。有人能帮我填一下吗?
比如O(n²)的运算会怎样? 如果一个操作是O(nlog (n))这是什么意思? 有人必须吸可卡因才能写出O(x!)吗?
当前回答
把它想象成垂直堆叠乐高积木(n)，然后跳过它们。
O(1)表示在每一步，你什么都不做。高度保持不变。
O(n)表示在每一步，你堆叠c块，其中c1是常数。
O(n²)表示在每一步，你堆叠c2 x n个块，其中c2是一个常数，n是堆叠块的数量。
O(nlogn)表示在每一步，你堆叠c3 x n x logn个块，其中c3是一个常数，n是堆叠块的数量。
其他回答
把它想象成垂直堆叠乐高积木(n)，然后跳过它们。
O(1)表示在每一步，你什么都不做。高度保持不变。
O(n)表示在每一步，你堆叠c块，其中c1是常数。
O(n²)表示在每一步，你堆叠c2 x n个块，其中c2是一个常数，n是堆叠块的数量。
O(nlogn)表示在每一步，你堆叠c3 x n x logn个块，其中c3是一个常数，n是堆叠块的数量。
好吧，这里有一些非常好的答案，但几乎所有的答案似乎都犯了同样的错误，这是一个普遍的常见用法。
非正式地，我们写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数量。)
大多数Jon Bentley的书(例如Programming Pearls)都以一种非常实用的方式涵盖了这些内容。他的这次演讲中就包括了一个这样的快排分析。
虽然与这个问题并不完全相关，但Knuth提出了一个有趣的想法:在高中微积分课上教授Big-O符号，尽管我觉得这个想法相当古怪。
你可能会发现把它形象化很有用:
同样，在LogY/LogX尺度上，函数n1/2, n, n2都看起来像直线，而在LogY/X尺度上，2n, en, 10n是直线和n!是线性的(看起来像n log 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.
