Language
Lt :: En

Algoritmų analizė

Algoritmų analizė

Kaip galima būtų įvertinti algoritmų efektyvumą? Paprastai žiūrima į du dalykus:

Konkrečiais matavimo vienetais (baitais ar sekundėmis) vertinti tai yra sunku, nes konkretūs skaičiai priklauso nuo naudojamos programavimo kalbos, kompiliatoriaus ir apskritai visos aplinkos, o taip pat „geležies“ galimybių. Todėl yra įpasta naudoti asimptotinę notaciją

Užrašas f(x) = O(g(x)) reiškia „funkcija f auga lėčiau už funkciją g(x)“.

Pažymėkime algoritmo veikimo laiką funkcija T(n), kur n yra pradinių duomenų dydis. Užrašas T(n) = O(n) reiškia, jog ši funkcija yra daugiau ar mažiau tiesiogiai proporcinga duomenų dydžiui, T(n) = O(n2) reikštų, kad programos veikimo laikas yra proporcingas duomenų dydžio kvadratui ir t.t.

Formaliai užrašas T(n) = O(f(n)) reiškia, jog egzistuoja tokios konstantos c bei n0, kad visiems n ≥ n0 teisinga nelygybė T(n) < c·f(n). Išvertus į žmonių kalbą tai reiškia, kad esant pakankamai dideliems n programos veikimo laikas yra proporcingas funkcijai f(n).

Nesunku įsitikinti, kad O(a f(n)) = O(f(n)), t.y. galime funkciją f(n) dauginti ar dalinti iš bet kokios teigiamos konstantos a ir nieko tuo nepakeisime. Taip pat galime įsitikinti, kad O(f(n) + g(n)) = O(f(n)) + O(g(n)). Dar viena naudinga lygybė yra O(f(n) + g(n)) = O(f(n)) jei g(n) = O(f(n)), t.y. pridėję lėčiau augančią funkciją g(n) prie greičiau augančios funkcijos f(n) nieko nepakeisime.

Praktiškai tai reiškia, kad jei f(n) yra bet koks n-tojo laipsnio daugianaris, galime ignoruoti visus narius, išskyrus pirmąjį: O(2n4 + n3 - 10000n + 17) = O(n4).

Panašiai užrašas f(x) = Ω(g(x)) reiškia, jog funkcija f(x) auga greičiau už funkciją g(x): egzistuoja konstantos c bei n0, kad visiems n ≥ n0 teisinga f(x) > c·g(x).

Užrašas f(x) = Θ(g(x)) reiškia, jog funkcija f(x) auga tokiu pat greičiu, kaip ir funkcija funkciją g(x): egzistuoja konstantos c1, c2 bei n0, kad visiems n ≥ n0 teisinga nelygybė c1·g(x) < f(x) < c2·g(x).

Asimptotiniai sąryšiai tarp funkcijų primena įprastus ženklus ≤, =, ≥. Vienas skirtumas: ne visos funkcijos yra asimptotiškai sulyginimos, tad kartais nei vienas iš aukščiau minėtų sąryšių netinka.

Dažniausiai pasitaikantys sąryšiai „didėjimo tvarka“: O(1), O(log n), O(n), O(n log n), O(n2), ..., O(n1000), ..., O(2n).


Valid XHTML 1.1! Valid CSS! Paskutiniai pakeitimai: 2016-09-10