algorithm - 八岁的Big-O？

Question

我正在询问更多关于这对我的代码意味着什么。我从数学上理解这些概念，我只是很难理解它们在概念上的含义。例如，如果要对数据结构执行 O(1) 操作，我知道它必须执行的操作数量不会增加，因为有更多项目。O(n) 操作意味着您将对每个元素执行一组操作。有人可以在这里填空吗？

就像 O(n^2) 操作到底会做什么？
如果一个操作是 O(n log(n))，这到底意味着什么？
是否有人必须抽大麻才能写出 O(x!)？

score 299 · Accepted Answer

一种思考方式是：

O(N^2) 意味着对于每个元素，您都在对每个其他元素做一些事情，例如比较它们。冒泡排序就是一个例子。

O(N log N) 意味着对于每个元素，您正在做的事情只需要查看元素的 log N。这通常是因为您对可以做出有效选择的元素有所了解。最有效的排序就是一个例子，例如归并排序。

O(N!) 意味着对 N 个元素的所有可能排列做一些事情。旅行推销员就是一个例子，其中有 N! 访问节点的方法，蛮力解决方案是查看每个可能排列的总成本以找到最佳排列。

score 274 · Accepted Answer

Big-O 表示法对您的代码的重要意义在于，当您将其操作的“事物”数量增加一倍时，它将如何扩展。这是一个具体的例子：

大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) 的冒泡排序。对 10 个事物进行排序时，快速排序比冒泡排序快 3 倍。但是当对 100 件东西进行排序时，它的速度要快 14 倍！显然，选择最快的算法很重要。当您访问具有数百万行的数据库时，这可能意味着您的查询在 0.2 秒内执行与花费数小时之间的差异。

要考虑的另一件事是，糟糕的算法是摩尔定律无法解决的问题。例如，如果您有一些 O(n^3) 的科学计算，并且它每天可以计算 100 件事情，那么将处理器速度加倍只会让您每天处理 125 件事情。但是，将该计算降低到 O(n^2) 并且您每天要做 1000 件事情。

澄清： 实际上，Big-O 并没有说不同算法在相同特定大小点上的比较性能，而是关于相同算法在不同大小点上的比较性能：

                 计算 计算 计算
大O | 10 件事 | 100 件事情 | 1000 件东西
-------------------------------------------------- --------------------
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

score 115 · Accepted Answer

您可能会发现将其可视化很有用：

大 O 分析

此外，在 LogY/LogX尺度上，函数n ^1/2、n、n ² 看起来都像直线，而在LogY/X尺度上2 ⁿ、 en 、10 ⁿ 是直线和ⁿ ! 是线性的（看起来像n log n）。

score 72 · Accepted Answer

这可能太数学了，但这是我的尝试。（我是一名数学家。）

如果某个东西是 O( f ( n ))，那么它在n 个元素上的运行时间将等于A f ( n ) + B （例如，以时钟周期或 CPU 操作来衡量）。理解你也有这些常量A和B的关键是，它们来自特定的实现。B本质上表示您的操作的“恒定开销”，例如您执行的一些预处理不依赖于集合的大小。A代表您的实际项目处理算法的速度。

不过，关键是您使用大 O 表示法来计算某些东西的缩放程度。所以这些常数并不重要：如果你想弄清楚如何从 10 项扩展到 10000 个项目，谁在乎恒定的开销B？同样，其他问题（见下文）肯定会超过乘法常数A的权重。

所以真正的交易是f ( n )。如果f与n完全不增长，例如f ( n ) = 1，那么您将获得惊人的扩展——您的运行时间将始终为A + B。如果f随n线性增长，即f ( n ) = n，您的运行时间将与预期的一样好——如果您的用户等待 10 ns 10 个元素，他们将等待 10000 ns 10000元素（忽略附加常数）。但如果它增长得更快，比如n ²，那么你就有麻烦了；当您获得更大的收藏时，事情将开始放缓太多。f ( n ) = n log( n ) 通常是一个很好的折衷方案：您的操作不能简单到提供线性缩放，但是您已经设法减少了一些东西，使其缩放比f好得多( n ) = n ²。

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

