O(sqrt(n)) + O(n^2) 的大 O 时间复杂度是 O(n)？ [重复]

Question

我正在研究 Big O 表示法，我试图了解具有 O(sqrt(n)) 部分和 O(n^2) 部分的函数是否近似为 O(n) 或 O(n^2) .

Answer 1

O(n²).

对于足够大的 n，在表达式 n² + sqrt(n) 中，n² 将远大于 sqrt(n)。

数学上更精确的表达方式是，存在两个常数，您可以将 n² 相乘，以从上方和下方限制函数 n² + sqrt(n)。

您可以使用 WolframAlpha 来显示这一点。这里，当 n > 1 时，常数 1 和 2 限制了函数。