大西塔问题
我有两个函数：
- f(n) = 2;
- g(n) = 10 ^ 100;
我必须证明 f(n) = BigTheta(g(n)) 是否合理。
我的猜测是 f(n) 是 BigTheta(g(n))，因为这两个函数都是常数（这意味着函数是成比例的），但我的老师坚持认为我错了。
我说得对吗？有什么办法可以让我休息一下吗？ 抱歉，如果这听起来像是一个菜鸟问题！谢谢。
I have two functions:
- f(n) = 2;
- g(n) = 10 ^ 100;
I have to justify if f(n) = BigTheta(g(n)) or not.
My guess is that f(n) is BigTheta(g(n)), since both functions are constants (wich means the functions are proportional), but a my teacher insists that I am wrong.
Am I right? Is there any way I could rest my case?
Sorry if this sounds like a noob question! Thanks.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
你是对的。假设你正确地引用了问题并且没有误解，如果你的老师说他们不是彼此的θ，那么他们就是错误的。
定义如下：
http://en.wikipedia.org/wiki/Big_O_notation# Family_of_Bachmann.E2.80.93Landau_notations
显然
|100^10|*k1 <= |2| <= |100^2|*k2对于常量k1=1/100^10和k2=1（对于所有大于任何合适截止值的 x valuex_cutoff）尽管不知道考试问题的实际文本以及您所写（或圈出）的确切文本，我们在互联网上无法知道是否存在某种误读的问题。您还应该注意，即使您的答案是正确的，您的理由仍然可能是错误的。
根据记录，不仅
f(x)在集合BigTheta(g(x))中，而且g(x)在集合BigTheta(f(x))。我认为一个等效的定义是两个函数的比率以 x -> 为界。无穷大（随后将维基百科定义除以|g(x)|得到|f(x)|/|g(x)||f(x)|/|g(x)||f(x)|/|g(x)|超过某个截止点），这可能是一个更容易思考的定义（并且更容易证明）。这也意味着 BigTheta 是一种对称关系。|g(x)|常数现在你有了合适的工具来问“你为什么认为我错了？”然后用数学来确定你们两个谁是对的；任何误解都应该出现在数学中，如果没有，你就证明了你的观点。
You are correct. Assuming you quoted the problem correct and there's no misunderstanding, your teacher is wrong if they said they are not theta-of-each-other.
Here's the definition:
http://en.wikipedia.org/wiki/Big_O_notation#Family_of_Bachmann.E2.80.93Landau_notations
Clearly
|100^10|*k1 <= |2| <= |100^2|*k2for constantsk1=1/100^10andk2=1(for all x larger than any suitable cutoff valuex_cutoff)Without knowing the actual text of the exam problem though, and the exact text you wrote (or circled), there is no way we on the internet can know there isn't some sort of misreading of the problem. You should also note that you could still be wrong in your justification even though your answer is right.
For the record, not only is
f(x)in the setBigTheta(g(x)), butg(x)is in the setBigTheta(f(x)). I think an equivalent definition is that the ratio of the two functions is bounded asx -> infinity(follows by dividing the Wikipedia definition by|g(x)|to get|f(x)|/|g(x)| < constantpast some cutoff point), which may be an easier definition to think about (and more obvious to prove). It would also imply that BigTheta is a symmetric relation.You now have the suitable tools to ask "why do you think I am wrong?" and then use math to determine which of you two are right; any misunderstanding should appear in the math, if not you'll have proved your point.
因此
f(n) = O(g(n))。所以
f(n) = Ω(g(n))。f(n)=O(g(n))和f(n)=Ω(g(n))都意味着f(n) = θ (g(n))。是的你是对的。Thus
f(n) = O(g(n)).And so
f(n) = Ω(g(n)).Both
f(n)=O(g(n))andf(n)=Ω(g(n))implyf(n) = Θ(g(n)). Yes, you are right.