algorithm - 当 c > 0 Log(n) = O(n) 时？不确定为什么不是 O(log n)

Question

在我的作业中，问题要求确定 n^.99999*log(n) 的渐近复杂度。我认为它会更接近 O( n log n) 但答案表明当 c > 0 时，log n = O(n)。我不太清楚这是为什么，有人可以提供解释吗？

Answer 1

lg n = O( n^k ) 也是真的(事实上，它是 o(n^k); 提示实际上是这么说的，也许？)对于 任何 常量 k，而不仅仅是 1。现在考虑 k=0.00001。那么n^0.99999 lg n = O(n^0.99999 n^0.00001 ) = O(n)。请注意，这个界限并不严格，因为我可以选择更小的 k，所以可以说 n^0.99999 lg n 是 O(n^0.99999 lg n)，正如我们所说的 n lg < em>n 是 O(n lg n).