logo

Różnica między notacjami Big O, Big Theta Θ i Big Omega Ω

Warunek wstępny – Notacje asymptotyczne , Własności notacji asymptotycznej , Analiza algorytmów
1. Notacja dużego O (O):

Definiuje się ją jako górną granicę, a górna granica algorytmu to największa wymagana ilość czasu (w najgorszym przypadku wydajność).
Notacja dużego O służy do opisu asymptotyczna górna granica .



Matematycznie, jeśli f(n) opisuje czas działania algorytmu; f(n) Jest O(g(n)) jeśli istnieje stała dodatnia C I n0 taki, że

0 <= f(n) = n0

N = używane do nadania górnej granicy funkcji.
Jeśli funkcja jest NA) , dzieje się to automatycznie O(n-kwadrat) również.



Przykład graficzny dla Wielkie O:

Python drukuje z dokładnością do 2 miejsc po przecinku

Przykład graficzny dla Big oh (O)

2. Notacja Wielkiej Omega (Ω):



Definiuje się go jako dolną granicę, a dolna granica algorytmu to najmniejsza ilość wymaganego czasu (najbardziej efektywny możliwy sposób, innymi słowy najlepszy przypadek).
Tak jak O notacja zapewnić asymptotyczna górna granica , Oh notacja zapewnia asymptotyczna dolna granica .

Pozwalać f(n) zdefiniować czas działania algorytmu;
f(n) mówi się Ω(g(n)) jeśli istnieje stała dodatnia C I (n0) takie, że

0 <= Cg(n) = n0

co to jest modulo w c++

N = używany do podania dolnej granicy funkcji
Jeśli funkcja jest Ω(n-kwadrat) dzieje się to automatycznie Och (n) również.

Graficzny przykład dla Wielka Omega (Ω):

Przykład graficzny dla Big Omega (Ω)

3. Notacja Big Theta (Θ):

Definiuje się je jako najściślejsze ograniczenie, a najściślejsze ograniczenie to najlepszy ze wszystkich najgorszych czasów, jakie może przyjąć algorytm.

Pozwalać f(n) określić czas działania algorytmu.
f(n) mówi się Θ(g(n)) Jeśli f(n) Jest O(g(n)) I f(n) Jest Ω(g(n)).

przemysł i fabryka

Matematycznie,

0 <= f(n) = n0
0 <= C2g(n) = n0

Łącząc oba równania otrzymujemy:

0 <= C2g(n) <= f(n) = n0

Równanie oznacza po prostu, że istnieją dodatnie stałe C1 i C2 takie, że f(n) jest kanapką pomiędzy C2 g(n) i C1g(n).

Graficzny przykład Wielka Theta (Θ) :

Graficzny przykład Big Theta (Θ)

Różnica między Big oh, Big Omega i Big Theta:

Tak nie.

Duże O Wielka Omega ( Oh) Wielka Teta (T)
1. To jest jak (<=)
tempo wzrostu algorytmu jest mniejsze lub równe określonej wartości.
To jest jak (>=)
tempo wzrostu jest większe lub równe określonej wartości.
To jest jak (==)
co oznacza, że ​​tempo wzrostu jest równe określonej wartości.
2. Górna granica algorytmu jest reprezentowana przez notację Big O. Tylko powyższa funkcja jest ograniczona przez Duże O. Asymptotyczna górna granica jest dana przez notację Dużego O. Dolna granica algorytmu jest reprezentowana przez notację Omega. Asymptotyczna dolna granica jest podana w notacji Omega. Granicę funkcji od góry i od dołu reprezentuje notacja theta. Dokładne zachowanie asymptotyczne jest określane za pomocą notacji theta.
3. Duże O – górna granica Duża Omega (Ω) – dolna granica Big Theta (Θ) – Ściśle związane
4. Definiuje się go jako górną granicę, a górna granica algorytmu to największa wymagana ilość czasu (w najgorszym przypadku wydajność). Definiuje się go jako dolną granicę, a dolna granica algorytmu to najmniejsza ilość wymaganego czasu (najbardziej efektywny możliwy sposób, innymi słowy najlepszy przypadek). Definiuje się je jako najściślejsze ograniczenie, a najściślejsze ograniczenie to najlepszy ze wszystkich najgorszych czasów, jakie może przyjąć algorytm.
5. Matematycznie: Big Oh wynosi 0 <= f(n) = n0 Matematycznie: Wielka Omega wynosi 0 <= Cg(n) = n0 Matematycznie – Big Theta wynosi 0 <= C2g(n) <= f(n) = n0

Więcej szczegółów znajdziesz w: Projektowanie i analiza algorytmów .