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

对于任何常数k，而不仅仅是 1 ，lg n = O( n ^k ) （实际上是 o( n ^k )；提示是否真的这么说？）也是正确的。现在考虑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 n是 O( n lg n )。