大O八岁的孩子?[重复]

Question

这个问题已经有一个答案在这里：

• 什么是一个普通的英语解释"大O"符号? 39的答案

我问的更多有关这意味着什么向我的代码。我理解的概念从数学上来说，我只有一个困难时期的包裹我的头左右他们的意思是什么概念上.例如，如果一个人执行一个O(1)操作一个数据结构，我的理解是，操作的数量也有执行不会增长，因为有更多的项目。和一个O(n)行动将意味着你将执行一组行动在每个元素。可能有人填补空白，这里？

• 喜欢什么将一个O(n^2)操作做什么？
• 和什么这是否意味着如果一个操作O(n log(n))?
• 并且有人要吸毒写O(x!)?

Answer 1

一种思维方式是这样的：

O(N^2)用于每一个元素，你正在做的事情与所有其他元素，例如比较。泡泡排序是这样的一个例子。

O(N记录N)用于每一个元素，你正在做的事情，只需要看看记录N的要素。这通常是因为你知道一些关于元素，让你做一个有效的选择。最有效的各种各样都是这方面的一个例子，例如合并排序。

O(N!) 意味着做一些事情所有可能的排列的N元素。旅行推销员是这方面的一个例子，那里有N!种方式访问的节点，而暴力的解决方案是看在费用总额的每一个可能的置换，以找到最佳之一。

Answer 2

一件大事，大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(n日志(n))与气泡的排序，这是O(n^2).当分类10个东西，快速排序的3倍的速度比泡泡排序。但是，当排序100事情，这是14倍的速度！清楚地挑选最快的算法是重要的。当你得到的数据库万行，它可以意味着之间的差您的查询执行在0.2秒，而把时间。

另一个要考虑的是，恶劣的算法是一件事，摩尔法律不能有帮助。例如，如果你已经有了一些科学计算，这是O(n^3)和可以计算100事情一天，加倍的处理速度只有得到你125事情一天。然而，把那计算O(n^2)和你在做1000事情一天。

澄清： 实际上，大-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

Answer 3

你可能会发现它很有用的可视化：

此外，上 LogY/LogX 规模的功能 n^1/2, n,n² 所有的看起来像 直线, ，而上 LogY/X 规模 2ⁿ, eⁿ, 10ⁿ 是直线路和 n! 是linearithmic(看起来像 n记录n).

Answer 4

这可能是过学，但这是我的尝试。(I 我 一个数学家。)

如果东西是O(f(n))，那么它的运行上的时间 n 元素将等于 一个 f(n) + B (测量，比如说，时钟周期或CPU操作)。这是关键的理解，你还有这些常量 一个 和 B, ，其产生的具体实施。 B 代表实质上的"常开销"的操作，例如一些预处理，你做的，并不取决于大小的集合。 一个 表示的速度实际项目处理算法。

关键的是，使用大O谱图找出 多好的东西会的规模.因此，那些常不会真正的问题:如果你想找出如何规模的10至10000项目，谁关心的恒的开销 B?同样，其他的关切(见下文)肯定会大于重量的乘法定 一个.

所以真正的交易 f(n).如果 f 增长没有带 n, 如 f(n)=1，则只规模惊人---你的运行时间将始终只是 一个 + B.如果 f 线性增长与 n, 即 f(n) = n, ，您的运行时间将扩大很多，因为更好的如可以预计的---如果你的用户等待的10ns，10要素，他们会等10000ns10000元(忽略的添加剂一定)。但是，如果它长得更快,喜欢 n², 那你就是在麻烦；事情将开始缓慢下来了太多的时候你得到较大的集合。 f(n) = n 日志(n)是一个很好的妥协，通常为：你的操作不可能那么简单，因为给线扩展，但你已经成功地削减下来的东西这样的，它会规模比 f(n) = n².

实际上，这里有一些很好的例子：

• O(1):检索的一个元件阵列。我们确切地知道它是在记忆，所以我们只是去得到它。不要紧，如果收集有10个项目或10000;它还在指标(说)3，所以我们只是跳来的位置3存储器中。
• O(n):检索的一个元素从一个链接清单。在这里， 一个 =0.5，因为平均上你"我必须要经过的1/2的列表之前，你找到你要寻找的。
• O(n²):各种"哑"排序的算法。因为通常他们的战略涉及，对于每一个元素(n)，你看看所有其他元素(如此次另一个 n, 给 n²)，然后给自己定位在正确的地方。
• O(n 日志(n)):各种"智能"排序的算法。事实证明，你只需要看看说，10元在10¹⁰-元的收集智能种自己相对于 每个人都 他在集合。因为别人都是 还 要看看10个单元，以及紧急行为是策划的只是正确的，所以，这是不够产生一种排序的清单。
• O(n!):一种算法，"尝试一切"，因为有(成比例) n!可能的组合 n 元素可能解决特定的问题。因此，它只是循环，通过所有这样的组合，试图将它们，然后停止，只要它成功。

