log(n)=Ω(n)？

Question

我相信不是.定义是:

log(n) >= c*n for some n = x, and all n > x

我认为不是因为c*n = c的增长率.log(n)的增长率= 1/n.因此,当n->无穷大时,n的增长率接近0,而c,c*n的增长率是恒定的.鉴于最终log(n)最终将比任何n*c增长得慢,其中c> 0,n*c将超过log(n).

那么,几个问题.

1. 我可以假设大欧米茄的定义中c> 0吗？
2. 我的直觉是否正确？
3. 我对上面的证据感到矛盾.因为对于非常小的c,log(n)= cn很早,我的上述假设意味着它们会再次交叉,这意味着log(n)= cn有多个解决方案,这似乎是错误的.

我很困惑,很感激帮助!

Answer 1

1- c不能为0或负数,所以你可以假设.

2-的生长log(n)比的生长下n,对于每一个n > 1,例如.由于Ω(n)是比函数"增长更多"的函数集f(n) = n,因此log(n)不是Ω(n).但你可以说n =Ω(log(n)),虽然那不是渐近的紧束缚.

3-定义指出不等式可能从一个值开始有效n0.如果n0存在某些,你可以这么说.但在这种情况下(log(n)=Ω(n)),它没有,因为它必须对每一个都有效n >= n0.而对于任何大的价值,log(n)的增长都低于n的增长.