Big-O 符号建议

Question

以下哪个函数不是 O(n²)?

一个。 O(n²log₂n)

乙。 O(log₂(log₂n)

C。 O(nlog₂n)

D. (log₂ⁿ)²

我相信，它不是 A，因为 n² 在那个中占据主导地位，这将使它成为 O(n²) 还有。

我的问题变成了你如何找出哪个不是 O(n²)?我用对数的工作不多，我仍然不清楚如何使用它们。

谢谢。

Answer 1

答案是 A

Big-O 是上限，在编程中代表 worst-case 运行时。例如 f(n) = n^2 意味着 f(n) 是 O(n^2) 和 O(n^3) 和 O(n^100*logn)。所以 O(n^2) 也是 O(n^3) 但 O(n^3) 不是 O(n^2)

对于您的问题，唯一大于 n^2 的答案是 A。绘制函数图形可以帮助您将其可视化。如您所见，A（红色）是唯一比 n^2（黑色）增长更快的

这篇文章或许对您也有帮助 https://en.wikipedia.org/wiki/Big_O_notation 并转到常用函数的顺序