O(1)：从数组中检索元素。我们确切地知道它在内存中的位置，所以我们就去获取它。集合有 10 个项目或 10000 个都没有关系；它仍然在索引（比如说）3，所以我们只是跳转到内存中的位置 3。
O( n )：从链表中检索元素。在这里，A = 0.5，因为平均而言，您必须经过 1/2 的链表才能找到您要查找的元素。
O( n ² )：各种“哑”排序算法。因为通常他们的策略涉及，对于每个元素 ( n )，您查看所有其他元素（因此，另一个n，给出n ²），然后将自己定位在正确的位置。
O( n log( n ))：各种“智能”排序算法。事实证明，您只需要查看 10 个^{10元素集合中的 10 个元素，就可以相对于集合中的其他}所有人对自己进行智能排序。因为其他人也将查看 10 个元素，并且紧急行为被恰到好处地编排，因此这足以产生一个排序列表。
O( n !)：一种“尝试一切”的算法，因为有（与）n！可能解决给定问题的n 个元素的可能组合。所以它只是遍历所有这些组合，尝试它们，然后在成功时停止。

score 61 · Accepted Answer

don.neufeld 的回答非常好，但我可能会分两部分来解释它：首先，大多数算法都属于 O() 的粗略层次结构。然后，您可以查看其中的每一个，以得出具有该时间复杂度的典型算法的作用的草图。

出于实际目的，似乎唯一重要的 O() 是：

O(1) “恒定时间” - 所需时间与输入的大小无关。作为一个粗略的类别，我会在这里包括诸如哈希查找和联合查找之类的算法，即使它们实际上都不是 O(1)。
O(log(n)) “对数” - 当你获得更大的输入时它会变慢，但是一旦你的输入变得相当大，它就不会发生足够的变化来担心。如果您的运行时可以使用合理大小的数据，您可以使用尽可能多的额外数据淹没它，它仍然可以。
O(n) “线性” - 输入越多，花费的时间越长，在一个平衡的权衡中。输入大小的三倍将花费大约三倍的时间。
O(n log(n)) “优于二次” - 增加输入大小会造成伤害，但仍然可以管理。该算法可能是不错的，只是潜在问题比那些可以在线性时间内解决的问题更困难（决策相对于输入数据的本地化程度较低）。如果您的输入大小达到那里，不要假设您必须处理两倍的大小而不改变您的架构（例如，通过将事情转移到夜间批处理计算，或者不做每帧的事情）。不过，如果输入大小增加一点也没关系；请注意倍数。
O(n^2) “二次” - 它实际上只能达到你输入的一定大小，所以要注意它可以有多大。此外，您的算法可能很糟糕——仔细想想是否有一个 O(n log(n)) 算法可以满足您的需求。一旦您来到这里，就非常感谢我们所拥有的令人惊叹的硬件。不久前，你试图做的事情对于所有实际目的来说都是不可能的。
O（n ^ 3）“立方” - 在质量上与O（n ^ 2）并没有什么不同。同样的评论也适用，只是更是如此。一个更聪明的算法很有可能将这个时间缩短到更小的时间，例如 O(n^2 log(n)) 或 O(n^2.8...)，但话又说回来，它很有可能不值得麻烦。（您的实际输入大小已经受到限制，因此更聪明的算法可能需要的常数因素可能会淹没它们在实际案例中的优势。此外，思考很慢；让计算机咀嚼它可能会节省您的时间总体。）
O（2 ^ n）“指数” - 问题要么从根本上计算困难，要么你是个白痴。这些问题对他们来说具有可识别的味道。您的输入大小有一个相当具体的硬限制。你会很快知道你是否符合这个限制。

就是这样。还有许多其他可能性适合这些（或大于 O(2^n)），但它们在实践中并不经常发生，并且它们在质量上与其中一种没有太大区别。三次算法已经有点牵强了。我只包括它们是因为我经常遇到它们值得一提（例如矩阵乘法）。

这些类型的算法实际上发生了什么？好吧，我认为你有一个好的开始，尽管有很多例子不符合这些特征。但对于上述情况，我想说它通常是这样的：

