Predpoklad - Asymptotické notácie , Vlastnosti asymptotických zápisov , Analýza algoritmov
1. Veľký O zápis (O):
Je definovaná ako horná hranica a horná hranica algoritmu je najviac potrebného času (výkon v najhoršom prípade).
Veľký O zápis sa používa na opis asymptotická horná hranica .
Matematicky, ak f(n) opisuje čas chodu algoritmu; f(n) je O(g(n)) ak existuje kladná konštanta C a n0 také, že
0 <= f(n) = n0
n = používa sa na zadanie hornej hranice funkcie.
Ak je funkcia O(n) , je to automaticky O (n-štvorec) tiež.
Grafický príklad pre Veľké O:
np.histogram
2. Veľký zápis Omega (Ω):
Je definovaná ako dolná hranica a dolná hranica algoritmu je čo najmenej času (najefektívnejší možný spôsob, inými slovami najlepší prípad).
Rovnako ako O notový zápis poskytnúť asymptotická horná hranica , Oh notový zápis poskytuje asymptotická dolná hranica .
Nechaj f(n) definovať čas chodu algoritmu;
f(n) vraj je Ω(g(n)) ak existuje kladná konštanta C a (n0) také že
0 <= Cg(n) = n0
ako získať emotikony iphone na android
n = používané na danú dolnú hranicu funkcie
Ak je funkcia Ω (n-štvorec) je to automaticky oh(n) tiež.
Grafický príklad pre Veľká Omega (Ω):
3. Veľká theta notácia (Θ):
Je definovaná ako najtesnejšia väzba a najtesnejšia väzba je najlepší zo všetkých časov najhoršieho prípadu, ktoré môže algoritmus trvať.
Nechaj f(n) definovať čas chodu algoritmu.
f(n) vraj je Θ(g(n)) ak f(n) je O(g(n)) a f(n) je Ω(g(n)).
java generuje náhodné číslo
matematicky,
0 <= f(n) = n0
0 <= C2g(n) = n0Zlúčením oboch rovníc dostaneme:
0 <= C2g(n) <= f(n) = n0
Rovnica jednoducho znamená, že existujú kladné konštanty C1 a C2, takže f(n) je sendvič medzi C2 g(n) a C1g(n).
Grafický príklad veľká theta (Θ) :
Rozdiel medzi Big oh, Big Omega a Big Theta:
| Áno nie. | Veľký O | Veľká Omega ( oh) | Veľká Theta (ja) |
|---|---|---|---|
| 1. | Je to ako (<=) rýchlosť rastu algoritmu je menšia alebo rovná špecifickej hodnote. | Je to ako (>=) rýchlosť rastu je väčšia alebo rovná špecifikovanej hodnote. | Je to ako (==) čo znamená, že tempo rastu sa rovná určitej hodnote. |
| 2. | Horná hranica algoritmu je reprezentovaná zápisom Big O. Iba vyššie uvedená funkcia je ohraničená Big O. Asymptotická horná hranica je daná notáciou Big O. | Dolnú hranicu algoritmu predstavuje notácia Omega. Asymptotická dolná hranica je daná notáciou Omega. | Ohraničenie funkcie zhora a zdola je reprezentované zápisom theta. Presné asymptotické správanie sa vykonáva týmto zápisom theta. |
| 3. | Veľké O – horná hranica | Veľká Omega (Ω) – Dolná hranica | Big Theta (Θ) – Pevná väzba |
| 4. | Je definovaná ako horná hranica a horná hranica algoritmu je najviac potrebného času (výkon v najhoršom prípade). | Je definovaná ako dolná hranica a dolná hranica algoritmu je čo najmenej času (najefektívnejší možný spôsob, inými slovami najlepší prípad). | Je definovaná ako najtesnejšia väzba a najtesnejšia väzba je najlepší zo všetkých časov najhoršieho prípadu, ktoré môže algoritmus trvať. |
| 5. | Matematicky: Veľký Oh je 0 <= f(n) = n0 | Matematicky: Veľká Omega je 0 <= Cg(n) = n0 | Matematicky – veľká theta je 0 <= C2g(n) <= f(n) = n0 |
Ďalšie podrobnosti nájdete na stránke: Návrh a analýza algoritmov .