在渐近表示法中，为什么我们不使用所有可能的函数来描述函数的增长率？

Question

如果f(n) = 3n + 8，

为此，我们说或证明了f(n) =Ω(n)

为什么我们不使用Ω(1)或Ω(logn)或.描述我们函数的增长率？

Answer 1

在研究算法复杂性的背景下，Ω渐近界至少可以达到两个目的：

• 检查是否有机会找到一个具有可接受复杂度的算法；
• 检查是否找到了最优算法，即它的O界与已知的Ω界匹配。

为了这些目的，最好是严格限制(强制性的)。

还请注意，f(n)=Ω(n)意味着f(n)=Ω(log(n))，f(n)=Ω(1)，并且所有的增长率都较低，我们不需要重复。

Answer 2

你真的可以这么做。检查Big表示法这里，让我们以Ω(log n)为例。我们有：

f(n) = 3n + 8 = Ω(log n)

因为：

​

​

(根据1914年Hardy-Littlewood的定义)

或者：

​

​

(根据Knuth的定义)。

关于liminf和limsup符号的定义(附图)，请查看这里。

也许真正意义上的是Θ (大Theta)，也就是说，O()和Ω()同时存在。