O(1) - 您最多只能查看固定大小的输入数据块，并且可能没有。示例：排序列表的最大值。
- 或者您的输入大小是有界的。示例：两个数字相加。（请注意，N 个数字相加是线性时间。）
O(log n) - 输入的每个元素都告诉您足以忽略输入其余部分的很大一部分。示例：当您在二进制搜索中查看数组元素时，它的值告诉您可以忽略数组的“一半”而不查看其中任何一个。或者类似地，您查看的元素为您提供了您不需要查看的剩余输入的一小部分的足够摘要。
- 不过，对半没有什么特别之处——如果你在每一步只能忽略 10% 的输入，它仍然是对数的。
O(n) - 你为每个输入元素做一些固定的工作。（但见下文。）
O(n log(n)) - 有几个变体。
- 您可以将输入分成两堆（不超过线性时间），在每一堆上独立解决问题，然后将两堆组合形成最终解决方案。两桩的独立性是关键。示例：经典递归归并排序。
- 数据上的每一次线性时间传递都会使您获得解决方案的一半。示例：快速排序，如果您考虑每个分区步骤中每个元素到其最终排序位置的最大距离（是的，我知道它实际上是 O(n^2)，因为退化的枢轴选择。但实际上，它属于我的 O(n log(n)) 类别。）
O(n^2) - 你必须查看每一对输入元素。
- 或者你没有，但你认为你有，而且你使用了错误的算法。
O(n^3) - 嗯......我对这些没有一个活泼的特征。它可能是其中之一：
- 你正在乘以矩阵
- 您正在查看每一对输入，但您所做的操作需要再次查看所有输入
- 您输入的整个图形结构是相关的
O(2^n) - 您需要考虑输入的每个可能子集。

这些都不严谨。特别是非线性时间算法（O（n））：我可以提出一些示例，您必须查看所有输入，然后是其中的一半，然后是其中的一半，等等。或者反过来 - - 您将输入对折叠在一起，然后在输出上递归。这些不符合上面的描述，因为您没有查看每个输入一次，但它仍然以线性时间出现。尽管如此，在 99.2% 的情况下，线性时间意味着查看每个输入一次。

score 22 · Accepted Answer

其中很多很容易用非编程的东西来演示，比如洗牌。

通过遍历整副牌找到黑桃 A，然后遍历整副牌找到黑桃 2 对一副纸牌进行排序，如果这副牌已经倒序排列，则以此类推将是最坏的情况 n^2。你看了所有 52 张牌 52 次。

一般来说，真正糟糕的算法不一定是故意的，它们通常是对其他东西的滥用，比如在其他方法中调用一个线性方法，该方法在同一集合上线性重复。

score 20 · Accepted Answer

我尝试通过在 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 ² ) 看起来像

int result = 0;
foreach (int outerNum in numbers)
{
    foreach (int innerNum in numbers)
    {
        result += outerNum * innerNum;
    }
}
return result;

O(n!) 看起来，嗯，想出任何简单的东西都累了。
但我希望你明白一般的意思吗？

score 19 · Accepted Answer

好的 - 这里有一些非常好的答案，但几乎所有答案似乎都犯了同样的错误，而且这是一个普遍使用的错误。

非正式地，我们写 f(n) = O( g(n) ) 如果直到一个比例因子并且对于所有大于某个 n0 的 n，g(n)大于f(n)。也就是说，f(n) 的增长速度不快于 g(n)，或者由g(n) 限制。这并没有告诉我们 f(n) 增长的速度有多快，除非它保证不会比 g(n) 差。

一个具体的例子：n = O( 2^n )。我们都知道 n 的增长速度比 2^n 慢得多，因此我们有权说它是由上述指数函数限制的。n 和 2^n 之间有很大的空间，所以它不是一个非常严格的界限，但它仍然是一个合法的界限。

为什么我们（计算机科学家）使用界限而不是精确？因为 a) 边界通常更容易证明，并且 b) 它为我们提供了表达算法属性的简写。如果我说我的新算法是 O(n.log n)，这意味着在最坏的情况下，它的运行时间将由 n.log n 在 n 输入上从上方限定，对于足够大的 n（尽管请参阅下面的评论关于什么时候我可能不是指最坏的情况）。

相反，如果我们想说一个函数的增长速度与其他函数一样快，我们使用theta来说明这一点（我会写 T( f(n) ）来表示 \Theta of f(n) in markdown） . 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) ) 表示法时，我们谈论的是最坏情况输入，因此我们正在做一个复合语句：在最坏情况下，运行时间不会比采用 g(n) 的算法差) 步骤，再次模缩放和足够大的 n。但有时我们想谈谈平均甚至最佳情况的运行时间。

与以往一样，香草快速排序是一个很好的例子。在最坏的情况下是 T(n^2)（实际上至少需要 n^2 步，但不会显着更多），但在平均情况下是 T(n.log n)，也就是说预期的步数与 n.log n 成正比。在最好的情况下，它也是 T(n.log n) - 但你可以改进它，例如，检查数组是否已经排序，在这种情况下，最好的情况下运行时间是 T(n)。

