ビッグOとビッグオメガは同じですが逆ですか？

Question

これは本当ですか？

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

これは基本的に互換性がありますか？

もしFがGのBig Oにあれば、GはFのBig Omegaですか？

それは定義を見てするのに役立ちます

Answer 1

私はビッグ・オ（Big-O）表記が「最悪の場合」であり、ビッグ・オメガが「ベスト・ケース」であるということが最も簡単な考え方です。

もちろん、たとえば、の場合、は次の（むしろダム）線形検索アルゴリズムが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）という表記を導入します。

平均ケースのように他のケースもあります。平均的なケースは、しばしば最良の場合と最悪の場合のいずれかと同じである。たとえば、よく実装された線形検索の最良のケースはO（1）です（探しているアイテムがリストの最初のアイテムである場合）が最悪の場合はO（n）ですリスト全体を検索してアイテムがそこにないことを発見する）。リストにアイテムが含まれている場合、平均でそれを見つけるのにn/2ステップかかるでしょう（私たちは平均してアイテムを見つけるためにリストの半分を見なければならないので）。従来は、「/ 2」部分を削除して、平均の場合がO（n）であると言うだけです。

これらは厳密にはではありませんが、と同じです。バイナリ検索ツリー検索の「最良の」ケースがO（1）とみなされるべきか（探しているアイテムがツリー上の最初のアイテムである可能性があるため）、またはそれを考慮する必要があるかどうかについて、 O（log n）（バイナリ検索の「最適な」ケースは、ツリーが完全に平衡している場合です）。 （BST挿入については、hereを参照してください）。平均的な場合はO（log n）です。最悪の場合はO（n）である（二分探索木が完全にである場合、が平衡している）。 O（1）、最良の場合をO（log n）、最悪の場合をO（n）とすると、平均、最悪、および最良の場合はすべて明らかに異なる。

Answer 2

：あなたはO（N G（））で、F（n）を行い、C、Kの値を見つけることができる場合は、同じ値も表示されます

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. 

g（n）をオメガ（f（n））とする（不等式の両辺を単にcで割る）。そういうわけで、彼らは交換可能です。

F（n）のシータ（G（N））ではありません、それはO（G（n）とオメガ（G（N））の両方である場合を除きます。

希望に役立ちます！