Tässä opetusohjelmassa opit asymptoottiset merkinnät. Opit myös Big-O-merkinnöistä, Theta-notaatioista ja Omega-merkinnöistä.
Algoritmin tehokkuus riippuu algoritmin suorittamiseen tarvittavasta ajasta, tallennustilasta ja muista resursseista. Tehokkuus mitataan asymptoottisten merkintöjen avulla.
Algoritmilla ei ehkä ole samaa suorituskykyä erityyppisille tuloille. Syötteen koon kasvaessa suorituskyky muuttuu.
Tutkimus algoritmin suorituskyvyn muutoksesta muutoksen kanssa syöttökoon järjestyksessä määritellään asymptoottiseksi analyysiksi.
Asymptoottiset merkinnät
Asymptoottiset merkinnät ovat matemaattisia merkintöjä, joita käytetään kuvaamaan algoritmin käyntiaikaa, kun tulo pyrkii kohti tiettyä arvoa tai raja-arvoa.
Esimerkiksi: Kun kuplalajittelussa tuloryhmä on jo lajiteltu, algoritmin viemä aika on lineaarinen eli paras tapa.
Mutta kun syöttötaulukko on päinvastaisessa kunnossa, algoritmilla on enimmäisaika (neliöllinen) elementtien lajittelemiseen eli pahimmassa tapauksessa.
Kun syöttötaulukkoa ei ole lajiteltu eikä päinvastaisessa järjestyksessä, se vie keskimääräisen ajan. Nämä kestot on merkitty käyttämällä asymptoottisia merkintöjä.
Asymptoottisia merkintöjä on pääasiassa kolme:
- Big-O-merkintä
- Omega-merkinnät
- Theta-merkinnät
Big-O-merkinnät (O-merkinnät)
Big-O-merkinnät edustavat algoritmin käyntiajan ylärajaa. Siten se antaa algoritmin pahimmassa tapauksessa monimutkaisuuden.
Big-O antaa funktion ylärajan
O (g (n)) = (f (n): on olemassa positiivisia vakioita c ja n 0, niin että 0 ≦ f (n) ≦ cg (n) kaikille n ≧ n 0 )
Edellä ilmaisu voidaan kuvata funktiona f(n)kuuluu joukkoon O(g(n)), jos on olemassa positiivinen vakio csiten, että se on välillä 0ja cg(n), ja riittävän suuri n.
Mitään arvoa n, algoritmin ajoaika ei ylitä tarjoamaa aikaa O(g(n)).
Koska se antaa algoritmin pahimman tapauksen ajoajan, sitä käytetään laajalti algoritmin analysointiin, koska olemme aina kiinnostuneita pahimmassa tilanteessa.
Omega-merkinnät (Ω-merkinnät)
Omega-merkinnät edustavat algoritmin käyntiajan alarajaa. Siten se tarjoaa algoritmin parhaan mahdollisen monimutkaisuuden.
Omega antaa funktion alarajan
Ω (g (n)) = (f (n): on olemassa positiivisia vakioita c ja n 0 siten, että 0 ≦ cg (n) ≦ f (n) kaikille n ≧ n 0 )
Yllä olevaa lauseketta voidaan kuvata funktiona, joka f(n)kuuluu joukkoon, Ω(g(n))jos on olemassa positiivinen vakio csiten, että se on cg(n)riittävän suuri yllä n.
nOmega antaa algoritmin edellyttämän vähimmäisajan mille tahansa arvolle Ω(g(n)).
Theta-merkinnät (Θ-merkinnät)
Theta-merkinnät sulkevat toiminnon ylhäältä ja alhaalta. Koska se edustaa algoritmin käyntiajan ylä- ja alarajaa, sitä käytetään algoritmin keskimääräisen monimutkaisuuden analysointiin.
Teeta rajoittaa toiminnon vakiotekijöihin
Funktion g(n), Θ(g(n))saadaan suhde:
Θ (g (n)) = (f (n): on olemassa positiivisia vakioita c 1 , c 2 ja n 0, niin että 0 ≦ c 1 g (n) ≦ f (n) ≦ c 2 g (n) kaikille n ≧ n 0 )
Edellä ilmaisu voidaan kuvata funktiona f(n)kuuluu joukkoon Θ(g(n)), jos on olemassa positiivisia vakioita , ja siten, että se voidaan välissä ja , ja riittävän suuri n.c1c2c1g(n)c2g(n)
Jos funktio f(n)on missä tahansa välissä ja kaikkien puolesta , sen sanotaan olevan asymptoottisesti tiukasti sidottu.c1g(n)c2g(n)n ≧ n0f(n)