这与您关于这些界限的实际实现的问题有何关系？好吧，不幸的是，O() 表示法隐藏了现实世界的实现必须处理的常量。因此，尽管我们可以说，例如，对于 T(n^2) 操作，我们必须访问每对可能的元素，但我们不知道必须访问它们多少次（除了它不是n)。所以我们可能不得不访问每一对 10 次，或者 10^10 次，而 T(n^2) 语句没有区别。低阶函数也被隐藏了——我们可能不得不访问每对元素一次，每个元素访问 100 次，因为 n^2 + 100n = T(n^2)。O(·) 符号背后的想法是，对于足够大的 n，这根本不重要，因为 n^2 比 100n 大得多，以至于我们没有甚至注意到 100n 对运行时间的影响。但是，我们经常处理“足够小”的 n，以便常数因素等产生真正的、显着的差异。

例如，快速排序（平均成本 T(n.log n)）和堆排序（平均成本 T(n.log n)）都是具有相同平均成本的排序算法——但快速排序通常比堆排序快得多。这是因为堆排序比快速排序对每个元素进行更多的比较。

这并不是说 O(·) 表示法没有用，只是不精确。对于小 n 来说，这是一个相当生硬的工具。

（作为这篇论文的最后一点，请记住 O( ) 表示法只是描述了任何函数的增长——它不一定是时间，它可以是内存、分布式系统中交换的消息或所需的 CPU 数量并行算法。）

score 13 · Accepted Answer

我向我的非技术朋友描述它的方式是这样的：

考虑多位数加法。很好的老式铅笔和纸添加。你7-8岁时学的那种。给定两个三或四位数字，您可以很容易地找出它们相加的内容。

如果我给你两个 100 位的数字，然后问你它们加起来是什么，即使你必须使用铅笔和纸，也很容易弄清楚。一个聪明的孩子可以在几分钟内完成这样的加法。这只需要大约 100 次操作。

现在，考虑多位乘法。您可能在大约 8 或 9 岁时就知道了这一点。你（希望）做了很多重复的练习来学习它背后的机制。

现在，想象一下我给了你同样的两个 100 位数字并告诉你将它们相乘。这将是一项艰巨得多的任务，需要你几个小时才能完成——而且你不可能不犯错误。原因是（这个版本的）乘法是 O(n^2); 底部数字中的每个数字都必须乘以顶部数字中的每个数字，总共留下大约 n^2 次操作。对于 100 位数字，即 10,000 次乘法。

score 6 · Accepted Answer

不，O(n) 算法并不意味着它将对每个元素执行操作。Big-O 表示法为您提供了一种独立于您的实际机器来谈论算法的“速度”的方法。

O(n) 意味着你的算法所花费的时间随着你的输入增加而线性增长。O(n^2) 意味着您的算法所花费的时间随着输入的平方而增长。等等。

score 6 · Accepted Answer

我的想法是，你的任务是清理由选择 N 的邪恶恶棍 V 引起的问题，并且你必须估计当他增加 N 时需要多长时间才能完成你的问题。

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，你花费的时间是原来的两倍，再加上一点。

这些是算法的界限；计算机科学家想要描述大 N 值需要多长时间。（当您对密码学中使用的数字进行因式分解时，这一点变得很重要——如果计算机加速了 10 倍，那么还有多少位呢？您必须使用以确保他们仍然需要 100 年才能破解您的加密，而不仅仅是 1 年？）

如果对相关人员产生影响，某些界限可能会有奇怪的表达。对于某些算法，我在 Knuth 的计算机编程艺术中的某处看到了 O(N log(N) log(log(N))) 之类的东西。（不记得我的头顶上哪一个）

score 5 · Accepted Answer

由于某种原因尚未触及的一件事：

当您看到具有 O(2^n) 或 O(n^3) 之类的算法或其他讨厌的值时，这通常意味着您必须接受对问题的不完美答案才能获得可接受的性能。

在处理优化问题时，像这样爆炸的正确解决方案很常见。在合理的时间范围内提供的几乎正确的答案要好于在机器腐烂很久之后才提供的正确答案。

考虑国际象棋：我不确切知道正确的解决方案是什么，但它可能类似于 O(n^50) 甚至更糟。理论上任何计算机都不可能真正计算出正确的答案——即使你使用宇宙中的每一个粒子作为计算元素，在宇宙的生命周期内尽可能短的时间内执行一个运算，你仍然有很多零. （量子计算机能不能解决是另一回事。）

