我花了一个多小时的时间来寻找以下内容的引用:
f = Ω(g)
但我一点运气都没有。我需要回答作业问题,但找不到引用资料。
作业基本上是要求我在以下选择的背景下指出它 (f = Ω(g)
) 的含义:
- f = Ω(g(n))
- g = o(ln n)
- g = o(g(n))
- g = O(f)
- f = O(g)
一开始我以为问题可能有误。
我知道选项 1 是错误的,并且假设选项 5 也是错误的,但在线一小时后我无法弄清楚哪一个是答案。
有人可以向我解释一下如何解决这个问题吗?我意识到这可能意味着给我答案,以便可以对其进行解释,但我更感兴趣的是为什么这些答案之一是正确的。
最佳答案
“f = Ω(g)
表示“f 渐近地由 g 下界”。f = O(g)
表示“f 渐近地由 g 上界” “根据评论。
如果河流的上界是一座桥,那么桥的下界是多少?河流。
我建议d
(为了完整起见,这些的“小”版本意味着增长方面的巨大差异。)
关于complexity-theory - 大欧米茄表示法 - 什么是 f = Ω(g)?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/16716291/