Answer 5

唐。neufeld的答案是非常好，但我可能会解释它在两个部分：第一，有一个粗略的层次结构的O()'s大多数的算法，落入。然后，你可以看看那些来了素描什么 典型的 算法的时的复杂性做。

出于实际目的，只O()'s曾经似乎要问题是：

• O(1)"时间常数"-所需的时间是独立的尺寸的输入。作为一个粗略的类别，我将包括诸如哈希查找和联盟-找到这里，即使没有这些都是实际上O(1)。
• O(日志(n))"对数"-它变得较慢的因为你会得到更大的投入，但是一旦你输入获得相当大，它不会改变，足以担心的。如果你的运行时确定合理的大小的数据，你可以沼泽它与尽可能多的额外的数据正如你想要的，它将仍然是确定。
• O(n)"线性"-更多的输入花费的时间越长，甚至折衷。三次输入大会采取的大约三倍之久。
• O(n日志(n))"比二次"-增加输入大伤害，但它仍然易于管理。算法可能是体面的，它只是基本问题更难(决定是较本地化的相对于所输入的数据)于这些问题是可以解决在线性时间。如果输入您的尺寸是得到了那里，不要以为你可以必处理两倍的大小而不改变你的建筑周围(例如通过移动的东西到过夜的批量计算，或者没有做的事情，每帧)。这是确定的，如果输入的尺寸增加了一点点，虽然；只是看出来的倍数。
• O(n^2)"二次"-这真的只会的工作达到一定规模的投入，所以注意有多大，它可以得到的。还有，你的算法可能会吸--认为很难看出如果有一个O(n日志(n))的算法，会给你你需要什么。一旦你在这里，觉得很感激的惊人的硬件我们已经有天赋。不久前，你们试图要做的就不可能为所有实际目的。
• O(n^3)"立方体"-不定性所不同，从O(n^2).同一评论适用，只有更是如此。有一个体面的机会，一个更聪明的算法可能刮胡子这个时候下降到更小的东西，例如O(n^2日志(n))或O(n^2.8...)，但随后又有一个很好的机会，这不会是值得的麻烦。(你已经有限，在实际输入的大小，所以恒的因素，可能需要的更加聪明的算法将可能的沼泽他们的优势实际情况。此外，思想是慢；让计算机咀嚼就可以节省你的时间整体。)
• O(2^n)"指数"的问题要么是根本计算上难或者你是一个白痴。这些问题有一个可识别的风味。你输入尺寸限制在一个相当特定的硬限制。你会很快知道你是否适合进入该限制。

就是这样。还有许多其他的可能性，适应之间的这些(或更大比O(2^n))，但是他们并不经常发生这样的情况在实践中，他们并不质量太大的不同，从其中的一个。立算法已经是一位的拉伸；我只包括他们，因为我碰到他们常常足以值得一提的是(例如矩阵乘).

什么是实际发生的事情对于这些类的算法？好吧，我想你有一个良好的开端，尽管有许多实例，不适合这些特性。但对于上述，我要说，它通常是这样的：

• O(1)-你只是寻找最多在一个固定的尺寸的大块输入数据，并有可能没有它。例如：最大的排序的清单。
  • 或输入您的尺寸是有界。例如：另外两个数字。(注意，除了N号码是线性时间)。
• O(日志n)-每个元素的输入您的告诉你足够忽略的一个很大一部分其余的输入。例如：当你看着一系列元素在二进制的搜索，其价值告诉你，你可以忽略"的一半"的阵列不看它的任何。或者是类似的，你看看给你足够的摘要的一小部分剩余输入你不需要来看待它。
  • 没有什么特别的半，虽然--如果你只能忽略了10％的输入在每一个步骤，它仍然对数。