score 4 · Accepted Answer

是否有人必须抽大麻才能写出 O(x!)？

不，只需使用 Prolog。如果您在 Prolog 中编写排序算法，仅描述每个元素应该比前一个元素大，然后让回溯为您进行排序，那将是 O(x!)。也称为“排列排序”。

score 4 · Accepted Answer

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) 构成了某种“速度限制”，因为最终它会通过它并永远离开它。

这不完全是big-O notation的定义，它还指出 f(x) 对于某个常数 C 只需大于 C*g(x) （这只是另一种说法，你不能通过将 g(x) 乘以一个常数因子来帮助 g(x) 赢得比赛 - f(x) 最终总是会获胜）。正式定义也使用绝对值。但我希望我设法让它变得直观。

score 3 · Accepted Answer

我喜欢唐纽菲尔德的回答，但我想我可以添加一些关于 O(n log n) 的内容。

使用简单的分而治之策略的算法可能是 O(log n)。最简单的示例是在排序列表中查找某物。您不会从头开始扫描它。你走到中间，然后决定是向后还是向前，跳到最后一个地方，然后重复这个过程，直到找到你要找的项目。

如果您查看快速排序或合并排序算法，您会发现它们都采用将要排序的列表分成两半、对每一半进行排序（使用相同的算法，递归地）然后重新组合这两半的方法。这种递归分治策略将是 O(n log n)。

如果你仔细考虑一下，你会发现快速排序对整个 n 个项目执行 O(n) 分区算法，然后对 n/2 个项目执行 O(n) 分区两次，然后对 n/4 个项目执行 4 次，等等......直到你在 1 个项目上得到一个 n 分区（这是退化的）。将 n 分成两半得到 1 的次数大约是 log n，每一步都是 O(n)，所以递归分治是 O(n log n)。Mergesort 以另一种方式构建，从 1 项的 n 次重组开始，以 n 项的 1 次重组结束，其中两个排序列表的重组为 O(n)。

至于吸烟破解写一个 O(n!) 算法，除非你别无选择，否则你就是。上面给出的旅行商问题被认为是这样一个问题。

score 3 · Accepted Answer

把它想象成垂直堆叠乐高积木 (n) 并跳过它们。

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

O(n) 意味着在每一步，你堆叠 c 个块，其中 c1 是一个常数。

O(n^2) 意味着在每一步，你堆叠 c2 xn 个块，其中 c2 是一个常数，n 是堆叠块的数量。

O(nlogn) 意味着在每一步，你堆叠 c3 xnx log n 个块，其中 c3 是一个常数，n 是堆叠块的数量。

score 2 · Accepted Answer

大多数 Jon Bentley 的书籍（例如Programming Pearls）都以非常实用的方式涵盖了这些内容。他的这次演讲包括对快速排序的一个这样的分析。

虽然与这个问题并不完全相关，但 Knuth 提出了一个有趣的想法：在高中微积分课上教授 Big-O 符号，尽管我觉得这个想法很古怪。

score 1 · Accepted Answer

要理解 O(n log n)，请记住 log n 表示 n 的 log-base-2。然后看每个部分：

当您对集合中的每个项目进行操作时，O(n) 或多或少是。

O(log n) 是当操作数与您提高 2 的指数相同时，以获得项目数。例如，二进制搜索必须将集合切成一半 log n 次。

O(n log n) 是一个组合——你正在对集合中的每个项目进行二进制搜索。有效的排序通常通过对每个项目执行一个循环来操作，并且在每个循环中进行良好的搜索以找到合适的位置来放置有问题的项目或组。因此 n * log n。

score 1 · Accepted Answer

只是为了回应我上面帖子中的几条评论：

Domenic - 我在这个网站上，我在乎。不是为了学究气，而是因为我们——作为程序员——通常关心精度。以某些人在这里所做的风格错误地使用 O( ) 表示法会使其毫无意义；在此处使用的约定下，我们也可以说某事需要 n^2 单位时间作为 O( n^2 )。使用 O( ) 不会增加任何东西。我所说的不仅仅是常用用法和数学精度之间的微小差异，而是有意义和没有意义之间的差异。

我认识很多很多优秀的程序员，他们准确地使用了这些术语。说“哦，我们是程序员，所以我们不在乎”会降低整个企业的成本。

