表达式的大 O 表示法

Question

如果我有一个需要 4n^2 + 7n 步才能完成的算法，它的 O 是多少？O(4n^2)？O(n^2)？

我知道 7n 被截断，但我不知道是否应该保留 n^2 系数。

谢谢

Answer 1

您应该放弃任何系数，因为真正的问题是，它试图将其定性为线性，指数，对数等“的顺序”问......也就是说，当n是非常大的，系数是不太重要。

这也解释了为什么你放下+ 7N，因为当n是非常大的，这个词有最终的答案比较意义不大。如果您熟悉微积分，你可能会说廉N-> INF（4 * N ^ 2 + 7N）〜= LIM N-> INF（4 * N ^ 2）〜= LIM N-> INF（N ^ 2）

您也可以考虑一下这款在图形感......也就是说，如果你绘制图形的函数4N ^ 2 + 7N对越来越大的n值，数学家可能会说“它看起来像N ^ 2”。当然，它必须是一个相当自由的数学家，因为这不是一个严谨的说法，但是这基本上是O（...）想传达。

Answer 2

在系数不是在大O符号相关的，所以它只是为O（n ² ）。 如Wikipedia解释：

  

[...]的系数，如果我们比较表达的任何其他顺序变得无关紧要，例如含有一个项n的表达式 ³ 或正 ²

Answer 3

每个阅读或撰写有关算法复杂性的人都应该确切地知道算法的复杂性是什么 兰道符号 和 渐近符号 是，否则他们并不能真正理解正在发生的事情，或者只是有一个近似的（并且常常是误导性的）想法。

为了简化（很多），让 f 和 g 是两个函数 f : N -> N 和 g : N -> N. 。我们这么说 f is O(g) 当且仅当有一个常数 M > 0 这样 |f(n)| < M|g(n)|, ， 对全部 n > M. 。也就是说，更非正式地，从一个大值开始 n, ，所有值 f(n) 小于的倍数 g(n) （IE， g 长得更快 比 f).

该定义相当于

f is O(g) <==> There is K >= 0 such that lim{n -> +oo} |f(n)|/|g(n)| = K

那么，让我们采取 f(n) = 4n^2 + 7n 和 g(n) = n^2, ，并尝试证明 f is O(g) （我将省略 {n -> +oo}):

lim |f(n)|/|g(n)| = lim f(n)/g(n) = lim (4n^2 + 7n) / n^2 = 4 + lim 7n/n^2 =
                  = 4 + lim 7/n = 4 + 0 = 4

这意味着有一个 M 这样 n > M ==> |f(n)| < M|g(n)|, ， 因此 f is O(g).

所以从技术上讲，这是正确的 4n^2 + 7n is O(4n^2), ，因为这是正确的说法 4n^2 + 7n is O(n^3), 4n^2 + 7n is O(e^n), ， 等等。但为了有意义，我们对下界感兴趣。因此，如果 f is O(e^n) 和 f is O(n^2), ，我们更感兴趣的是知道 f is O(n^2), ，因为这更具限制性。

非常重要的注意事项

选择算法时极其重要的是要了解 大 O 符号 指的是 渐近病例, ，也就是说，当你考虑 极其难以想象的巨大投入, ，这可以远远超出已知宇宙中可用的计算能力（即无限输入集，数学上表示为 {n -> +oo}).

对于实际用途（即，不 所以 巨大的输入），当选择算法时，当然，你会观察候选算法 大 O 符号, ，但您必须确保所选算法能够很好地适应您的（预期）输入（并且性能更好）。

最后，通常性能更好的算法更难以理解和正确实施。在选择算法时，您也必须考虑这一事实（即， 是我要花的时间 调试和修复我的实现 这个算法的时间比我必须等待另一个算法（使用更糟糕的大 O 表示法）的时间要长得多？. 。如果是这样，您应该考虑更简单、效率较低的算法，因为整体解决方案会更有效）。

Answer 4

这是为O（n ^ 2）。常数因子“移入0”。你只保留最大的指数，因为这是一个占主导地位。并且可以由于比较不同的算法即使是非常大的系数产生较小总数比具有较大的指数（其中n足够大）时离开了系数。

Answer 5

像

一个语句

4n² + 7n = O(n²)

意味着对于某些常数乘法器c，表达cn²最终将超过4n² + 7n。这在技术上不是不正确离开系数在那里 - O(n²)和O(4n²)意味着同样的事情，因为前者的任何常量c可以通过c/4后者所取代。然而，这样的事情是不太清楚，可能是误导性的，绝对非标准的。

Answer 6

从数学上讲，你会写O（4n²）。这意味着你的算法的复杂性函数为n->4n²行为朝正无穷大。

但在计算机科学/算法，你会只写O（N²），这足以归类你的算法。