不太瞭解記號

Question

我真的不明白我應該如何或者我應該證明什麼。我已經研究過每個問題，但我仍然不清楚預期結果。

以下哪項是正確的？證明你的答案。

1. N²∈O（N 3）
2. N²∈Ω（N 3）
3. 2ⁿ∈Θ（2 ^{N + 1}）
4. N！ ∈Θ（（n + 1）！）

任何幫助將不勝感激！

Answer 1

由於這（可能是家庭作業）的問題已經過時了幾天，我想我可以簡單回答這個問題。

維基百科頁面（希望你的課本和/或註釋過）說

f(n) ∈ O(g(n))  ⇔  lim sup |f(n)/g(n)| < ∞ 
f(n) ∈ Ω(g(n))  ⇔  lim sup |f(n)/g(n)| > 0 
f(n) ∈ Θ(g(n))  ⇔  f(n) ∈ O(g(n)) and f(n) ∈ Ω(g(n)) 

爲了證明左側可以證明右側。

1. n² ∈ O(n³)是真實的，因爲

   lim sup |n²/n³| = lim (n²/n³) = lim (1/n) = 0 < ∞ 
   

2. n² ∈ Ω(n³)是假的，由於

   lim sup |n²/n³| = lim (n²/n³) = lim (1/n) = 0 
   

3. 2ⁿ ∈ Θ(2n+1)是真實的，因爲

   0 < lim sup |2ⁿ/2<sup>n+1</sup>| = lim (2ⁿ/(2⋅2ⁿ) = lim (1/2) = 1/2 < ∞ 
   

4. n! ∈ Θ((n+1)!)是假的，由於

   lim sup |n!/(n+1)!| = lim (n!/((n+1)⋅n!) = lim (1/(n+1)) = 0 
   

注意：所有限制適用於n → ∞。