big-theta - 大 Theta 问题

Question

我有两个功能：

• f(n) = 2;
• g(n) = 10 ^ 100;

我必须证明 f(n) = BigTheta(g(n)) 是否合理。

我的猜测是 f(n) 是 BigTheta(g(n))，因为这两个函数都是常数（这意味着函数是成比例的），但是我的老师坚持认为我错了。

我对吗？有什么办法可以让我的案子休息吗？对不起，如果这听起来像一个菜鸟问题！谢谢。

Answer 1

你是对的。假设您引用了正确的问题并且没有误解，那么如果您的老师说他们不是彼此的θ，那么您的老师就错了。

这是定义：

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 x_cutoff）

但是，如果不知道考试问题的实际文本以及您写（或圈出）的确切文本，我们在互联网上就无法知道没有对问题的某种误读。您还应该注意，即使您的答案是正确的，您的理由仍然可能是错误的。

为了记录，不仅f(x)在 setBigTheta(g(x))中，而且g(x)在 set 中BigTheta(f(x))。我认为一个等效的定义是这两个函数的比率是有界的x -> infinity（接下来将维基百科的定义除以某个截止点），这可能是一个更容易思考的定义（并且更容易证明）|g(x)|。|f(x)|/|g(x)| < constant这也意味着 BigTheta 是一个对称关系。

你现在有合适的工具来问“你为什么认为我错了？” 然后用数学来确定你们两个中哪一个是对的；任何误解都应该出现在数学中，否则你就证明了你的观点。

Answer 2

f(n) <= g(n) * 1
2    <= 10^100     for all n >= 0

因此f(n) = O(g(n))。

f(n) >= g(n) * 2/(10^100)
2    >= 10^100 * 2/(10^100) = 2      for all n >= 0

等等f(n) = Ω(g(n))。

两者f(n)=O(g(n))和f(n)=Ω(g(n))暗示f(n) = Θ(g(n))。是的你是对的。