大西塔問題

Question

我有兩個功能：

• F（N）= 2;
• g（n）= 10^100;

我必須證明如果f（n）= BigTheta（g（n））或不。我的猜測是f（n）是BigTheta（g（n）），因爲這兩個函數都是常量（這意味着函數是成比例的），但是我的老師堅持認爲我錯了。

我對不對？有什麼方法可以讓我的病情得到休息嗎？ 對不起，如果這聽起來像一個noob問題！謝謝。

Answer 1

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))。你是對的。

Answer 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比任何合適的臨界值x_cutoff大）

不知道考試問題的實際文本雖然，以及你寫的（或圈出的）確切的文字，我們不可能在互聯網上知道這個問題沒有任何誤解。你也應該注意到，即使你的回答是正確的，你仍然可能在錯誤的理由。

備案時，不僅是f(x)在集BigTheta(g(x))，但g(x)是在集BigTheta(f(x))。我認爲一個等價的定義是，這兩個函數的比率是有界的x -> infinity（通過將維基百科的定義除以|g(x)|得到|f(x)|/|g(x)| < constant經過某個分界點），這可能是一個更容易的定義要考慮（並且更明顯證明）。這也意味着BigTheta是一個對稱關係。

你現在有合適的工具來問「爲什麼你認爲我錯了？」然後用數學來確定你們哪一個是對的;任何誤解都應該出現在數學中，如果不是的話，你會證明你的觀點。