大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有什么区别？

回答

相关问题