• O(n)-你做一些固定工作量每个输入单元。(但请见下文。)
• O(n日志(n))-有几个变异体。
  • 你可分输入到两桩(不超过直线时间)，解决了问题，独立于每一桩，然后结合起来的两桩形成最终的解决方案。独立的两桩是关键。例如：经典递归成了归并排序。
  • 每个线性时间通过数据得到你一半你的解决方案。例如：快速排序，如果你认为在条款的最大距离的每一个元件对其最后排位置，在每个分区的步骤(是的，我知道，它实际上是O(n^2)，因为退化的枢轴的选择。但是，实际而言，它属于我的O(n日志(n))的类别。)
• O(n^2)-你要看看每一对输入的单元。
  • 或你没有，但你认为你做的，你正在使用错误的算法。
• O(n^3)-嗯...我没有一个活泼的表征。它可能是一种：
  • 你乘以矩阵
  • 你看着每一个对投入，但操作你不需要寻找在所有的再投入
  • 整个结构图你的输入是相关的
• O(2^n)-你需要考虑每一个子集的可能的投入。

所有这些都是严格的。特别是不是直线时间算法(O(n)):我可以拿出一些例子里，你需要看看所有的输入，然后他们中的一半，那么一半，等等。或其他的方式--你们折叠在一起对投入，然后recurse上的输出。这些不适合的说明中所述，既然你不看着每一个输入一旦，但它仍然出来的线性时间。仍然，99.2%的时间，线性时间意味着在每个输入一次。

Answer 6

很多这些容易证明的东西非编程，像洗牌的卡片。

排序的一副牌通过的整个甲板上找到黑桃,然后通过整个甲板上找到2个黑桃等将是最糟糕的是n^2,如果在甲板上已经排倒退。你看了所有52张牌52倍。

在一般的真的很糟糕算法不一定是故意的，他们通常滥用别的东西，像叫一个方法就是直线内部的其他一些方法，重复了同样的定线性。

Answer 7

确定-有一些非常好的答案在这里，但几乎所有的人似乎都犯同样的错误，它是一个普遍共同的使用情况。

非正式的，我们写信，f(n)=O(g(n))，如果达到扩缩系数和所有n大于一些n0、g(n) 大 比f(n)。这是f(n) 增长没有更快的 比，或者是 界定从上面 由、g(n)。这告诉我们没有关于如何快速f(n)的增长，节省的事实，即这是保证不以任何比克(n)。

一个具体的例子：n=O(2^n)。我们都知道，n增长更迅速地于2^正，以便我们有权要说，它是界上所通过的指数函数。有很多的房间n and2^正，所以它不是一个非常 紧 约束，但它仍然是一个合法的约束。

我们为什么(计算机科学家)的使用范围，而不是确切的?因为)的界限往往更容易证明和b)它给我们一个简短的手表性的算法。如果我说，我的新算法是O(n.记录n)这意味着，在最糟糕的是其运行时间将界定从上由n。日志上的n的n的投入，对于足够大的n(虽然看我下面的评论时，我可能不是最糟糕的情况下)。

如果相反，我们想说，一个函数的增长完全一样迅速，因为其他一些功能，我们使用 theta 做出这一点(我会写T(f(n))为指 heta的f(n)在降价).T(g(n))的简短手为被界从 上面和下面 通过g(n)，再一次，扩展因素和渐进.

这是f(n)=T(g(n)) <=>f(n)=O(g(n))和g(n)=O(f(n))。在我们的例子，我们可以看到，n!= T(2^n)因为2^n!= O(n)。

为什么关心这个?因为在你的问题你写'将有人要吸毒写O(x!)?' 答案是没有-因为你写的一切将有界从上述因素的功能。的运行时间为快速排序是O(n!) -它不仅仅是一个紧密结合。

还有另一个层面的微妙在这里。通常我们都在谈论 最糟糕的情况下输入 当我们使用O(g(n))的符号，这样，我们正在做一个合声明：在最糟糕的情况下运行时间将不会有任何差于一种算法，考克(n)的步骤，再次模扩展和足够大的n.但有时我们要谈的运行时间 平均 甚至 最好的 情况。

香草的快速排序，与以往一样，一个很好的例子。它是T(n^2)在最糟糕情况(它实际上将至少需要正^2步骤，但不明显的更多)，但T(n.记录n)在一般情况下，也就是说预期数量的步骤是成正比。登录n。在最好的情况下，它也是T(n.记录n)-但是你可以改进，为，通过例如检查，如果所列的是已经排序在这种情况下，最好的情况下运行时间将是T(n)。

