八岁的大O？
我更多地询问这对我的代码意味着什么。 我从math的angular度理解了这些概念，我只是很难从概念上理解他们的意思。 例如，如果要在数据结构上执行O（1）操作，那么我知道它所执行的操作数量不会增长，因为有更多的项目。 O（n）操作将意味着您将对每个元素执行一组操作。 有人可以填空吗？
- 像一个O（n ^ 2）操作到底会做什么？
- 如果一个操作是O（n log（n）），那么这意味着什么？
- 还有人不得不抽烟裂口写一个O（X！）？
思考的一个方法是：
O（N ^ 2）意味着每个元素，你正在做其他每个元素，比如它们。 泡沫sorting就是一个例子。
O（N log N）表示每个元素，你正在做的事情只需要看看元素的日志N. 这通常是因为你知道一些关于让你做出有效select的元素。 最有效率的sorting就是一个例子，比如合并sorting。
O（N！）表示为N个元素的所有可能的排列做一些事情。 旅行推销员就是这样的一个例子，那里有N！ 访问节点的方法，蛮力解决scheme是查看每个可能的排列的总成本以find最佳排列。
Big-O符号对您的代码意味着什么，它将如何在您操作的“事物”数量增加一倍的情况下进行扩展。 这里有一个具体的例子：
Big-O | 计算10件事| 计算100件事情 -------------------------------------------------- -------------------- 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（n log（n））与O（n ^ 2）的冒泡sorting为快速sorting。 sorting10件事时，快速sorting比泡泡sorting快3倍。 但是当分拣100件东西时，速度要快14倍！ 明显地select最快的algorithm是很重要的。 当你到达有数百行的数据库时，这可能意味着你的查询在0.2秒内执行，而不是花费数小时。
要考虑的另一件事是，一个不好的algorithm是摩尔定律不能帮助的一件事。 例如，如果你有一些O（n ^ 3）的科学计算，并且每天可以计算100件事情，那么加倍的处理器速度一天只能得到125件事情。 然而，敲这个计算到O（n ^ 2），你每天做1000件事情。
您可能会发现将其可视化很有用：
这可能太math了，但这是我的尝试。 （我是math家）
如果某事物是O（ f （ n ）），那么它在n个元素上的运行时间等于A f （ n ）+ B （例如在时钟周期或CPU操作中测量）。 理解你也有这些常量A和B ，这是由具体的实现产生的关键。 B基本上代表了操作的“常量开销”，例如，你所做的一些预处理不依赖于集合的大小。 A表示实际项目处理algorithm的速度。
关键是，你用大O符号来弄清楚事情将如何扩展 。 所以这些常量并不重要：如果你想弄清楚如何从10个项目扩展到10000个项目，那么谁在关注不断的开销B呢？ 同样，其他问题（见下文）肯定会超过乘法常数A的权重。
所以真正的交易是f （ n ）。 如果f根本不随n增长，例如f （ n ）= 1，那么你就可以很好地进行缩放—你的运行时间将永远是A + B。 如果f随着n线性增长，即f （ n ）= n ，则运行时间将按照预期的那样最大程度地扩展 – 如果用户等待10个元素10个元素，他们将等待10000 ns元素（忽略添加常数）。 但是，如果它增长得更快，就像n 2一样 ，那么你就麻烦了; 当你收集更多的东西时，事情会开始变慢。 f （ n ）= n log（ n ）是一个很好的折衷scheme，通常情况下：你的操作不能像线性缩放那么简单，但是你已经设法削减了一些东西，使它比f （ n ）= n 2 。
实际上，这里有一些很好的例子：
- O（1）：从数组中检索一个元素。 我们确切地知道它在记忆中的位置，所以我们只是去得到它。 如果collections品有10件或10000件， 它仍然在索引（说）3，所以我们只是跳到内存中的位置3。
- O（ n ）：从链表中检索一个元素。 在这里， A = 0.5，因为平均而言，在find要查找的元素之前，必须先通过链表的1/2。
- O（ n 2 ）：各种“哑”sortingalgorithm。 因为通常他们的策略涉及到每个元素（ n ），你看所有其他元素（所以再次n ，给n 2 ），然后把自己放在正确的地方。
- O（ n log（ n ））：各种“智能”sortingalgorithm。 事实certificate，你只需要看一个10 10个元素的集合中的10 个元素，就可以相对于集合中的其他人智能地sorting自己。 因为其他人也要看10个元素，而紧急行为恰好是恰当的，所以这足以产生一个sorting列表。
- O（ n ！）：“尝试一切”的algorithm，因为有（与） n成正比！ n个元素的可能组合，可以解决一个给定的问题。 所以它只是循环遍历所有这些组合，尝试它们，然后在成功时停止。
don.neufeld的答案是非常好的，但我可能会分两部分来解释：首先，大多数algorithm都有一个粗略的O（）的层次结构。 然后，你可以看看每个人想出什么样的时间复杂性的典型algorithm的草图。
出于实际的目的，似乎唯一重要的O（）是：
- O（1）“恒定时间” – 所需的时间与input的大小无关。 作为一个粗略的分类，我将在这里包括诸如哈希查找和联合查找等algorithm，即使这些algorithm实际上都不是O（1）。
- O（log（n））“对数” – 当你获得更大的input时，它会变慢，但是一旦你的input变得相当大，它就不会变得足够担心。 如果你的运行时间对于合理大小的数据是可以的，你可以用尽可能多的额外数据来弥补它的数据，而且它还是可以的。
- O（n）“线性” – 投入越多，需要的时间越长，甚至是平衡。 input大小的三倍大约需要三倍。
- O（n log（n））“优于二次方” – 增加了input大小，但它仍然是可pipe理的。 该algorithm可能是体面的，只是潜在的问题比在线性时间可以解决的问题更困难（决策相对于input数据的本地化程度较低）。 如果你的input大小在那里，那么不要以为你可以在不改变你的体系结构的情况下处理两倍的大小（例如把东西移动到一夜之间的批量计算，或者不按照每帧的方式进行）。 但是，如果input大小稍微增加，也可以; 只要注意倍数。
- O（n ^ 2）“二次方” – 它实际上只能达到您的input的一定大小，所以请注意它可以得到多大。 此外，您的algorithm可能会吸引 – 想想看是否有一个O（n log（n））algorithm，会给你你需要的。 一旦你在这里，感到非常感激我们已经与天赋的惊人的硬件。 不久以前，你所做的一切都不可能实现。
- O（n ^ 3）“立方体” – 与O（n ^ 2）没有定性差别。 同样的意见也适用，只是更多。 有一个很好的机会，一个更聪明的algorithm可以将这个时间缩减到更小的一些，例如O（n ^ 2 log（n））或者O（n ^ 2.8 …），但是再一次有这个机会将是不值得的麻烦。 （你的实际input大小已经受到限制，所以对于更聪明的algorithm来说，可能需要的常数因素可能会在实际情况下淹没它们的优点，思维也很慢;让计算机咀嚼它可以为你节省时间总体。）
- O（2 ^ n）“指数” – 这个问题要么是从根本上计算困难，要么就是成为一个白痴。 这些问题对他们来说是一种可识别的味道。 您的input大小限制在一个相当具体的硬限制。 你会很快知道你是否适合这个限制。
就是这样。 还有很多其他的可能性（或者大于O（2 ^ n）），但是它们在实践中并不经常发生，它们在性质上与其中之一没有太大的区别。 立方algorithm已经有点儿了。 我只包括他们，因为我经常碰到他们经常足以值得一提（例如matrix乘法）。
这些类algorithm实际上发生了什么？ 那么，我认为你有一个好的开始，虽然有很多例子不适合这些特征。 但是对于上述情况，我会说它通常是这样的：
- O（1） – 你只能看到固定大小的input数据，可能没有。 示例：sorting列表的最大值。
- 或者你的input大小是有限的。 例如：添加两个数字。 （请注意，N个数字的加法是线性时间。）
- O（log n） – 您的input的每个元素都足以让您忽略大部分input的其余部分。 例如：当您查看二进制search中的数组元素时，它的值告诉您可以忽略数组中的任何一个而忽略数组的“一半”。 或者类似的，你看的元素给了你足够的剩余input的一小部分的总结，你不需要看它。
- 尽pipe如此，如果在每一步中只能忽略10％的input，它仍然是对数的。
- O（n） – 你为每个input元素做了一些固定的工作量。 （但是请看下面）
- O（n log（n）） – 有几个变种。
- 你可以把input分成两堆（不超过线性时间），在每一堆上独立解决问题，然后把两堆结合起来形成最终的解决scheme。 两桩的独立性是关键。 例子：经典的recursionmergesort。
- 每个线性时间传递的数据让你一半到你的解决scheme。 例子：如果用每个分区步骤中每个元素到最后sorting位置的最大距离来思考quicksort（是的，我知道它实际上是O（n ^ 2），因为退化的枢轴select，但实际上它属于我的O（n log（n））类别。）
- O（n ^ 2） – 你必须看每一对input元素。
- 或者你不这样做，但你认为你是这样做的，而你正在使用错误的algorithm。
- O（n ^ 3） – 嗯…我没有一个活泼的人物特征。 这可能是下列之一：
- 你正在乘以matrix
- 您正在查看每对input，但是您所做的操作需要再次查看所有input
- 您的input的整个graphics结构是相关的
- O（2 ^ n） – 您需要考虑input的每个可能的子集。
没有一个是严格的。 特别是不是线性时间algorithm（O（n））：我可以想出一些例子，你必须看看所有的input，然后是一半，然后是其中的一半，或者相反 – – 将input对放在一起，然后recursion输出。 这些不符合上面的描述，因为你没有看每个input一次，但它仍然是线性时间。 但是，99.2％的时间，线性时间意味着每个input一次。
很多这些很容易显示一些非编程，如洗牌。
通过遍历整个甲板find一张黑桃王牌，然后通过整个甲板find2个黑桃，如果甲板已经向后sorting，那么将是最坏的情况n ^ 2。 你看了所有52张牌52次。
一般而言，真正不好的algorithm不一定是有意的，它们通常是其他方面的误用，比如调用一个线性的方法，这个方法是线性重复的。
好的 – 这里有一些非常好的答案，但几乎所有的人似乎都犯了同样的错误，这是普遍使用的。
非正式地，我们写出f（n）= O（g（n）），如果一个缩放因子和所有n大于某个n0，g（n） 大于 f（n）。 也就是说，f（n） 不会比g（n） 更快或者更高 。 这并不能告诉我们f（n）有多快，除了保证不会比g（n）差。
一个具体的例子：n = O（2 ^ n）。 我们都知道，n比2 ^ n增长要快得多，所以我们可以说它被指数函数所限制。 n和2 ^ n之间有很大的空间，所以它不是一个非常紧密的界限，但它仍然是一个合法的界限。
为什么我们（计算机科学家）使用边界而不是精确？ 因为a）边界通常更容易被certificate，b）它为我们提供了一个expressionalgorithm性质的空间。 如果我说我的新algorithm是O（n.log n），这意味着在最糟糕的情况下，它的运行时间将受到n.log n的n个input的约束，对于足够大的n（尽pipe见下面的评论当我可能并不意味着最坏的情况）。
相反，如果我们想说一个函数的增长和其他函数一样快，那么我们使用theta来表示这个点（我将把T（f（n））写成markdown中f（n）的\ Theta） 。 T（g（n））是由g（n）从上到下的边界，又是一个缩放因子和渐近的。
即f（n）= T（g（n））= f（n）= O（g（n））和g（n）= 0（f（n））。 在我们的例子中，我们可以看到n！= T（2 ^ n），因为2 ^ n！= O（n）。
为什么要关心这个？ 因为在你的问题中，你写'会有人抽烟写一个O（X！）？ 答案是否定的，因为基本上所有你写的东西都是由阶乘函数所限定的。 快速sorting的运行时间是O（n！） – 这不是一个严格的限制。
这里还有另一个微妙之处。 通常我们使用O（g（n））表示法讨论最坏情况的input ，所以我们正在做一个复合语句：在最糟糕的情况下，运行时间不会比使用g（n ）步骤，再次模量缩放并足够大n。 但有时我们想谈谈平均甚至最好的情况下的运行时间。
香草速溶是一个很好的例子。 在最坏的情况下，它是T（n ^ 2）（它实际上至less需要n ^ 2个步骤，但是不会太多），但是在平均情况下T（n.log n），也就是预期的步骤与n.log n成正比。 在最好的情况下，它也是T（n.log n） – 但是你可以通过例子检查数组是否已经被sorting，在这种情况下最好的运行时间是T（n）。
这与你关于这些边界的实际实现的问题有什么关系？ 那么，不幸的是，O（）符号隐藏了真实世界实现必须处理的常量。 所以尽pipe我们可以说，例如，对于一个T（n ^ 2）操作，我们必须访问每一对可能的元素，但是我们不知道有多less次要访问它们（除了它不是一个函数N）。 所以我们可以每10次访问一次，也就是10 ^ 10次，T（n ^ 2）的声明没有区别。 低阶函数也是隐藏的 – 我们可以访问每一对元素一次，每个单独的元素100次，因为n ^ 2 + 100n = T（n ^ 2）。 O（）符号背后的想法是，对于足够大的n，这根本就不重要，因为n ^ 2比100n大得多，我们甚至没有注意到100n对运行时间的影响。 然而，我们经常处理“足够小”，使得常数因素等等产生真正的显着差异。
例如，快速sorting（平均成本T（n.log n））和堆sorting（平均成本T（n.log n））都是具有相同平均成本的sortingalgorithm，但是快速sorting通常比sorting快得多。 这是因为heapsort每个元素比quicksort做了几个比较。
这并不是说O（）表示法是无用的，只是不精确。 对小n来说，这是一个相当直率的工具。
（作为这篇论文的最后一个注意事项，记住O（）表示法只是描述了任何函数的增长 – 它不一定是时间，它可能是内存，分布式系统中交换的消息或者一个并行algorithm。）
我试图通过在C＃中提供简单的代码示例来解释。
对于List<int> numbers = new List<int> {1,2,3,4,5,6,7,12,543,7};
O（1）看起来像
return numbers.First();
O（n）看起来像
int result = 0; foreach (int num in numbers) { result += num; } return result;
O（n log（n））看起来像
int result = 0; foreach (int num in numbers) { int index = numbers.length - 1; while (index > 1) { // yeah, stupid, but couldn't come up with something more useful :-( result += numbers[index]; index /= 2; } } return result;
O（n ^ 2）看起来像
int result = 0; foreach (int outerNum in numbers) { foreach (int innerNum in numbers) { result += outerNum * innerNum; } } return result;
O（n！）看起来像呃很累，想出任何简单的东西。
但是，我希望你能得到一般意见？
我向非技术型朋友描述的方式是这样的：
考虑多位数的加法。 好老式的，铅笔和纸张的补充。 你在7-8岁时学到的那种。 给定两个三位或四位数字，你可以很容易地找出他们加起来的东西。
如果我给了你两个100位数的数字，问你们加起来是多less，即使你不得不使用铅笔纸，计算出来也是非常简单的。 一个聪明的孩子可以在几分钟内做出这样的补充。 这只需要大约100次操作。
现在考虑多位乘法。 你可能了解到，大约在8或9岁。 你（希望）做了很多重复性的练习来学习它背后的机制。
现在，想象一下，我给了你两个100位数字，告诉你把它们放在一起。 这将是一个非常艰难的任务，需要你花费几个小时的时间来完成 – 而且你不可能没有错误地完成任务。 原因是（这个版本）的乘法是O（n ^ 2）; 底部数字中的每个数字必须乘以顶部数字中的每个数字，总共大约n ^ 2次操作。 在100位数字的情况下，这是10000次乘法。
不，O（n）algorithm并不意味着它会对每个元素执行一个操作。 大O符号给你一个方法来谈论你的algorithm的“速度”独立于你的实际机器。
O（n）意味着当你的input增加时，你的algorithm将会呈线性增长。 O（n ^ 2）意味着你的algorithm所花费的时间会随着input的平方增长。 等等。
我想到的方法是，你有任务清理由一个邪恶的恶棍V挑选N造成的问题，你必须估计，当他增加N时，要花多less时间来完成你的问题。
O（1） – >增加N确实没有任何区别
O（log（N）） – >每次V加倍N时，你必须花费额外的时间T来完成任务。 V再加倍N，你花费相同的金额。
O（N） – >每次V加倍N，你花费两倍的时间。
O（N ^ 2） – >每当V加倍N，你花费4倍的时间。 （这不公平！！！）
O（N log（N）） – >每次V加倍N时，花费两倍的时间再加上一点点。
这些是algorithm的界限; 计算机科学家们想要描述N的大值需要多长时间（当你在密码学中使用数字时，这是很重要的 – 如果计算机加速了10倍，还有多less位你必须使用，以确保它仍然需要100年来打破你的encryption，而不仅仅是1年？）
如果对所涉及的人有所影响的话，一些界限可能会有奇怪的表情。 在Knuth的计算机编程艺术中，我看到了一些像O（N log（N）log（log（N）））这样的东西。 （不记得我头顶的哪一个）
有一件事因为某种原因还没有被触及：
当你看到类似O（2 ^ n）或O（n ^ 3）或其他讨厌值的algorithm时，通常意味着你将不得不接受对你的问题的不完全的回答，以获得可接受的性能。
在处理优化问题时，像这样爆炸的正确解决scheme是很常见的。 在一个合理的时间内交付一个近乎正确的答案比在机器衰变成灰尘后很长时间内得到的正确答案更好。
考虑一下国际象棋：我不知道究竟是什么正确的解决scheme，但它可能是像O（n ^ 50）甚至更糟。 任何计算机在理论上都不可能真正计算出正确的答案 – 即使你使用宇宙中的每个粒子作为一个计算元素在宇宙生命的最小可能时间内执行一个操作，你仍然有很多的零。 （量子计算机能否解决这个问题是另外一回事。）
大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符号的定义，它也表示f（x）对于某个常量C只需要大于C * g（x）（这只是另一种说法，你不能帮助g（x）通过乘以一个常数来赢得竞争 – f（x）总是会赢得胜利）。 正式的定义也使用绝对值。 但是我希望我能够让它变得直观。
- 还有人不得不抽烟裂口写一个O（X！）？
不，只要使用Prolog。 如果你在Prolog中写了一个sortingalgorithm，只要描述每个元素应该比前一个更大，让回溯为你sorting，那就是O（x！）。 也被称为“排列sorting”（permutation sort）。
我喜欢don neufeld的回答，但我想我可以添加一些关于O（n log n）的内容。
一个使用简单的分而治之策略的algorithm可能是O（log n）。 最简单的例子就是在sorting列表中find一些东西。 你不是从一开始就开始扫描。 你去中间，你决定是否应该后退或前进，半途跳到你最后看的地方，并重复这个，直到你find你正在寻找的物品。
如果你看一下quicksort或者mergesortalgorithm，你会发现它们都采用了将列表分成两半的方法，对每一半进行sorting（recursion地使用相同的algorithm），然后重新组合这两个半部分。 这种recursion分治策略将是O（n log n）。
如果仔细想一想，你会发现快速sorting在整个n项上执行O（n）分区algorithm，然后在n / 2项上进行O（n）分割两次，然后在n / 4项上进行4次分割，等等…直到你得到1个项目（这是退化）的n个分区。 将n除以1得到1的次数大约是log n，每一步是O（n），所以recursion除法和征服是O（n log n）。 Mergesort以另一种方式构build，从1个项目的n个重组开始，并且完成n个项目的1个重组，其中两个sorting列表的重组是O（n）。
至于吸烟破解写一个O（n！）algorithm，你是除非你没有select。 上面提到的旅行商问题被认为是一个这样的问题。
Jon Bentley的大部分书籍（例如Programming Pearls ）都以真正实用的方式来涵盖这些内容。 他给的这个讲话包括一个这样的快速分析。
虽然这个问题不完全相关，但是Knuth提出了一个有趣的想法 ：在高中微积分课程中教Big-O符号，虽然我觉得这个想法很古怪。
把它看作是垂直叠放乐高积木（n）并跳过它们。
O（1）意味着在每一步，你什么都不做。 高度保持不变。
O（n）表示在每个步骤中，堆栈c块，其中c1是常量。
O（n ^ 2）表示在每个步骤中，堆栈c2个xn块，其中c2是一个常数，n是堆栈块的数量。
O（nlogn）表示在每个步骤中，堆栈c3 xnx log n个块，其中c3是常量，n是堆栈块的数量。
要理解O（n log n），记住log n表示n的log-base-2。 然后看看每个部分：
O（n）或多或less，当你在集合中的每个项目上进行操作时。
O（log n）是当操作的次数与你提出的指数2相同时，得到项目的数量。 例如二进制search必须将集合减半loggingn次。
O（n log n）是一个组合 – 你正在按照二进制search的方式做一些事情。 有效的sorting通常通过每个项目执行一个循环来操作，并且在每个循环中进行良好的search以find将项目或组置于正确的位置。 因此n * log n。
只是为了回应我在上面的post中的一些评论：
Domenic – 我在这个网站上，我很在乎。 不是出于任何义务，而是因为我们 – 作为程序员 – 通常关心精确性。 使用O（）符号不正确的风格，在这里做的一些渲染它是一种毫无意义; 我们也可以说在这里使用的约定下，有n ^ 2个单位的时间为O（n ^ 2）。 使用O（）不会添加任何内容。 我所说的不仅仅是常见用法和math精确度之间的小差异，它是有意义的而不是有意义的。
我认识很多许多精通这些术语的优秀程序员。 说'哦，我们是程序员，所以我们不在乎'唾弃整个企业。
一个人 – 呃，不是真的，但我明白你的意思。 对于任意大的n，不是O（1），这是O（）的定义。 它只是表明O（）限制了对有界n的适用性，我们宁愿实际谈论所采取的步骤数量，而不是对该数量的限制。
告诉你8岁的日志（n）意味着你必须砍伐一个长度为n的日志数量为2的次数，以使其达到n = 1的大小：p
O（n log n）通常是sortingO（n ^ 2）通常是比较所有的元素对
假设你有一台能解决一定规模问题的电脑。 现在想象一下，我们可以将性能提高一倍。 每增加一倍，我们可以解决多大的问题？
如果我们能解决一个两倍的问题，那就是O（n）。
如果我们有一个不是一个的乘数，这是某种多项式的复杂性。 例如，如果每翻一番，我们就可以将问题的大小增加40％左右，这是O（n ^ 2），大约30％是O（n ^ 3）。
如果我们只是添加到问题的大小，它是指数或更糟糕的。 例如，如果每个倍增手段我们可以解决一个更大的问题，那就是O（2 ^ n）。 （这就是为什么使用合理大小的密钥强制使用密码密钥变得无法实现的原因：128位密钥需要比64位处理大约16倍的处理量）。
还记得乌龟和兔子（乌龟和兔子）的寓言吗？
从长远来看，乌龟获胜，但短期内兔子获胜。
这就像O（logN）（乌龟）与O（N）（兔子）。
如果两种方法的不同之处在于他们的大O，那么他们中的一个将会赢得一个N的水平，但是大O没有说明N是多大。
为了保持诚恳的问题，我会回答这个问题，我会回答一个8岁的孩子
假设一位冰淇淋卖家准备了许多不同形状的冰淇淋（比如说N），这些冰淇淋有规律地排列着。 你想吃中间的冰淇淋
案例1： – 只有当你吃过所有比它小的冰淇淋，你才能吃冰淇淋。你将不得不吃一半冰淇淋（input）。答案直接取决于input的大小解决scheme将是o（N）
案例2： – 你可以直接在中间吃冰淇淋
解决scheme将是O（1）
案例3：只有吃过所有比它小的冰淇淋，每次吃冰淇淋时，你可以吃冰淇淋，你可以让另一个孩子（每次新来的孩子）吃所有的冰淇淋。总共花费的时间是N + N + N …….（N / 2）次解答将是O（N2）
log（n）表示对数增长。 一个例子就是分而治之的algorithm。 如果数组中有1000个已sorting的数字（例如3,10,34,244,1203 …），并且希望在列表中search一个数字（find它的位置），则可以从检查数组数字在索引500.如果它低于你所寻找的，跳到750.如果它高于你所寻找的，跳到250.然后你重复这个过程，直到你find你的价值（和关键）。 每次我们跳过一半的search空间时，我们可以挑选出许多其他值，因为我们知道数字3004不能超过数字5000（请记住，它是一个sorting列表）。
n log（n）则表示n * log（n）。
除了技术术语和math概念之外，我会试着写一个真正的八岁男孩的解释。
像一个
O(n^2)操作到底会做什么？
如果你参加一个聚会，聚会上还有n人，包括你在内。 多less次握手才能让每个人都握手，因为人们可能会忘记他们在某个时候握手的人。
注意：这近似于一个产生n(n-1)的单形，其接近n^2 。
And what the heck does it mean if an operation is
O(n log(n))?
Your favorite team has won, they are standing in line, and there are n players in the team. How many hanshakes it would take you to handshake every player, given that you will hanshake each one multiple times, how many times, how many digits are in the number of the players n .
Note: this will yield n * log n to the base 10 .
And does somebody have to smoke crack to write an
O(x!)?
You are a rich kid and in your wardrobe there are alot of cloths, there are x drawers for each type of clothing, the drawers are next to each others, the first drawer has 1 item, each drawer has as many cloths as in the drawer to its left and one more, so you have something like 1 hat, 2 wigs, .. (x-1) pants, then x shirts. Now in how many ways can you dress up using a single item from each drawer.
Note: this example represent how many leaves in a decision-tree where number of children = depth , which is done through 1 * 2 * 3 * .. * x
