Selles õpetuses saate teada, mis on asümptootilised tähised. Samuti saate teada Big-O notatsiooni, teeta notatsiooni ja Omega notatsiooni kohta.
Algoritmi efektiivsus sõltub algoritmi käivitamiseks kuluvast ajast, salvestusruumist ja muudest ressurssidest. Efektiivsust mõõdetakse asümptootiliste märkide abil.
Algoritm ei pruugi erinevat tüüpi sisendite puhul olla sama. Sisendi suuruse suurenemisega muutub jõudlus.
Uuring algoritmi toimivuse muutumisest koos sisendi suuruse järjekorra muutumisega on määratletud kui asümptootiline analüüs.
Asümptootilised tähised
Asümptootilised tähised on matemaatilised tähised, mida kasutatakse algoritmi tööaja kirjeldamiseks, kui sisend kaldub kindla või piirväärtuse poole.
Näiteks: kui mulli sorteerimine on juba sisestatud massiivi sorteeritud, on algoritmi jaoks kuluv aeg lineaarne, st parim.
Kuid kui sisendmassiiv on vastupidises olekus, võtab algoritm elementide sortimiseks maksimaalse aja (ruut), st halvimal juhul.
Kui sisendmassiivi pole sorteeritud ega vastupidises järjekorras, võtab see keskmist aega. Neid kestusi tähistatakse asümptootiliste tähistuste abil.
Asümptootilisi tähistusi on peamiselt kolm:
- Big-O tähistamine
- Omega tähistamine
- Teeta tähistus
Big-O tähis (O-tähis)
Big-O tähistus tähistab algoritmi tööaja ülemist piiri. Seega annab see algoritmi halvimal juhul keerukuse.
Big-O annab funktsiooni ülemise piiri
O (g (n)) = (f (n): eksisteerivad positiivsed konstandid c ja n 0, nii et kõigi n ≧ n 0 korral 0 ≦ f (n) ≦ cg (n )
Ülaltoodud väljendus võib kirjeldada kui funktsiooni f(n)kuulub komplekti O(g(n))kui on olemas positiivne konstant c, nii et see jääb 0ja cg(n)jaoks piisavalt suur n.
Mis tahes väärtuse puhul nei ületa algoritmi tööaeg pakutavat aega O(g(n)).
Kuna see annab algoritmi halvima käitamisaja, kasutatakse seda algoritmi analüüsimiseks laialdaselt, kuna meid huvitab alati halvim stsenaarium.
Omega tähistus (Ω-tähis)
Omega tähistus tähistab algoritmi tööaja alumist piiri. Seega tagab see algoritmi parimal juhul keerukuse.
Omega annab funktsiooni alumise piiri
Ω (g (n)) = (f (n): eksisteerivad positiivsed konstandid c ja n 0, nii et kõigi n ≧ n 0 korral 0 ≦ cg (n) ≦ f (n )
Ülaltoodud avaldist võib kirjeldada kui funktsiooni f(n)hulka kuuluvat, Ω(g(n))kui eksisteerib positiivne konstant c, mis jääb cg(n)piisavalt suureks n.
Mis tahes väärtuse puhul nannab Omega algoritmi jaoks vajaliku minimaalse aja Ω(g(n)).
Teeta tähistus (Θ-tähistus)
Teeta tähistus ümbritseb funktsiooni ülalt ja alt. Kuna see tähistab algoritmi tööaja ülemist ja alumist piiri, kasutatakse seda algoritmi keskmise juhtumi keerukuse analüüsimiseks.
Teeta piirab funktsiooni konstantide tegurite piires
Funktsiooni g(n), Θ(g(n))on antud seoses:
Θ (g (n)) = (f (n): eksisteerivad positiivsed konstandid c 1 , c 2 ja n 0, nii et 0 ≦ c 1 g (n) ≦ f (n) ≦ c 2 g (n) kõigi jaoks n ≧ n 0 )
Ülaltoodud avaldist võib kirjeldada kui funktsiooni f(n)kuulub hulka, Θ(g(n))kui on olemas positiivseid konstante ja selline, et selle saab paigutada piisavalt suure n vahele ja .c1c2c1g(n)c2g(n)
Kui funktsioon f(n)asub kuskil vahepeal ja kõigi jaoks , siis öeldakse, et see on asümptootiliselt tihedalt seotud.c1g(n)c2g(n)n ≧ n0f(n)