如何这涉及到你的问题有关的实际实现这些界限?好了，不幸的是，O()表示法常隐藏其真实世界的实现必须处理。因此，虽然我们可以说，例如，对于一个T(n^2)操作的，我们访问的每一个可能的一对因素，我们不知道有多少次我们要访问他们(除，这不是一个功能n)。因此，我们可能要访问的每一对10倍，或10^10倍，和T(n^2)声明没有区别。低阶的职能还隐藏-我们可能要访问的每一对因素一次，并且每一单个元素的100倍，因为n^2+100n=T(n^2).背后的想法O()表示法是，足够大的n,这个并不重要，因为在所有正^2得到这么多大比100n，我们甚至不通知的影响100n在运行时间。然而，我们经常处理的'足够小的'n这样的认定因素，因此在做一个真正的显着差异。

例如，快速排序(平均成本T(n.记录n))和heapsort(平均成本T(n.记录n))的两个排序的算法具有相同的平均费用-但快速排序通常远远快于heapsort.这是因为heapsort不多几个比较每个元素比的快速排序.

这并不是说O()表示法是无用的，只是不精确的。这是一个相当钝的工具运用于小n.

(作为最后注意到这篇论文，请记住，O()符号仅描述了成长的任何功能的-它不一定必须要时间，它可以存储、信息交换，在一种分布式系统或数量处理器需要一个并行的算法。)

Answer 8

我试着解释给简单的代码的例子。

对于 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日志(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!) 看起来像，嗯，到累起来的东西简单。
但我希望你获得一般性的观点？

Answer 9

我的描述它对我非技术性的朋友是这样的：

考虑多位之外。好的老式、铅笔和纸。你学会了当你还是7到8岁。鉴于两三个或四位数字的号码,你可以找到什么他们加起来相当容易。

如果我给了你两个100位数字，问你什么是他们加起来，找出它将是非常简单，甚至如果你不得不使用铅笔和纸张。一个聪明的孩子能做这样的一个外在只有几分钟。这只会需要大约100行动。

现在，考虑多数乘法运算。你可能了解到，在围绕8或9岁。你(希望)做了很多的重复演习，以了解该机制。

现在，想象一下我给你的那些相同的两个100位数字，并告诉您乘他们在一起。这将是一个多， 很多 难任务，这要花时间来做的-那你不可能做到的，没有错误。为此原因是，(该版本)乘是O(n^2);每个数字在底部的数量必须乘以每个数字在上面的数字，而使总共约n^2操作。在这种情况下的100位数字的号码，这是10 000名乘法。

Answer 10

不,O(n)的算法并不意味着它将执行一个操作上的每一个元素。大O符号为您提供了一种方式谈论"速度"你的算法独立的实际机。

O(n)意味着，时间你算法将采取线性增长作为你的输入增加。O(n^2)意味着，时间你算法需要随之增加，因为方的输入。等等。

Answer 11

我想它是你们的任务清理问题引起的一些邪恶的坏人V谁选N,和你需要估算出多少时间，它需要完成你的问题时，他增加了N

O(1)->增加N真的不做任何区别

O(日志(N))->每次五倍N，你必须花费额外的时间T完成任务。V双N再和你度过的同样的金额。

O(N)->每次五倍N,你花两倍的时间。

O(N^2)->每次五倍N,你花4倍尽可能多的时间。(这是不公平的!!!)

O(N日志(N))->每次五倍N,你花两倍的时间加上多一点。

这些边界的一个算法；计算机科学家们想描述如何，只要它是要采取大价值。(其获得重要当你是保理业务数字中使用的密码--如果计算机的速度通过一系数为10，如何更多的位做你必须使用，以确保它仍然需要他们的100年里打破你的加密而不仅仅是1年吗?)

一些范围可以有奇怪的表达，如果它有差别的人参与。我已经看到的东西，如O(N日志(N)日志(日志(N)))的地方，在Knuth的技术的计算机编程的一些算法。(不可能记得其中一个掉我的头顶)

Answer 12

有一件事还没有被感动，但对于一些原因：

当你看到的算法的事情如O(2^n)或O(n^3)或其他令人讨厌的价值观也往往意味着你必须要接受一个不完美的回答你的问题，以便获得可接受的性能。

正确的解决方案，打击起来像这样的公共当处理的优化问题。一个接近正确的答案在交付合理的时间范围是优于一个正确的答案交付的长后，机器已经腐烂的灰尘。

考虑的国际象棋：我不知道到底是什么的正确解决方案被认为是但这是可能的东西喜欢O(n^50)或甚至更糟。这在理论上是不可能的任何计算机实际计算正确的答案--甚至如果您使用的每一颗粒在宇宙中作为一个计算元件的执行作在尽可能短的时间对生活的宇宙，你还有很多零离开。(不论是一个量子计算机可以解决这个问题是另一回事。)