onebyone - 好吧，虽然我同意你的观点，但不是真的。对于任意大的 n，它不是 O(1)，这是 O(·) 的一种定义。它只是表明 O(·) 对于有界 n 的适用性有限，我们宁愿实际谈论所采取的步骤数，而不是该数字的界限。

score 1 · Accepted Answer

告诉你 8 岁的 log(n) 意味着你必须将长度为 n 的 log 砍成两半才能缩小到 n=1 的次数：p

O(n log n) 通常是排序 O(n^2) 通常是比较所有元素对

score 1 · Accepted Answer

假设您有一台可以解决一定规模问题的计算机。现在想象一下，我们可以将性能提高几倍。每次翻倍可以解决多大的问题？

如果我们能解决两倍大小的问题，那就是 O(n)。

如果我们有一些不是一个的乘数，那就是某种多项式复杂度。例如，如果每次加倍允许我们将问题大小增加约 40%，则为 O(n^2)，约 30% 为 O(n^3)。

如果我们只是增加问题的大小，它是指数级的或更糟。例如，如果每次加倍意味着我们可以解决一个更大的问题，那就是 O(2^n)。（这就是为什么使用合理大小的密钥来暴力破解密码密钥实际上变得不可能：128 位密钥需要大约 16 万亿倍的处理量是 64 位的。）

score 1 · Accepted Answer

还记得乌龟和兔子（乌龟和兔子）的寓言吗？

从长远来看，乌龟赢了，但从短期来看，兔子赢了。

这就像 O(logN)（乌龟）与 O(N)（野兔）。

如果两种方法的 big-O 不同，则存在一个 N 水平，其中一个会获胜，但 big-O 没有说明 N 有多大。

score 1 · Accepted Answer

为了对提出的问题保持真诚，我会像回答一个 8 岁的孩子一样回答这个问题

假设一个冰淇淋卖家准备了许多不同形状的冰淇淋（比如 N 个），它们以有序的方式排列。你想吃中间的冰淇淋

案例1：-只有吃完所有比它小的冰淇淋才能吃冰淇淋你必须吃掉所有准备好的冰淇淋的一半（输入）。答案直接取决于输入的大小解决方案将是o(N) 阶

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

解决方案将是 O(1)

案例3：只有当你吃完所有比它小的冰淇淋时，你才能吃冰淇淋，并且每次吃冰淇淋都让另一个孩子（每次都是新孩子）吃掉他所有的冰淇淋总时间为N + N + N.......(N/2) 次解将是 O(N2)

score 0 · Accepted Answer

log(n) 表示对数增长。一个例子是分而治之的算法。如果您在数组中有 1000 个已排序的数字（例如 3、10、34、244、1203 ...）并且想要在列表中搜索一个数字（找到它的位置），您可以从检查索引 500 处的数字。如果它低于您所寻求的值，则跳至 750。如果它高于您所寻求的值，则跳至 250。然后重复该过程，直到找到您的值（和键）。每次我们跳过一半的搜索空间，我们可以剔除测试许多其他值，因为我们知道数字 3004 不能高于数字 5000（请记住，它是一个排序列表）。

n log(n) 则表示 n * log(n)。

score 0 · Accepted Answer

除了技术术语和数学概念之外，我将尝试为一个真正的八岁男孩写一个解释。

就像手术到底会O(n^2)做什么？

如果您参加聚会，并且聚会中n有人，包括您。考虑到人们可能会忘记他们在某个时候与谁握手，需要多少次握手才能使每个人都与其他人握手。

注意：这近似于一个n(n-1)足够接近的单纯形屈服n^2。

如果手术是什么意思O(n log(n))？

你最喜欢的球队赢了，他们排着队，队里有n球员。考虑到您将与每个玩家握手多次，玩家人数中有多少个数字，您与每个玩家握手需要多少次握手n。

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

有没有人必须抽crack才能写O(x!)？

你是个有钱的孩子，你的衣柜里有很多衣服，x每种衣服都有抽屉，抽屉是相邻的，第一个抽屉有一件物品，每个抽屉里的衣服和抽屉里的衣服一样多它的左边还有一个，所以你有1帽子，2假发，..(x-1)裤子，然后是x衬衫。现在，您可以通过多少种方式使用每个抽屉中的单个物品来装扮。

注意：这个例子表示决策树中有多少叶子在哪里number of children = depth，这是通过1 * 2 * 3 * .. * x

algorithm - 八岁的Big-O？

25 回答 25

Related

Reference