algorithm - 大O和大Omega有什么区别？

Question

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

score 0 · Accepted Answer

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 参考：

在此处输入图像描述

score -1 · Accepted Answer

有时您想证明一个上限（Big Oh），有时您想证明一个下限（Big Omega）。

Bachmann-Landau 符号家族

score -1 · Accepted Answer

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

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

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

3 回答 3