Algoritmų sudėtingumas

Straipsnis iš Vikipedijos, laisvosios enciklopedijos.
Peršokti į: navigaciją, paiešką

Sudėtingumo teorija yra 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.


Algoritmų sudėtingumą galima tirti šiais būdais:

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

Algoritmų laiko sudėtingumas[taisyti | redaguoti kodą]

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 žingsnių; tokia problema yra 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[taisyti | redaguoti kodą]

O žymėjimas
Asimptotiškai „viršutinė“ riba.
  • Apibrėžtis:f(n)=O(g(n)) jei egzistuoja konstantos c ir n_0 tokios, kad c g(n)\geq f(n) visiems n\geq n_0.

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

\Omega žymėjimas
Asimptotiškai „apatinė“ riba.
  • Apibrėžtis:f(n)=\Omega(g(n)) jei egzistuoja konstantos c ir n_0 tokios, kad c g(n)\leq f(n) visiems n\geq n_0.

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

\Theta žymėjimas
Asimptotiškai „ankšta“ riba.
  • Apibrėžtis:f(n)=\Theta(g(n)) jei egzistuoja konstantos c_1, c_2 ir n_0, tokios, kad c_1 g(n)\leq f(n)\leq c_2 g(n) visiems n\geq n_0.

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

o žymėjimas
Asimptotiškai „negriežta viršutinė“ riba.
  • Apibrėžtis:f(n)=o(g(n)) jei egzistuoja konstantos c>0 ir n_0>0, tokios, kad c g(n) > f(n) visiems n\geq n_0.
\omega žymėjimas
Asimptotiškai „negriežta apatinė“ riba.
  • Apibrėžtis:f(n)=\omega(g(n)) jei egzistuoja konstantos c>0 ir n_0>0, tokios, kad c g(n) < f(n) visiems n\geq n_0.

Žymėjimo ypatumai[taisyti | redaguoti kodą]

Žymėjimas f(n)=O(g(n)), kai vietoj O gali būti O,o,\Theta,\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[taisyti | redaguoti kodą]

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²) kvadratinis
O(nc) polinominis, kartais geometrinis
O(cn) eksponentinis Eksponentinė (NP)
O(n!) faktorialas
O(nn) ?

Pavyzdžiai[taisyti | redaguoti kodą]

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