Answer 13

在"Intuitition"后面的大-O

想象一下，一个"竞争"的两个职能超过x,x方法无限：f(x)和g(x)。

现在，如果从某一点上(一些x)一个功能总是具有更高的价值，然后其他的，那么让我们叫这个功能的"迅速"。

因此，例如，如果为每一个x>100你看见f(x)>g(x)，然后f(x)"快速"比克(x)。

在这种情况下，我们会说g(x)=O(f(x))。f(x)构成一种"速度限制"的各种g(x)，因为最终它通过它和叶子，它后面。

这是不完全的定义 大O符号, ，它还指出，f(x)只有得大于C*克(x)对于某些恒C(这仅仅是另一种说法，你不可以帮助克(x)在竞争中取胜，通过乘以一定的因素-f(x)会总是赢的结束)。正式的定义也使用绝对值。但我希望我设法让它直观。

Answer 14

• 并且有人要吸毒写O(x!)?

没有，只是使用序言.如果你写一个排序的算法在序言中只是描述，每一单元应当能大于以前的，并让回溯做分拣你，那将是O(x!).也被称为"排序".

Answer 15

我喜欢不neufeld的答案，但我认为我可以添加的东西有关O(n记录n)。

一种算法，它使用一个简单的分而治之战略可能是O(日志n)。最简单的例子就是找到一个东西在一个排序的清单。你不从头开始扫描。你走到中间，你决定是否应该然后去向前或向后，跳一半的最后一个地方，你看，和重复，直到你找到你要找的。

如果你看着的快速排序或成了归并排序的算法，你会看到他们两个都采用的方法分割的列表可以按半，排序每半(使用同样的算法，递归的)，然后重新组合了两半。这种 递归 分而治之战略将O(n记录n)。

如果你想想看仔细，会看到，快速排序并O(n)分算法在整个n的项目，然后O(n)分区两次n/2的项目，然后是4次关于n/4个项目，等等。直到你得到一个n的分区1中的项目(被退化).的次数分n一半以得到大约1日志n、和每一个步骤是O(n)，因此递归的分而治之是O(n记录n)。成了归并排序基础的其他方式，开始n recombinations的1项，以及整理与1重组的n的项目，在重组中的两个序列表是O(n)。

至于吸烟的裂写O(n!) 算法的，你是的除非你别无选择。旅行推销员问题上给出的是据认为是这样一个问题。

Answer 16

最乔恩*宾利书籍(例如 编程珍珠)涵盖这些东西在一个非常务实的方式。 这次谈话 给他包括这样一个分析的一个快速排序.

虽然不完全相关的问题，Knuth想出了一个 有趣的想法:教学大O符号在高中的微积分类，但我找到这个想法太偏心。

Answer 17

认为这是堆叠乐高积木块(n)和垂直跳跃过他们。

O(1)意味着在每一个步骤，你什么都不做。高度保持不变。

O(n)意味着在每一个步骤，你堆c块，其中c1是一个恒定不变。

O(n^2)意味着在每一个步骤，你堆c2x n块，其中c2是一个常数，并n是堆积区块。

O(nlogn)意味着在每一个步骤，你堆c3x n x日志n块，其中c3是一个常数，并n是堆积区块。

Answer 18

了解O(n记录n)，请记住的日志n意味着登基-2n.然后看看每一个部分：

O(n)，或多或少，当你操作上的每个项目的所设置的。

O(日志n)当数量的操作是相同的指数，其中你提出的2、获得的数量的项目。二进制的搜索，例如，具有削减的设置于半日志n次。

O(n记录n)是一个组合–你在做什么线沿线的二分搜索的每个项目的所设置的。有效的各种各样经常经营过做一个循环的每个项目，并在每个循环做一个好的搜索找到正确的地方，把该项目或一组中的问题。因此n*登录n。

Answer 19

只是为了响应几点评论关于我的以上员额：

多米尼克 -我在这个网站上，我关心。不用迂腐的缘故，而是因为我们--作为编程员-通常关心的精确度。使用O()表示法错误的风格，某些已经完成在这里呈现一种没有意义的；我们可能只是不如说一些需要正^2单元的时间，因为O(n^2)根据该公约在这里使用。使用O()增加了什么。它不只是一个小型之间的差异常见的使用情况和精确的数学，我是说，它是之间的差异，它正在有意义的，它不是。

