大欧米茄符号-f =Ω(g)是什么? [英] Big Omega notation - what is f = Ω(g)?
问题描述
一个小时的时间里,我一直在努力寻找以下内容的参考:
I've been trying for the better part of an hour to find reference to the following:
f =Ω(g)
f = Ω(g)
但是我根本没有运气.我需要为作业回答一个问题,但找不到参考资料.
But I have had no luck at all. I need to answer a question for an assignment and I can't find references.
该作业基本上是在以下选择的背景下要求我指出它(f = Ω(g)
)的含义:
The assignment is basically asking me to indicate what it (f = Ω(g)
) means, in the context of the following choices:
- f =Ω(g(n))
- g = o(ln n)
- g = o(g(n))
- g = O(f)
- f = O(g)
最初,我认为问题可能有误.
Initially, I thought that perhaps there is an error in the question.
我知道选项1错误,并且假设选项5也错误,但是在线一个小时后,我不知道哪个是答案.
I know option 1 is wrong and assume option 5 is also wrong, but after an hour online I couldn't figure out which one is the answer.
有人可以向我解释如何解决吗?我意识到这可能意味着给我答案,以便可以解释它,但是我对为什么其中一个答案是正确的更感兴趣.
Can someone please explain to me how to figure this out? I realize that might mean giving me the answer so it can be explained, but I'm more interested in why one of these answers are correct.
推荐答案
"f = Ω(g)
表示"f被g渐近地包围在下面".f = O(g)
意味着"f被g渐近地被包围在上面".
"f = Ω(g)
means "f is bounded below by g asymptotically". f = O(g)
means "f is bounded above by g asymptotically" as per the comments.
如果河流的上限是一座桥梁,那么桥梁的下限是多少?这条河.
If a river's upper bound is a bridge, what's a bridge's lower bound? The river.
我建议d
(为完整性起见,这些小"版本表示增长差异非常大.)
(For completeness, the "little" versions of these imply a very strong difference in growth.)
这篇关于大欧米茄符号-f =Ω(g)是什么?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!