Jaka jest różnica między Θ (n) i O (n)?

Czasami widzę Θ (n) z dziwnym symbolem with z czymś pośrodku, a czasem tylko O ​​(n). Czy to tylko lenistwo podczas pisania, ponieważ nikt nie wie, jak wpisać ten symbol, czy oznacza to coś innego?

Krótkie wyjaśnienie:

Jeśli algorytm ma wartość Θ (g (n)), oznacza to, że czas działania algorytmu, gdy n (rozmiar wejściowy) staje się większy, jest proporcjonalny do g (n).

Jeśli algorytm ma wartość O (g (n)), oznacza to, że czas działania algorytmu w miarę wzrostu n jest co najwyżej proporcjonalny do g (n).

Zwykle nawet jeśli ludzie mówią o O (g (n)), to tak naprawdę oznaczają Θ (g (n)), ale technicznie jest różnica.

Bardziej technicznie:

O (n) oznacza górną granicę. Θ (n) oznacza ścisłe powiązanie. Ω (n) oznacza dolną granicę.

f (x) = Θ (g (x)) iff f (x) = O (g (x)) if (x) = Ω (g (x))

Zasadniczo, gdy mówimy, że algorytm ma wartość O (n), jest to również O (n ² ), O (n ^1000000 ), O (2 ⁿ ), ... ale algorytm Θ (n) nie jest Θ (n ² ) .

W rzeczywistości, ponieważ f (n) = Θ (g (n)) oznacza, że ​​dla wystarczająco dużych wartości n, f (n) może być związane w zakresie c ₁ g (n) i c ₂ g (n) dla niektórych wartości c ₁ i c ₂ , tj. Szybkość wzrostu f jest asymptotycznie równa g: g może być dolną granicą i górną granicą f. To bezpośrednio implikuje, że f może być również dolną granicą i górną granicą g. W konsekwencji,

f (x) = Θ (g (x)) iff g (x) = Θ (f (x))

Podobnie, aby pokazać f (n) = Θ (g (n)), wystarczy pokazać, że g jest górną granicą f (tj. F (n) = O (g (n))), a f jest dolną granicą g (tj. f (n) = Ω (g (n)), co jest dokładnie tym samym co g (n) = O (f (n))). Treściwie,

f (x) = Θ (g (x)) iff f (x) = O (g (x)) ig (x) = O (f (x))

Istnieją również ωnotacje little-oh i little-omega ( ) reprezentujące luźne górne i luźne dolne granice funkcji.

Podsumowując:

f(x) = O(g(x))(big-oh) oznacza, że ​​tempo wzrostu f(x)jest asymptotycznie mniejsze lub równe tempu wzrostu wynoszącemu g(x).

f(x) = Ω(g(x))(duża-omega) oznacza, że ​​tempo wzrostu f(x)jest asymptotycznie większe lub równe tempu wzrostu wynoszącemug(x)

f(x) = o(g(x))(mało-o) oznacza, że ​​tempo wzrostu f(x)jest asymptotycznie niższe niż tempo wzrostu g(x).

f(x) = ω(g(x))(mała omega) oznacza, że ​​tempo wzrostu f(x)jest asymptotycznie większe niż tempo wzrostug(x)

f(x) = Θ(g(x))(theta) oznacza, że ​​szybkość wzrostu f(x)jest asymptotycznie równa szybkości wzrostu wynoszącejg(x)

Aby uzyskać bardziej szczegółową dyskusję, możesz przeczytać definicję na Wikipedii lub zajrzeć do klasycznego podręcznika, takiego jak Wprowadzenie do algorytmów autorstwa Cormena i in.

Jest prosty sposób (jak sądzę) podstęp, aby zapamiętać, który zapis oznacza co.

Wszystkie notacje Big-O można uznać za mające pasek.

Patrząc na Ω, pasek znajduje się na dole, więc jest dolną granicą (asymptotyczną).

Patrząc na Θ, pasek jest oczywiście pośrodku. Jest to więc (asymptotyczna) ciasna więź.

Pismo odręczne O zwykle kończy się u góry i rysuje zawijas. Dlatego O (n) jest górną granicą funkcji. Szczerze mówiąc, ten nie działa z większością czcionek, ale jest to oryginalne uzasadnienie nazw.

jeden to Big „O”

jeden to Wielka Theta

http://en.wikipedia.org/wiki/Big_O_notation

Duże O oznacza, że ​​Twój algorytm wykona się nie więcej niż w danym wyrażeniu (n ^ 2)

Duża Omega oznacza, że ​​Twój algorytm wykona się nie mniej niż w podanym wyrażeniu (n ^ 2)

Jeśli oba warunki są prawdziwe dla tego samego wyrażenia, możesz użyć dużej notacji theta ....

Zamiast podać teoretyczną definicję, którą już tutaj pięknie podsumowuję, podam prosty przykład:

Załóżmy, że czas działania f(i)to O(1). Poniżej znajduje się fragment kodu, którego asymptotycznym środowiskiem wykonawczym jest Θ(n). To zawsze wywołuje funkcję f(...) nrazy. Zarówno dolna, jak i górna granica to n.

for(int i=0; i<n; i++){
    f(i);
}

Drugi fragment kodu poniżej ma asymptotyczny czas działania O(n). W f(...) większości n przypadków wywołuje funkcję . Górna granica to n, ale dolna granica może być Ω(1)lub Ω(log(n)), w zależności od tego, co dzieje się w środku f2(i).

for(int i=0; i<n; i++){
    if( f2(i) ) break;
    f(i);
}

Theta to skrótowy sposób na odniesienie się do specjalnego situtation, w którym duże O i Omega są takie same.

