-4
A
回答
0
如果這些集合不相等，那麼至少有一個不在另一箇中的元素。我們會尋找一個。
Theta和o都是O的子集，所以必須是它們的聯合。這意味着LHS中的一切都必須在RHS中。所以，如果我們要找到使這些集合不同的東西，它將是O但是既不是Theta也不是o。
事情是O但不是Theta一定不是歐米茄。也就是說，他們不能從下面限制，因爲他們是從上面。這是一個簡單的贏在這裏是一個不連續的函數，（a）在一種情況下增長漸近較慢，（b）在另一箇中以相同的漸近速率增長。例如，Theta（n^2）在某些情況下，Theta（n lg n）在其他情況下。它將是O（n^2），但不是Theta（n^2）或o（n^2）。
我們可以通過隨機或根據輸入大小選擇氣泡排序和合並排序並將其稱爲反例排序來獲得具有此時間複雜度的算法。
+0
謝謝你的回答。英語不是我的母語，所以我必須慢慢閱讀，但我想我可以明白你的觀點。 – wangzhao765
相關問題
- 1. 證明最大（O（f（n）），O（g（n）））= O（max（f（n），g（n））
- 2. 數據結構。 f（x）和g（x）
- 3. Javascript：s/digit /「」x that digit/g
- 4. 證明O（max {f（n），g（n）} = O（f（n）+ g（n））
- 5. 如何在MacOS X上安裝g ++？
- 6. 瞭解一個SML類型fn（f，g，x）=> g（f（x））或類似
- 7. 在漸近分析中，證明：O表示大O. O（f（n）+ g（n））= O（max {f（n），g（n）}）
- 8. lm（y〜x * g）忽略g的一個值
- 9. 如何在Haskell中自由地實現f（g x）（h x）？
- 10. 當x趨於無窮大時，其中f（x）使g（f（x））的階數最小化
- 11. 宏在g ++中未能使用decltype（X）
- 12. 頂點着色由python-色數X（G）
- 13. 使用Ramda的形式f（x）（g（x））的函數組合
- 14. 如何更改gsp g：字段大小
- 15. 大O符號爲G（N）> H（N）
- 16. 爲什麼f <$> g <$> x等於（f。g）<$> x儘管<$>不是正確聯想？
- 17. 如何使boost和g ++使用insure ++ 3.4.x
- 18. 證明，僅使用O（）的定義，證明2^sqrt（x）不是O（x^10）
- 19. 邏輯程序設計：解決術語約束條件f（X; Y; g（a））= f（g（Y）; Z; X）
- 20. 如何獲取大小爲X的Java集並分解爲X/Y集？
- 21. g ++無法在Mac OS X上編譯小牛隊
- 22. 「__gfortran_pow_c8_i4」錯誤鏈接.o文件從g ++和gfortran使用g ++
- 23. g ++優化小寫字母大寫 - bug？
- 24. 如何繪製「無功能」圖：f（x）= g（y）
- 25. 如何使用ggplot2繪製（x，y，r，g，b）座標圖像？
- 26. 如何配置g ++使x ++爲原子（Ubuntu，openmp）？
- 27. f（g（x））一起或分裂的結果不一致
- 28. CUDA：使用-g -G
- 29. 在Matlab GPU計算中G2 = G * G和G2 = G * G之間的區別
- 30. 確定圖G中獨立邊的最大數v（G）
請不要發佈由單個鏈接組成的問題到外部網站。如果外部內容消失/更改，稍後您的問題就沒有意義了。 –
考慮如下函數：如果n是偶數，則f（n）= n，如果n是奇數，則爲1。 – fgb
@fgb這是個好主意。我不得不說，當我作爲一個本科生得到這個問題時，有人強調，隱含在算法增長階段的領域中，只考慮單調的非遞減函數（這個問題也可以解決這個問題）。 –