我在问更多关于这对我的代码意味着什么。我能从数学上理解这些概念，只是很难理解它们在概念上的含义。例如，如果有人要对一个数据结构执行O(1)操作，我知道它必须执行的操作数量不会增长，因为有更多的项。O(n)操作意味着您将对每个元素执行一组操作。有人能帮我填一下吗?
比如O(n²)的运算会怎样? 如果一个操作是O(nlog (n))这是什么意思? 有人必须吸可卡因才能写出O(x!)吗?
当前回答
大多数Jon Bentley的书(例如Programming Pearls)都以一种非常实用的方式涵盖了这些内容。他的这次演讲中就包括了一个这样的快排分析。
虽然与这个问题并不完全相关，但Knuth提出了一个有趣的想法:在高中微积分课上教授Big-O符号，尽管我觉得这个想法相当古怪。
其他回答
还记得乌龟和兔子的寓言吗?
从长远来看，乌龟赢了，但从短期来看，兔子赢了。
这就像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!)算法，除非你别无选择。上面提到的旅行推销员问题被认为是这样一个问题。
有一件事由于某种原因还没有被提及:
当你看到像O(2^n)或O(n^3)这样的算法时，这通常意味着你将不得不接受一个不完美的问题答案，以获得可接受的性能。
在处理优化问题时，像这样的正确解决方案很常见。在合理的时间内给出一个近乎正确的答案，总比在机器腐烂成灰尘很久之后才给出一个正确答案要好。
以国际象棋为例:我不知道正确的解决方案是什么，但它可能是O(n^50)或更糟。从理论上讲，任何计算机都不可能真正计算出正确答案——即使你用宇宙中的每个粒子作为计算元素，在宇宙生命周期内尽可能短的时间内执行一项操作，你仍然会剩下很多零。(量子计算机能否解决这个问题是另一回事。)
我是这样想的，你有一个任务，要清理一个由坏人V引起的问题，他选择了N，你必须估计出当他增加N时，你需要多长时间来完成你的问题。
O(1) ->增加N并没有什么不同
O(log(N)) ->每次V翻倍N，你必须花费额外的时间T来完成任务。V又翻倍了N，你花了同样多的钱。
O(N) -> V N每翻一倍，花费的时间就翻一倍。
O(N²)- V N每翻一倍，花费的时间就增加4倍。(这不公平!!)
O(nlog (N)) -， V每翻一倍N，你就花两倍的时间，再多一点。
这些是算法的边界;计算机科学家想要描述大n值需要多长时间(当你分解密码学中使用的数字时，这很重要——如果计算机速度提高了10倍，你需要多使用多少位才能确保它们仍然需要100年而不是1年才能破解你的加密?)
有些界限可能有奇怪的表达式，如果它对涉及的人有影响的话。我在Knuth的《计算机编程艺术》中见过类似于O(nlog (N) log(log(N))的算法。(我一时想不起是哪一个了)
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)最终总是会赢)。正式的定义也使用绝对值。但我希望我能让它更直观。
