我在问更多关于这对我的代码意味着什么。我能从数学上理解这些概念，只是很难理解它们在概念上的含义。例如，如果有人要对一个数据结构执行O(1)操作，我知道它必须执行的操作数量不会增长，因为有更多的项。O(n)操作意味着您将对每个元素执行一组操作。有人能帮我填一下吗?
比如O(n²)的运算会怎样? 如果一个操作是O(nlog (n))这是什么意思? 有人必须吸可卡因才能写出O(x!)吗?
当前回答
Big-O背后的“直觉
想象一下，当x趋于无穷时，x上的两个函数f(x)和g(x)之间的“竞争”。
现在，如果从某一点开始(某个x点)，一个函数的值总是比另一个高，那么我们称这个函数比另一个“快”。
例如，对于每x > 100，你看到f(x) > g(x)，那么f(x)比g(x)“快”。
在这种情况下，我们可以说g(x) = O(f(x))F (x)对g(x)提出了某种“速度限制”，因为最终它超过了它，并将其永远甩在后面。
这并不完全是大o符号的定义，它还指出，对于某个常数C, f(x)只需要大于C*g(x)(这只是另一种说法，你不能通过将g(x)乘以常数因子来帮助g(x)赢得竞争- f(x)最终总是会赢)。正式的定义也使用绝对值。但我希望我能让它更直观。
其他回答
把它想象成垂直堆叠乐高积木(n)，然后跳过它们。
O(1)表示在每一步，你什么都不做。高度保持不变。
O(n)表示在每一步，你堆叠c块，其中c1是常数。
O(n²)表示在每一步，你堆叠c2 x n个块，其中c2是一个常数，n是堆叠块的数量。
O(nlogn)表示在每一步，你堆叠c3 x n x logn个块，其中c3是一个常数，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.
Big-O背后的“直觉
想象一下，当x趋于无穷时，x上的两个函数f(x)和g(x)之间的“竞争”。
现在，如果从某一点开始(某个x点)，一个函数的值总是比另一个高，那么我们称这个函数比另一个“快”。
例如，对于每x > 100，你看到f(x) > g(x)，那么f(x)比g(x)“快”。
在这种情况下，我们可以说g(x) = O(f(x))F (x)对g(x)提出了某种“速度限制”，因为最终它超过了它，并将其永远甩在后面。
这并不完全是大o符号的定义，它还指出，对于某个常数C, f(x)只需要大于C*g(x)(这只是另一种说法，你不能通过将g(x)乘以常数因子来帮助g(x)赢得竞争- f(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
大多数Jon Bentley的书(例如Programming Pearls)都以一种非常实用的方式涵盖了这些内容。他的这次演讲中就包括了一个这样的快排分析。
虽然与这个问题并不完全相关，但Knuth提出了一个有趣的想法:在高中微积分课上教授Big-O符号，尽管我觉得这个想法相当古怪。
