我在问更多关于这对我的代码意味着什么。我能从数学上理解这些概念，只是很难理解它们在概念上的含义。例如，如果有人要对一个数据结构执行O(1)操作，我知道它必须执行的操作数量不会增长，因为有更多的项。O(n)操作意味着您将对每个元素执行一组操作。有人能帮我填一下吗?
比如O(n²)的运算会怎样? 如果一个操作是O(nlog (n))这是什么意思? 有人必须吸可卡因才能写出O(x!)吗?
当前回答
只是为了回应我上面帖子的一些评论:
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的适用性有限，在这里我们更愿意讨论所走的步数，而不是这个数字的界限。
其他回答
log(n) means logarithmic growth. An example would be divide and conquer algorithms. If you have 1000 sorted numbers in an array ( ex. 3, 10, 34, 244, 1203 ... ) and want to search for a number in the list (find its position), you could start with checking the value of the number at index 500. If it is lower than what you seek, jump to 750. If it is higher than what you seek, jump to 250. Then you repeat the process until you find your value (and key). Every time we jump half the search space, we can cull away testing many other values since we know the number 3004 can't be above number 5000 (remember, it is a sorted list).
N log(N)表示N * log(N)
其中很多都很容易用非编程的东西来演示，比如洗牌。
对一副牌进行排序通过遍历整副牌找到黑桃a，然后遍历整副牌找到黑桃2，以此类推最坏情况是n^2，如果这副牌已经倒着排序了。你看了52张牌52次。
一般来说，真正糟糕的算法不一定是故意的，它们通常是对其他东西的误用，比如在同一集合上线性重复的另一个方法中调用一个线性方法。
告诉你8年前的log(n)意味着你必须把一个长度为nlog的东西切成两半的次数，让它变成大小为n=1:p
O(nlogn)通常是排序 O(n²)通常是比较所有元素对
还记得乌龟和兔子的寓言吗?
从长远来看，乌龟赢了，但从短期来看，兔子赢了。
这就像O(logN)(乌龟)vs O(N)(野兔)。
如果两种方法的大o值不同，那么它们中的一种会在N的水平上获胜，但大o值没有说明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!)算法，除非你别无选择。上面提到的旅行推销员问题被认为是这样一个问题。
