大0和大是一样的，但方向相反

Question

这是真的吗?

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

基本上它们是可以互换的，因为它们是对立的吗?

如果F在大O (G)中，那么G是大(F) ?

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.  

如果你能找到c和k的值使f(n)在O(g(n))中，那么相同的值也会表明g(n)等于(f(n))(只要不等式两边除以c)，这就是为什么它们是可互换的。

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

希望有帮助!

Answer 2

我自己从来没有特别关心过符号。考虑这个问题的最简单方法是，大o符号是"最坏情况"，而大Omega是"最好情况"。

当然，还有其他你可能感兴趣的东西。例如，您可以声明以下(相当愚蠢的)线性搜索算法是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)和(n)对于这种情况，我们引入Theta(n)的符号。

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

它们并没有严格意义上的要求相同。我看到过一些关于二叉搜索树搜索的"最佳"情况应该被认为是O(1)(因为你正在寻找的项目可能是树上的第一个项目)还是应该被认为是O(log n)(因为二叉搜索的"最佳"情况是树是完全平衡的)的争论。(关于BST插入的讨论见这里)。平均情况肯定是O(log n)最坏的情况是O(n)(如果二叉搜索树完全un平衡)。如果我们取最佳情况为O(1)，平均情况为O(log n)，最差情况为O(n)，那么平均值，最差情况和最佳情况显然都是不同的