Algoritmų sudėtingumas

Sudėtingumo teorija – informatikos šaka, nagrinėjanti įvairias algoritmų savybes, dažnai jų įvykdymo greitį. Teorija atsako į klausimą kaip palyginti skirtingus algoritmus sprendžiančius tą pačią užduotį (dažniausiai svarbu yra algoritmo veikimo laikas, bet taip pat nagrinėjama kiek algoritmas sunaudoja atminties, ar jis apskritai baigia darbą, ar galima jį vykdyti lygiagrečiai su keliais kompiuteriais), bei kurie algoritmai yra geriausi.

Pagrindiniai algoritmo sudėtingumo kriterijai: trukmė ir sintaksinis algoritmo aprašymas. Algoritmų sudėtingumą galima tirti šiais būdais:

• Invariantų tyrimas;
• Asimptotinės išraiškos;

Algoritmų laiko sudėtingumas

Laiko sudėtingumo skaičiavimas vertina, kiek laiko reiktų tam tikrai problemai su tam tikru duomenų dydžiu spręsti efektyviausiu algoritmu. Tarkime, kad turint n bitų duomenų kiekį, problema išsprendžiama per n² žingsnių; tokia problema yra n² sudėtingumo. Iš tiesų, kiekvienas algoritmo įgyvendinimas spręstų problemą skirtingu žingsnių skaičiumi, todėl sąlyginis žingsnių skaičius (eilė) žymima O(n²).

Asimptotinis žymėjimas

$O$ žymėjimas

Asimptotiškai „viršutinė“ riba.

• Apibrėžtis:$f(n)=O(g(n))$ jei egzistuoja konstantos $c$ ir $n_0$ tokios, kad $cg(n)\ge f(n)$ visiems $n\ge n_0$.

$O$ dažniausia naudojamas algoritmo blogiausiam atvejui apibūdinti.

$\mathrm{\Omega }$ žymėjimas

Asimptotiškai „apatinė“ riba.

• Apibrėžtis:$f(n)=\mathrm{\Omega }(g(n))$ jei egzistuoja konstantos $c$ ir $n_0$ tokios, kad $cg(n)\le f(n)$ visiems $n\ge n_0$.

$\mathrm{\Omega }$ dažniausia apibūdina algoritmo geriausią atvejį arba apatinę ribą.

$\mathrm{\Theta }$ žymėjimas

Asimptotiškai „ankšta“ riba.

• Apibrėžtis:$f(n)=\mathrm{\Theta }(g(n))$ jei egzistuoja konstantos $c_1,c_2$ ir $n_0$, tokios, kad $c_{1}g(n)\le f(n)\le c_{2}g(n)$ visiems $n\ge n_0$.

Asimptotiškai „ankštai“ ribai taip pat galioja savybė, $f(n)=\mathrm{\Theta }(g(n))⟺f(n)=O(g(n))\wedge f(n)=\mathrm{\Omega }(g(n))$. Asimtotiškai „viršutinė“ riba $O(g(n))$ dažnai yra neteisingai naudojama ankštai ribai $\mathrm{\Theta }(g(n))$ apibrėžti, kuri nepadengia $\mathrm{\Omega }(g(n))$ atvejo.

$o$ žymėjimas

Asimptotiškai „negriežta viršutinė“ riba.

• Apibrėžtis:$f(n)=o(g(n))$ jei $\underset{n\to \mathrm{\infty }}{\lim }(f(n)/g(n))=0$.

$\omega$ žymėjimas

Asimptotiškai „negriežta apatinė“ riba.

• Apibrėžtis:$f(n)=\omega (g(n))$ jei $\underset{n\to \mathrm{\infty }}{\lim }(f(n)/g(n))=\mathrm{\infty }$, t. y., $g(n)=o(f(n))$.

Žymėjimo ypatumai

Žymėjimas $f(n)=O(g(n))$, kai vietoj $O$ gali būti $O,o,\mathrm{\Theta },\mathrm{\Omega },\omega$ yra konceptualiai klaidingas, tačiau yra plačiai naudojamas analizuojant algorithmų sudėtingumą. Korektiškumo dėlei reikėtų vartoti $f(n)\in O(g(n))$

O žymėjimai

Dažniausi algoritmų sudėtingumo žymėjimai ir jų pavadinimai:

Žymėjimas	Sudėtingumas	Klasė
$O(1)$	konstantinis	Polinominė (P)
$O(\log n)$	logaritminis
$O([\log n{]}^c)$	polilogaritminis
$O(n)$	tiesinis
$O(n\log n)$	supratiesinis
$O(n^2)$	kvadratinis
$O(n^c)$	polinominis, kartais geometrinis
$O(c^n)$	eksponentinis	Eksponentinė (NP)
$O(n!)$	faktorialas
$O(n^n)$	?

Pavyzdžiai

Paprasčiausių algoritmų sudėtingumo pavyzdžiai:

• Paieškos algoritmas tiesinėje nesurikiuotų duomenų struktūroje – O(n)
• Paieškos algoritmas tiesinėje surikiuotų duomenų struktūroje – O(log n)
• Rikiavimo algoritmas tiesinėje duomenų struktūroje – O(n · log n)