2

我一直在尝试一个小时的大部分时间来找到对以下内容的参考:

f = Ω(g)

但我一点运气都没有。我需要回答一个作业问题,但我找不到参考资料。

该作业基本上是要求我f = Ω(g)在以下选择的上下文中指出它 ( ) 的含义:

  1. f = Ω(g(n))
  2. g = o(ln n)
  3. g = o(g(n))
  4. g = O(f)
  5. f = O(g)

最初,我认为问题中可能存在错误。

我知道选项 1 是错误的,并假设选项 5 也是错误的,但是在网上一个小时后,我无法弄清楚哪个是答案。

有人可以向我解释如何解决这个问题吗?我意识到这可能意味着给我答案以便可以解释,但我更感兴趣的是为什么这些答案之一是正确的。

4

1 回答 1

4

"f = Ω(g)表示“f 以 g 渐近地f = O(g)为界”。根据评论,表示“f 以 g 渐近地为界”。

如果一条河流的上界是一座桥,那么一座桥的下界是什么?河流。

我建议d

(为了完整起见,这些“小”版本意味着增长的非常大的差异。)

于 2013-05-23T14:27:27.073 回答