1

Big Omega 应该是 Big O 的对立面,但它们总是可以具有相同的值,因为根据定义 Big O 意味着:

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 将是相同的。那么这两个有什么意义呢?他们的目的是什么?

4

3 回答 3

0

Big O 以(直到常数因子)渐近为界,而 Big Omega 以(直到常数因子)渐近为界。

从数学上讲,f(x) = O(g(x)) (big-oh) 意味着 f(x) 的增长率渐近小于或等于 g(x) 的增长率。

f(x) = Ω(g(x)) (big-omega) 表示 f(x) 的增长率渐近大于或等于 g(x) 的增长率

请参阅下面的 Wiki 参考:

大 O 符号

在此处输入图像描述

于 2013-05-13T07:45:22.947 回答
-1

有时您想证明一个上限(Big Oh),有时您想证明一个下限(Big Omega)。

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

Bachmann-Landau 符号家族

于 2013-05-13T07:47:47.340 回答
-1

当你断言这样的 ag 存在时你是正确的,但这并不意味着它是已知的。

除了谈论算法的复杂性,您还可以谈论问题的复杂性。

众所周知,例如乘法的位数是 Ω(n) 和 O(n log(n) log(log(n))),但精确的表征(用 Θ 表示)是未知的。整数分解和一般的NP 问题也是如此,这就是整个 P 与 NP 的关系。

此外,显然还有一些算法被证明是最优的,但其复杂性是未知的。请参阅http://en.wikipedia.org/wiki/User:Erel_Segal/Optimal_algorithms_with_unknown_runtime_complexity

于 2015-05-15T04:48:10.187 回答