1

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

4

1 回答 1

3

对于任何常数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 )。

于 2013-05-18T20:37:40.633 回答