大O和大歐米茄是相同的，但相反？

Question

這是真的嗎？

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

基本上它們是可以互換的，因爲它們是相反的嗎？

所以如果F在G的大O中，那麼G就是F的大歐米茄？

Answer 1

我我從來沒有特別關心這個符號，最簡單的方法就是，Big-O符號是「最壞的情況」，Big Omega是「最好的情況」。

當然，還有其他的你可能會感興趣的東西。例如，你可以可能陳述下列（而非啞）線性搜索算法是O（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插入的討論，請參閱here）。但平均情況絕對是O（log n）。最壞的情況是O（n）（如果二叉查找樹完全是un平衡）。如果我們把最好的情況設爲O（1），平均情況是O（log n），最壞情況是O（n），那麼平均情況，最壞情況和最好情況都會明顯不同。

Answer 2

它有助於看看定義：

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. 

如果你能找到，這使得在O（G（N）），F（N）C和K的值，那麼相同的值也將顯示g（n）爲Ω（f（n））（只要將不等式的兩邊除以c）。這就是爲什麼它們可以互換。

F（n）不西塔（G（N）），除非它無論是在O（G（N）和歐米茄（G（N））。

希望幫助！