big-o - 为什么 n^2 + 2n + 2 等于 O(n^2)？

Question

我正在学习 Big-O 表示法，我发现了一个我无法简化的例子。

为什么 n^2 + 2n + 2 = O(n^2)？

标签： big-o

Answer 1

在谈论渐近符号时，您通常使用非常大的值，n并且您尝试找出程序有界的数学函数。

在这种情况下，您有 2 个函数n^2和2n（让我们暂时忽略常量）。

如果您绘制这些图表，您可以看到以下内容：

虽然比一开始2n略高，但一旦走向无穷，永远低于n^2n2nn^2

因此，如果您的方法具有 的复杂性，那么当的值趋于无穷大O(n^2 + 2n)时，这并不重要（或者可以忽略不计），因为您的程序将始终受. 你可以用同样的推理来解释为什么一个常数没有那么重要，即使它是一个很大的常数。n2nn^2

此外，在渐近符号中，当你有总和时，你经常会做这种“简化”，就是这样。但是，如果复杂性是 ，这将是不同的O(n^2 * 2n)，如果我没记错的话，最终会是O(n^3)- 常量无关紧要，所以我们可以摆脱2然后你有n^2 * n。