algorithm - 为什么 n log(n) 比 n 具有更高的优势？

Question

考虑一个例子，如果 n=4

n log(n)=4 * log(4) =2.408

n=4

那怎么办n log(n)> n ???

Answer 1

大 O 表示法假定 n 很大。 n=4与复杂度分析无关。

在一般情况下，如果您查看两者之间的比率:n.log(n)/n = log(n) 前提是 n>0。

当 n 变大时，这个比率趋于无穷大，这意味着 n.log(n) 比 n 花费“无限”多的时间，因此 n.log(n) 支配 n。