Big O 和 Big Omega 相同但相反？

Question

这是真的吗？

f(n) = O(g(n))  === g(n) = Omega(f(n))

基本上它们是可以互换的，因为它们是相反的吗？

那么如果F在G的Big O中，那么G就是F的Big Omega？

Answer 1

查看定义有帮助：

f(n) is in O(g(n)) if and only if:
There are positive constants c and k, such that 0 ≤ f(n) ≤ cg(n) for all n ≥ k.


g(n) is in Omega(f(n)) if and only if: 
There are positive constants c and k, such that g(n)  ≥ cf(n)  ≥ 0 for all n ≥ k.

如果你能找到使 f(n) 变为 O(g(n)) 的 c 和 k 的值，那么相同的值也将显示 g(n) 为 Omega(f(n)) (只需将不等式两边除以 c)。这就是它们可以互换的原因。

F(n) 不是 Theta(g(n))，除非它同时存在于 O(g(n) 和 Omega(g(n)) 中。

希望对您有所帮助！

Answer 2

我自己从来没有特别关心过符号。想到这一点的最简单方法是 Big-O 表示法是 "worst case" 而 Big Omega 是 "best case."

当然，还有其他您可能感兴趣的东西。例如，您可以声明以下（相当愚蠢的）线性搜索算法是 O(n) , 但更准确地说它总是与 n:

成正比

public bool Contains(List<int> list, int number)
{
    bool contains = false;
    foreach (int num in list)
    {
      // Note that we always loop through the entire list, even if we find it
      if (num == number)
         contains = true;
    }

    return contains;
}

或者，我们可以声明这既是 O(n) 又是 Omega(n)。对于这种情况，我们引入 Theta(n).

的符号

还有其他情况，例如平均情况。平均情况通常与最好或最坏情况相同。例如，良好实施的线性搜索的最佳情况是 O(1)（如果您要查找的项目是列表中的第一项），但最坏的情况是 O(n)（因为您可能有搜索整个列表以发现该项目不存在）。如果列表包含该项目，平均而言，需要 n/2 步才能找到它（因为平均而言，我们必须浏览一半的列表才能找到该项目）。按照惯例，我们去掉“/2”部分，只说平均情况是O(n)。

严格来说，它们并不相同。我已经看到一些关于二叉搜索树搜索的 "best" 情况是否应该被视为 O(1) 的争论（因为您正在寻找的项目可能是树上的第一项）或者它是否应该被认为是 O(log n)（因为二分搜索的 "optimal" 情况是树是否完全平衡）。（有关 BST 插入的讨论，请参阅 here）。不过，平均情况肯定是 O(log n)。最坏的情况是O(n)（如果二叉搜索树完全un平衡）。如果我们将最好的情况设为 O(1)，将平均情况设为 O(log n)，将最坏情况设为 O(n)，那么平均值、最坏情况和最佳情况显然都是不同的。

Big O 和 Big Omega 相同但相反？

Big O and Big Omega are the same but in reverse?

big-o

big-theta