Būtina sąlyga – Asimptotinės žymos , Asimptotinių žymėjimų savybės , Algoritmų analizė
1. Didžiojo O žymėjimas (O):
Ji apibrėžiama kaip viršutinė riba, o viršutinė algoritmo riba yra daugiausiai reikalingo laiko (blogiausio atvejo našumas).
Didelis O žymėjimas naudojamas apibūdinti asimptotinė viršutinė riba .
Matematiškai, jei f(n) apibūdina algoritmo veikimo laiką; f(n) yra O(g(n)) jei yra teigiama konstanta C ir n0 toks,
0 <= f(n) = n0
n = naudojamas viršutinei funkcijai suteikti.
Jei funkcija yra O(n) , tai automatiškai O (n kvadratas) taip pat.
Grafinis pavyzdys Didysis O:
eilutę į charakterį
2. Big Omega žymėjimas (Ω):
Tai apibrėžiama kaip apatinė ir apatinė algoritmo riba yra mažiausiai reikalingas laikas (veiksmingiausias įmanomas būdas, kitaip tariant, geriausiu atveju).
Tiesiog kaip O žymėjimas pateikti an asimptotinė viršutinė riba , Oi žymėjimas numato asimptotinė apatinė riba .
Leisti f(n) apibrėžti algoritmo veikimo laiką;
f(n) sakoma, kad yra Ω(g(n)) jei yra teigiama konstanta C ir (n0) toks kad
0 <= Cg(n) = n0
Parsisiųsti youtube video vlc
n = naudojamas norint nurodyti apatinę funkcijos ribą
Jei funkcija yra Ω (n kvadratas) tai automatiškai Oi (n) taip pat.
Grafinis pavyzdys Didžioji Omega (Ω):
3. Didysis teta žymėjimas (Θ):
Ji apibrėžiama kaip griežčiausia riba, o griežčiausia riba yra geriausias iš visų blogiausių atvejų, kuriuos gali užtrukti algoritmas.
Leisti f(n) apibrėžti algoritmo veikimo laiką.
f(n) sakoma, kad yra Θ(g(n)) jeigu f(n) yra O(g(n)) ir f(n) yra Ω(g(n)).
Matematiškai,
0 <= f(n) = n0
0 <= C2g(n) = n0pramonė ir gamyklaSujungę abi lygtis, gauname:
0 <= C2g(n) <= f(n) = n0
Lygtis tiesiog reiškia, kad yra teigiamų konstantų C1 ir C2, kad f(n) yra tarp C2 g(n) ir C1g(n).
Grafinis pavyzdys Didysis teta (Θ) :
Skirtumas tarp Big Oh, Big Omega ir Big Theta:
| Taip ne. | Didysis O | Didžioji Omega ( Oi) | Didysis Teta (T) |
|---|---|---|---|
| 1. | Tai kaip (<=) algoritmo augimo greitis yra mažesnis arba lygus tam tikrai vertei. | Tai kaip (>=) augimo greitis yra didesnis arba lygus nurodytai vertei. | Tai lyg (==) reiškia, kad augimo tempas yra lygus nurodytai vertei. |
| 2. | Viršutinė algoritmo riba pavaizduota Big O žymėjimu. Tik aukščiau pateiktą funkciją riboja Big O. Asimptotinė viršutinė riba pateikiama Big O žymėjimu. | Algoritmo apatinė riba pavaizduota Omega žymėjimu. Asimptotinė apatinė riba pateikiama Omega žymėjimu. | Funkcijos riba iš viršaus ir apačios pavaizduota teta žymėjimu. Tikslus asimptotinis elgesys nustatomas naudojant šį teta žymėjimą. |
| 3. | Didysis O – viršutinė riba | Big Omega (Ω) – apatinė riba | Didysis teta (Θ) – griežtas apribojimas |
| 4. | Jis apibrėžiamas kaip viršutinė algoritmo riba, o viršutinė riba yra daugiausiai reikalingo laiko (blogiausio atvejo našumas). | Tai apibrėžiama kaip apatinė ir apatinė algoritmo riba yra mažiausiai reikalingas laikas (veiksmingiausias įmanomas būdas, kitaip tariant, geriausiu atveju). | Ji apibrėžiama kaip griežčiausia riba, o griežčiausia riba yra geriausias iš visų blogiausių atvejų, kuriuos gali užtrukti algoritmas. |
| 5. | Matematiškai: Didysis Oh yra 0 <= f(n) = n0 | Matematiškai: Big Omega yra 0 <= Cg(n) = n0 | Matematiškai – Didysis teta yra 0 <= C2g(n) <= f(n) = n0 |
Norėdami gauti daugiau informacijos, žr. Algoritmų projektavimas ir analizė .