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. 我可以从big omega的定义中假设c>0吗？ 2. 我上面的直觉正确吗？ 3. 我对我的证明感到困惑。因为对于非常小的c，log(n)=cn很早就成立，我的假设意味着它们会再次相交，这意味着log(n)=cn有多个解，这似乎是错误的。

我很困惑，感谢您的帮助！

- kodai

---

这个问题对我来说有点困惑，因为omega符号通常用于表征算法，而不是抽象函数。例如，有些算法可以在Ω(1)的时间内计算log(n)（对于有限的输入值n），你的FPU可能包含一个以查找表的形式实现的算法。 - Daniel Pryden

Omega符号用于表征函数的渐进增长，因此该问题是绝对正确的。它不是用来描述算法的，但可以描述算法的资源消耗（时间、空间等）。 - shuhalo

Answer 1

1- c 不能为0或负数，因此您可以假设。

2- 对于每个 n > 1，例如，log(n) 的增长速度低于 n 的增长速度。由于 Ω(n) 是指“增长速度比函数 f(n) = n 更快的函数集合”，所以 log(n) 不是 Ω(n)。但是你可以说 n = Ω(log(n))，虽然这不是渐近紧密界限。

3- 定义说明不等式可能从一个值 n0 开始有效。如果存在某个 n0，则可以这样说。但在这种情况下（log(n) = Ω(n)），它不存在，因为它必须对每个 n >= n0 都有效。对于任何大的值，log(n) 的增长速度都低于 n 的增长速度。

- Gabriel

Answer 2

不，实际上恰恰相反。

• log(n)函数的运行时间是O(n)

[读作：上界为某个最高项系数为n的多项式函数]

• 而一个运行时间为n的fn 是Ω(log(n))

  [读作：下界为某个最高项系数为log(n)的多项式函数]

关于你的直觉，它是完全正确的。log(n)=cn只在一个点相交。

- jemmanuel