算法複雜度大O，小O，大歐米茄，小歐米茄，西塔

-2

For each pair of expressions, indicate whether A is O, o, Ω, ω, or Θ of B.

enter image description here

我明白工作的問題是相當多的上限和歐米茄是下限和θ是上下限。我很困惑什麼小o和小omega推測。（n^3）>（n^2）中的B的A O，但我不確定其他的一切。我想知道如果有人可以給我一些關於如何測試每一個的步驟。我檢查過維基百科和一些教育網站，但它不是很清楚，並且沒有太多的測試例子。

感謝

來源

2015-04-21 Jake Senior

Offtopic。不是一個真正的編程問題。嘗試http://cs.stackexchange.com/ –

請參閱[this]（http://stackoverflow.com/questions/471199/what-is-the-difference-between-%CE%98n-and-on/471206# 471206）解釋朗道（=「大哦」）符號。 –

如從Big O notation on Wikipedia

O形表示法和鄰符號的定義採取相似。主區別在於在於，在F（N）= O（G（N）），結合的0<=f(n)<=c*g(n) 保持用於"some constant c>0"，但是，在F（N）= O（G（N）） ，綁定 0<=f(n)<=o(g(n))持有"all constants c>0"。

在鄰表示法中，函數f（n）的相變微不足道的 G（N）爲n->∞： -

enter image description here //嚴格小O符號

lim n->∞ f(n)/g(n) = c,  `c closer to 0` // for strict Big-O notation

同樣，對於小歐米茄符號，

lim (x->infinity) f(x)/ g(x) = infinity

然而，嚴格的BIG-歐米茄符號

lim n->∞ f(n)/g(n) = c,  `c closer to ∞`

所以，現在要通過你的問題，

1. lim n-> ∞ A(n)/B(n) = lim n-> ∞ {(4*n^3 - 12*n^2 + 5*n)/36*n^2} 
         = lim n-> ∞ (n/9 - ...) 
         = ∞.

因此，A（n）是ω（B（N））。因此，A（n）是Ω（g（n））。因此，A（n）是Ω（g（n））。

其他兩個正在爲你留下作爲一個練習。如果您有任何問題，請留下更多評論。祝你好運，以解決您的問題。

來源

2015-04-21 20:01:59

哇。非常感謝。我很確定我現在明白了所有這一切。我想知道你是否可以詳細闡述'更接近無窮'和'更接近於0'。我還想知道如果你能解釋如何找到它是否是大的theta？非常感謝你的詳細解釋，它超出了我的期望 –

同樣對於數字2，wolfram alpha說n的限制爲A/B的無窮大是無窮大。所以不會是小歐米茄，不是大O？ –

@ JakeSenior-你最好讓c的那部分更接近0或者無窮大。此外，Big-theta與你所提到的一樣，我可以添加任何新東西。但是，對於第二個問題，是的，我錯誤地輸入了O代替Ω。謝謝，但是，它也取決於n的價值，因此，它將是資本Ω，而不是小歐米茄。因爲，如果你會按照你的邏輯進行操作，那麼所有的功能將會是「小」或「小」。只要你不確定n的價值，你就需要把它變成Big-O或Big-omega。因此，那更接近無窮大---我希望你安靜的理解。 –

算法複雜度大O，小O，大歐米茄，小歐米茄，西塔

回答

相關問題