Predpogoj – Asimptotični zapisi , Lastnosti asimptotičnih zapisov , Analiza algoritmov
1. Zapis velikega O (O):
Definirana je kot zgornja meja, zgornja meja algoritma pa je največja količina potrebnega časa (zmogljivost v najslabšem primeru).
Veliki O zapis se uporablja za opis asimptotična zgornja meja .
Matematično, če f(n) opiše čas delovanja algoritma; f(n) je O(g(n)) če obstaja pozitivna konstanta C in n0 tako da,
0 <= f(n) = n0
n = uporablja se za podajanje zgornje meje funkciji.
Če je funkcija O(n) , je samodejno O(n-kvadrat) prav tako.
Grafični primer za Veliki O:
linux uredite datoteko
2. Zapis velike omega (Ω):
Opredeljena je kot spodnja meja, spodnja meja algoritma pa je najmanjša količina potrebnega časa (najučinkovitejši možni način, z drugimi besedami najboljši primer).
Tako kot O zapis zagotoviti asimptotična zgornja meja , Oh zapis prispeva asimptotična spodnja meja .
Pustiti f(n) definirati čas delovanja algoritma;
f(n) naj bi bil Ω(g(n)) če obstaja pozitivna konstanta C in (n0) tako da
0 <= Cg(n) = n0
kako dobiti iphone emojije na android
n = uporablja se za podano spodnjo mejo funkcije
Če je funkcija Ω (n-kvadrat) je samodejno Oh(n) prav tako.
Grafični primer za Velika omega (Ω):
3. Big Theta zapis (Θ):
Opredeljen je kot najstrožja vezava in najtesnejša vezava je najboljši od vseh najslabših možnih časov, ki jih algoritem lahko prenese.
Pustiti f(n) določite čas delovanja algoritma.
f(n) naj bi bil Θ(g(n)) če f(n) je O(g(n)) in f(n) je Ω(g(n)).
matematično,
0 <= f(n) = n0
0 <= C2g(n) = n0Če združimo obe enačbi, dobimo:
0 <= C2g(n) <= f(n) = n0
system.out.println
Enačba preprosto pomeni, da obstajata pozitivni konstanti C1 in C2, tako da je f(n) v sendviču med C2 g(n) in C1g(n).
Grafični primer Velika Theta (Θ) :
Razlika med Big oh, Big Omega in Big Theta:
| da ne | Veliki O | velika omega ( Oh) | Velika Theta (JAZ) |
|---|---|---|---|
| 1. | Je kot (<=) stopnja rasti algoritma manjša ali enaka določeni vrednosti. | Je kot (>=) stopnja rasti je večja ali enaka določeni vrednosti. | Je kot (==) kar pomeni, da je stopnja rasti enaka določeni vrednosti. |
| 2. | Zgornja meja algoritma je predstavljena z oznako Big O. Samo zgornja funkcija je omejena z velikim O. Asimptotična zgornja meja je podana z zapisom velikega O. | Spodnja meja algoritma je predstavljena z zapisom Omega. Asimptotična spodnja meja je podana z zapisom Omega. | Omejitev funkcije od zgoraj in spodaj je predstavljena s theta zapisom. Natančno asimptotično vedenje določa ta theta zapis. |
| 3. | Big O – zgornja meja | Velika omega (Ω) – spodnja meja | Big Theta (Θ) – tesno vezana |
| 4. | Opredeljena je kot zgornja meja, zgornja meja algoritma pa je največja količina potrebnega časa (zmogljivost v najslabšem primeru). | Opredeljena je kot spodnja meja, spodnja meja algoritma pa je najmanjša količina potrebnega časa (najučinkovitejši možni način, z drugimi besedami najboljši primer). | Opredeljen je kot najstrožja vezava in najtesnejša vezava je najboljši od vseh najslabših možnih časov, ki jih algoritem lahko prenese. |
| 5. | Matematično: Big Oh je 0 <= f(n) = n0 | Matematično: Velika omega je 0 <= Cg(n) = n0 | Matematično – Big Theta je 0 <= C2g(n) <= f(n) = n0 |
Za več podrobnosti glejte: Oblikovanje in analiza algoritmov .