Tak więc, jeśli ktoś twierdzi The Theta is expression q, to oni również koniecznie twierdzą, że Big O is expression qi Omega is expression q.

Szorstka analogia:

Jeśli: Theta twierdzi, „To zwierzę ma 5 nóg”. to znaczy, że: Wielka O jest prawdą („To zwierzę ma mniej niż 5 nóg.”), a Omega jest prawdą („To zwierzę ma więcej niż 5 nóg”).

To tylko z grubsza analogia, ponieważ wyrażenia niekoniecznie są konkretnymi liczbami, ale zamiast tego działają o różnych rzędach wielkości, takie jak log (n), n, n ^ 2, (itd.).

Wykres mógłby wcześniejsze odpowiedzi łatwiejsze do zrozumienia:

Θ-Notacja - To samo zamówienie | Notacja O - górna granica

Po angielsku,

Po lewej stronie zauważ, że istnieje górna granica i dolna granica, które są tego samego rzędu wielkości (tj. G (n) ). Zignoruj ​​stałe, a jeśli górna granica i dolna granica mają ten sam rząd wielkości, można słusznie powiedzieć, że f (n) = Θ (g (n)) lub f (n) jest w dużej theta g (n) .

Zaczynając od prawej, prostszy przykład, mówi, że górna granica g (n) jest po prostu rzędem wielkości i ignoruje stałą c (tak jak robi to cała duża notacja O ).

f(n)należy do, O(n)jeśli istnieje pozytywny kjakof(n)<=k*n

f(n)należy do, Θ(n)jeśli istnieje pozytywny k1, k2jakk1*n<=f(n)<=k2*n

Artykuł w Wikipedii na temat notacji Big O

Korzystanie z limitów

Zastanówmy się f(n) > 0i g(n) > 0na zawsze n. Można to wziąć pod uwagę, ponieważ najszybszy rzeczywisty algorytm ma co najmniej jedną operację i kończy jej wykonanie po uruchomieniu. Uprości to rachunek różniczkowy, ponieważ możemy użyć wartości ( f(n)) zamiast wartości bezwzględnej ( |f(n)|).

1. f(n) = O(g(n))

   Generał:

             f(n)     
   0 ≤ lim ──────── < ∞
       n➜∞   g(n)
   

   Dla g(n) = n:

             f(n)     
   0 ≤ lim ──────── < ∞
       n➜∞    n
   

   Przykłady:

       Expression               Value of the limit
   ------------------------------------------------
   n        = O(n)                      1
   1/2*n    = O(n)                     1/2
   2*n      = O(n)                      2
   n+log(n) = O(n)                      1
   n        = O(n*log(n))               0
   n        = O(n²)                     0
   n        = O(nⁿ)                     0
   

   Kontrprzykłady:

       Expression                Value of the limit
   -------------------------------------------------
   n        ≠ O(log(n))                 ∞
   1/2*n    ≠ O(sqrt(n))                ∞
   2*n      ≠ O(1)                      ∞
   n+log(n) ≠ O(log(n))                 ∞
   

2. f(n) = Θ(g(n))

   Generał:

             f(n)     
   0 < lim ──────── < ∞
       n➜∞   g(n)
   

   Dla g(n) = n:

             f(n)     
   0 < lim ──────── < ∞
       n➜∞    n
   

   Przykłady:

       Expression               Value of the limit
   ------------------------------------------------
   n        = Θ(n)                      1
   1/2*n    = Θ(n)                     1/2
   2*n      = Θ(n)                      2
   n+log(n) = Θ(n)                      1
   

   Kontrprzykłady:

       Expression                Value of the limit
   -------------------------------------------------
   n        ≠ Θ(log(n))                 ∞
   1/2*n    ≠ Θ(sqrt(n))                ∞
   2*n      ≠ Θ(1)                      ∞
   n+log(n) ≠ Θ(log(n))                 ∞
   n        ≠ Θ(n*log(n))               0
   n        ≠ Θ(n²)                     0
   n        ≠ Θ(nⁿ)                     0
   

Wniosek: traktujemy duże O, duże θ i duże Ω jako to samo.

Dlaczego? Podam powód poniżej:

Po pierwsze wyjaśnię jedno błędne stwierdzenie, niektórzy uważają, że zależy nam na najgorszej złożoności czasowej, dlatego zawsze używamy dużego O zamiast dużego θ. Powiem, że ten człowiek bzduruje. Górna i dolna granica służą do opisania jednej funkcji, a nie do opisania złożoności czasowej. Funkcja najgorszego czasu ma swoją górną i dolną granicę; funkcja najlepszego czasu ma również swoją górną i dolną granicę.

Aby jasno wyjaśnić związek między dużym O i dużym θ, najpierw wyjaśnię związek między dużym O i małym O. Z definicji możemy łatwo wiedzieć, że małe o jest podzbiorem dużego O. Na przykład ：

T (n) = n ^ 2 + n, możemy powiedzieć T (n) = O (n ^ 2), T (n) = O (n ^ 3), T (n) = O (n ^ 4). Ale dla małego o, T (n) = o (n ^ 2) nie spełnia definicji małego o. Tak więc tylko T (n) = o (n ^ 3), T (n) = o (n ^ 4) są poprawne dla małego o. Nadmiarowe T (n) = O (n ^ 2) jest czym? Jest duży θ!

Ogólnie mówimy, że duże O to O (n ^ 2), trudno powiedzieć T (n) = O (n ^ 3), T (n) = O (n ^ 4). Dlaczego? Ponieważ podświadomie uważamy duże O za duże θ.

Podobnie podświadomie uważamy również duże Ω za duże θ.

Jednym słowem, duże O, duże θ i duże Ω nie są tym samym z definicji, ale są tym samym w naszych ustach i mózgu.