我知道很多很多优秀的编程人员使用这些术语准确。说'噢，我们的程序员，因此我们不关心'跌价的整个企业。

。参见样式 -嗯，不是真的虽然我把你的一点。这不是O(1)任意大n，这是一种定义O().它只是表明，O()具有有限的适用性界n，我们会，而实际上谈论的数量而采取的步骤，而不是一个结在这个数字。

Answer 20

告诉你八岁的日志(n)指数的时候，你要砍长n登录在两个对它来获得规模n=1:p

O(n记录n)通常为排序 O(n^2)通常是比较对所有的元素

Answer 21

假设你有计算机，可以解决的一个问题的某一大小。现在想象一下，我们可以双倍的性能几次。如何更大的问题，我们可以解决与每增加一倍?

如果我们可以解决的一个问题的两倍，这是O(n)。

如果我们有一些乘数，这不是一个，那就是某种形式的多项复杂性。例如，如果每增加一倍，使我们增加的问题，大约40%，这是O(n^2)，约有30%将O(n^3).

如果我们只是添加到问题的大小、它的指数或者更糟。例如，如果每增加一倍，这意味着我们可以解决的一个问题1更大，这是O(2^n)。(这是为什么强迫一个密码变得不可能有效地用合理的小型项：128位密钥需要大约16三次方倍的处理作为64位。)

Answer 22

记住的寓言的乌龟兔赛跑(乌龟兔子)?

从长远来看，乌龟赢得，但在短跑的兔子的胜利。

这就像O(的)(龟)与O(N)(兔子).

如果两种方法不同，在他们的大O,然后有一个水平，在其中他们中的一个将会赢得，但大-O没有多大，N。

Answer 23

保持真诚的问题我会回答这个问题的方式，我会回答的一个8岁的孩子

假设一个冰淇淋卖方准备一些冰淇淋(说N)的不同形状的安排有序的方式。你想吃冰淇淋躺在中间

案例1：-你可以吃冰淇淋只有如果你吃的所有的冰淇淋小于它 你会有吃的一半，所有的冰淇淋制(输入)。回答直接取决于尺寸的输入 解决方案将是以的o(N)

案例2：-你可以直接吃冰淇淋在中间

解决方案将O(1)

3种情况：你可以吃冰淇淋只有如果你吃的所有的冰淇淋小于它和每次你吃冰淇淋的你能让一个孩子(新的孩子，每次)以吃掉所有他的冰淇淋 总时间将是N+N+N.......(N/2)时间 解决方案将O(N2)

Answer 24

日志(n)意味着对数的增长。一个例子是，分而治之的算法。如果你有1000排中的数字阵列(前。3, 10, 34, 244, 1203 ...)，要搜索一些列表中(中找到其位置)，你可以开始检查数的数值指数的500。如果是低于你要求什么，跳到750.如果它是高于你要求什么，跳到250个。然后重复这一过程直到你找到你的价值(以及键)。每次我们跳一半的搜索空间，我们可以剔除程测试很多其他价值观，因为我们知道数3004不能上述数5000(记得，它是一个排列表)。

n日志(n)，然后装置n*日志(n)。

Answer 25

我会尝试实际编写一个解释为一个真正的八岁的男孩，除了从技术术语和数学的概念。

喜欢什么会 O(n^2) 操作做什么？

如果你是在一个缔约方，并有 n 人包括你。多少握手采取所以，每个人都有handshaked其他人一样，鉴于人们可能会忘记他们handshaked在某一点。

注：这种近似于一个单纯的收益 n(n-1) 这足够近 n^2.

和什么这是否意味着如果一个操作 O(n log(n))?

你最喜欢的球队赢了，他们正站在线，并有 n 在球员的球队。多少hanshakes它会带你到握手每个球员,你会hanshake每一个多次，有多少时间，有多少位数的球员 n.

注：这将产生 n * log n to the base 10.

并且有人要吸毒写 O(x!)?

你是一个富有的孩子，在你的衣柜里有很多的衣服，还有 x 抽屉用于每种类型的服装，抽屉旁边的每个人，第一个抽屉有1个项目，每个抽屉有尽可能多的布的抽屉到其离开和一个多，所以你有喜欢的东西 1 帽子， 2 假发,.. (x-1) 裤子，然后 x 衬衫。现在在许多方式可以你打扮使用一个单一的项目从每个抽屉。

注：这个例子表示的如何许多的叶子中的一个决定-那里的树 number of children = depth, ，这样做是通过 1 * 2 * 3 * .. * x