對於這個問題，我想是因爲我認爲這個問題基本上是問f(n)大於或等於g(n)則比2^(f(n))大於或等於2^(g(n))如果f（n）是歐米茄（g（n）），那麼2 ^（f（n））是歐米茄（2^g（n））。這是真的還是假的
因此，如果我們拿一個實例是真的f(n) = 2n和g(n) = n,f(n)是> g(n)。然後2^2n大於2^n。
但我的朋友說這不正確，有人能給我一些見解嗎？我想我可能會對這個問題有所誤解。
對於這個問題，我想是因爲我認爲這個問題基本上是問
f(n)大於或等於g(n)這是真的，那麼是大於或等於2^(g(n))
都能跟得上2^(f(n))。這不是什麼大歐米茄符號的意思。 f(n) = Ω(g(n))意味着對於足夠大的n，比率f(n)/g(n)的範圍低於正常數。
要看到f(n) = Ω(g(n))並不意味着2^f(n) = Ω(2^g(n))，請考慮f(n) = n - log(n)和g(n) = n。然後2^f(n) = (2^n)/n和2^g(n) = 2^n和2^f(n) != Ω(2^g(n))。
您想證明或反證此要求：
如果F（N）= Ω（G（N）），然後2 F（N）= Ω（2克（ n））。
當您看到類似的聲明時，澄清f和g在這裏通常很有幫助。具體而言，上述真的語句意味着：
對於任意函數f和g，如果f（N）= Ω（G（N）），然後2 F（N） = Ω（ 2克（N））
所以在這個意義上說，如果你想證明這種說法是真實的，你需要通過表示，這種說法是真實的對任何可能的選擇辦法吧f和g，不僅僅是通過選擇單個f和單個函數並確認這種關係適用於這些特定職能。從這個意義上說，你的朋友是對的。
（在另一方面，如果要反駁這個要求，則只需要給的函數f和g其中f（N）= Ω（G（N）），但2 ˚F例子（正） ≠ Ω（2 g（n））。）
作爲這個問題的提示：像O，Ω和Θ這樣的漸近符號都完全忽略了常數因子。如果f（n）= Ω（g（n）），那麼您可以通過任何您想要的常數因子來縮放f或g，並且該關係仍將保持不變。另一方面，指數中的常數因素從根本上改變了指數的性質。例如，該函數e Ñ呈指數增長比函數e 2n個比較慢，因爲È2N =（E 2 ）Ñ，這是具有較高底的指數函數。換句話說，你不能以一個恆定的因子來衡量指數，而不能完全改變它們的增長率。
基於此斷開連接 - Ω表示法不能區分常數因子不同的函數，但該指數函數對常數因子非常敏感 - 您認爲該聲明是真的還是錯誤的？根據以上建議，你如何證明這樣的陳述？
是的。你還可以回答標題問題嗎？ – Bergi
@Bergi：我認爲答案沒問題，只是指出了提問者的誤解，但肯定還是反例。 – user2357112
哦，好的，我天真地認爲暗示仍然是正確的。 – Bergi