time-complexity - 表达式的大 O 表示法

Question

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

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

谢谢

Answer 1

您应该删除任何系数，因为问题实际上是在“按顺序”询问，它试图将其表征为线性、指数、对数等......也就是说，当 n 非常大时，系数并不重要。

这也解释了为什么要放弃 +7n，因为当 n 非常大时，该术语对最终答案的意义相对较小。如果你熟悉微积分，你可能会说 lim 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 ² )。 正如维基百科解释的那样：

[...] 如果我们与任何其他表达顺序（例如包含项 n ³或 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)（即，g 增长速度快于f）。

该定义等价于

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

所以，让我们取f(n) = 4n^2 + 7nand 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}) 表示。

对于实际用途（即，输入不是那么大），在选择算法时，当然，您会观察候选算法big-O notations，但您必须确保所选算法非常适合您（预期的） ） 输入。

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

Answer 4

它是 O(n^2)。常数因素“进入O”。您只保留最大的指数，因为这是占主导地位的指数。并且您可以省略系数，因为在比较不同的算法时，即使是非常大的系数也会导致比具有更大的指数（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²)，这足以对你的算法进行分类。