Algoritmų analizė

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

veikimo laiką
sunaudojamos atminties kiekį

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(n²) 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 n₀, kad visiems n ≥ n₀ 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(2n⁴ + n³ - 10000n + 17) = O(n⁴).

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 n₀, kad visiems n ≥ n₀ 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 c₁, c₂ bei n₀, kad visiems n ≥ n₀ teisinga nelygybė c₁·g(x) < f(x) < c₂·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(n²), ..., O(n¹⁰⁰⁰), ..., O(2ⁿ).