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
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 (Ω):
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 (Θ) :
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 .