大O和大Omega有什麼區別？

大歐米茄應該是大O的對立面，但他們總是能夠具有相同的值，因爲按照定義，大O是指：大O和大Omega有什麼區別？

g(x) so that cg(x) is bigger or equal to f(x)

和大歐米茄意味着

g(x) so that cg(x) is smaller or equal to f(x)

唯一改變的是c的值，如果c的值是一個任意值（我們選擇滿足不等式的值），那麼Big Omega和Big O將是相同的。那兩個有什麼關係？他們的服務目的是什麼？

來源

2013-05-13 Martin Renee

不是。就是不行！互聯網斷了嗎？ – 2013-05-13 07:42:56

可能重複http://stackoverflow.com/questions/471199/what-is-the-difference-between-n-and-on – BenC 2013-05-13 07:50:42

'c'不允許隨'x'變化。給定'f'和'g'，必須有一個特殊的'c'使所有足夠大的'x'的不等式成立。 – user57368 2013-05-13 08:21:16

-1

漸近地，大O的上界受到（達到常數因子），而大歐米伽在漸近下受限於（達到常數因子）。在數學上，f（x）= O（g（x））（big-oh）表示f（x）的增長率漸近地小於或等於g（x）的增長率，。

F（X）=Ω（G（X））（大-ω）表示F（X）的生長速率是漸近大於或等於G的增長速度（X）

請參見下面的參考維基：

Big O notation

enter image description here

來源

2013-05-13 07:45:22 David

-1

有時候你想證明一個上限（大哦），你想證明一個下界（大歐米茄）另外一些時候。

http://en.wikipedia.org/wiki/Big_O_notation：

Family of Bachmann–Landau notations

來源

2013-05-13 07:47:47

-1

當你斷言，這樣A G存在，但並不意味着它認識你是正確的。

除了談論算法的複雜性，你還可以談論問題的複雜性。已知multiplication例如在位數中是Ω（n）和O（n log（n）log（log（n））），但是精確的表徵（由Θ表示）是未知的。一般而言，這與integer factorization和NP problems是同樣的故事，這是整個P對NP的事情。

此外，顯然有algorithms和證明是最優的，其複雜性是未知的。見http://en.wikipedia.org/wiki/User:Erel_Segal/Optimal_algorithms_with_unknown_runtime_complexity

來源

2015-05-15 04:48:10

大O和大Omega有什麼區別？

回答

相關問題