我在问更多关于这对我的代码意味着什么。我能从数学上理解这些概念，只是很难理解它们在概念上的含义。例如，如果有人要对一个数据结构执行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)最终总是会赢)。正式的定义也使用绝对值。但我希望我能让它更直观。
其他回答
一种思考的方式是:
O(N²)意味着对于每个元素，你都要对其他元素做一些事情，比如比较它们。冒泡排序就是一个例子。
O(N log N)意味着对于每个元素，你只需要看log N个元素。这通常是因为你知道一些元素，可以让你做出有效的选择。最有效的排序就是一个例子，比如归并排序。
O(N!)表示对N个元素的所有可能排列进行处理。旅行推销员就是一个例子，那里有N!访问节点的方法，暴力解决方案是查看每一种可能的排列的总代价，以找到最优的一个。
我喜欢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!)算法，除非你别无选择。上面提到的旅行推销员问题被认为是这样一个问题。
你可能会发现把它形象化很有用:
同样，在LogY/LogX尺度上，函数n1/2, n, n2都看起来像直线，而在LogY/X尺度上，2n, en, 10n是直线和n!是线性的(看起来像n log n)
告诉你8年前的log(n)意味着你必须把一个长度为nlog的东西切成两半的次数，让它变成大小为n=1:p
O(nlogn)通常是排序 O(n²)通常是比较所有元素对
要理解O(n log n)，请记住log n意味着log-base-2 (n)。然后看看每一部分:
O(n)是，当你对集合中的每一项进行操作时。
O(log n)是指操作的次数与取2的指数相同，以得到项目的数量。例如，二分搜索必须将集合切成log n的一半。
O(nlogn)是一个组合——你在对集合中的每一项进行二分搜索。高效的排序通常是对每个项目进行一次循环，并在每个循环中进行良好的搜索，以找到放置相关项目或组的正确位置。因此是n * log n。
