Algoritmų sudėtingumas

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ėtingumasKeisti

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ėjimasKeisti

  žymėjimas
Asimptotiškai „viršutinė“ riba.
  • Apibrėžtis:  jei egzistuoja konstantos   ir   tokios, kad   visiems  .

  dažniausia naudojamas algoritmo blogiausiam atvejui apibūdinti.

  žymėjimas
Asimptotiškai „apatinė“ riba.
  • Apibrėžtis:  jei egzistuoja konstantos   ir   tokios, kad   visiems  .

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

  žymėjimas
Asimptotiškai „ankšta“ riba.
  • Apibrėžtis:  jei egzistuoja konstantos   ir  , tokios, kad   visiems  .

Asimptotiškai „ankštai“ ribai taip pat galioja savybė,  . Asimtotiškai „viršutinė“ riba   dažnai yra neteisingai naudojama ankštai ribai   apibrėžti, kuri nepadengia   atvejo.

  žymėjimas
Asimptotiškai „negriežta viršutinė“ riba.
  • Apibrėžtis:  jei  .
  žymėjimas
Asimptotiškai „negriežta apatinė“ riba.
  • Apibrėžtis:  jei  , t. y.,  .

Žymėjimo ypatumaiKeisti

Žymėjimas  , kai vietoj   gali būti   yra konceptualiai klaidingas, tačiau yra plačiai naudojamas analizuojant algorithmų sudėtingumą. Korektiškumo dėlei reikėtų vartoti  

O žymėjimaiKeisti

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

Žymėjimas Sudėtingumas Klasė
  konstantinis Polinominė (P)
  logaritminis
  polilogaritminis
  tiesinis
  supratiesinis
  kvadratinis
  polinominis, kartais geometrinis
  eksponentinis Eksponentinė (NP)
  faktorialas
  ?

PavyzdžiaiKeisti

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