algorithm - 你能说 (n lg n) 是 O(n^2) 吗？

Question

我知道给定 O(n lg n) 和 O(n^2)，当 (n lg n) 较小时n 足够高。

但是 O(n^2) 会是 (n lg n) 的正确评估吗？

O(n lg n) 和 O(n^2) 有很大的不同，所以我不确定 O(n^ 2) 将是 (n lg n) 的“最坏情况”

的最佳答案

Answer 1

回答标题问题(原来是:你能说 nlgn 等于 O(n^2) 吗？):

不，你不能作为nlgn是一个函数并且O(n^2)是一个集合。

从正文中回答您的问题:

嗯，是的，nlogn是O(n^2) ...但不要试图用 O(n^n) 回答考试中的每个问题.这不是他们要问的。大 O 符号不用于给出最佳答案。这只是提供一些信息的一种方式。

根据维基百科:

Big O notation is a mathematical notation that describes the limiting behavior of a function when the argument tends towards a particular value or infinity. It is a member of a family of notations invented by Paul Bachmann, Edmund Landau, and others, collectively called Bachmann-Landau notation or asymptotic notation.