o(n) 和 o(n+n^1/2) 在算法上有什么区别？

Question

我看了一个在线课程，其中提到 O(n) 和 O(n + n^(1/2)) 在算法中是等价的。

我很好奇为什么n^(1/2)部分可以被忽略。这个遗漏的原因是什么？我还想知道在其他什么情况下多项式的一部分可以被忽略。非常感谢！

Answer 1

“在 Big-O 表示法中，我们主要关注增长最快的项。

让我们输入一些值 𝑛 号：

对于 𝑛

100 n=100，100的平方根是 100

10 100 =10。 为了 𝑛

1000 n=1000，平方根约为 1000 ≈ 30 1000 约30。 正如您所看到的，当比较 30 和 1000 时，对时间复杂度的影响非常可以忽略不计。