big-o - 证明 n^2 不是 O(n*log(n))？

Question

仅使用 O() 的定义？

Answer 1

你想计算的极限

  (n * log(n)) / (n ^ 2) =
= log(n) / n =
= 0 if n approaches infinity.

因为log(n)比 增长慢n。

Answer 2

你需要用反证法来证明。假设n^2 是 O(n*log(n))。这意味着根据定义，存在一个有限且非可变的实数c ，使得

n^2 <= c * n * log(n) 

对于每一个大于某个有限数的 n n0。

然后你到达了 时的点c >= n /log(n)，你推导出为n -> INF，c >= INF这显然是不可能的。

你得出n^2 的结论不是 O(n*log(n))