Algoritmų sudėtingumas

Straipsnis iš Vikipedijos, laisvosios enciklopedijos.

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

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

Turinys

[taisyti] 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 ž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²).

[taisyti] Asimptotinis žymėjimas

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

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

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

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

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

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 Θ(g(n)) apibrėžti, kuri nepadengia Ω(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 n0 > 0, tokios, kad cg(n) > f(n) visiems n\geq n_0.
ω žymėjimas
Asimptotiškai „negriežta apatinė“ riba.
  • Apibrėžtis:f(n) = ω(g(n)) jei egzistuoja konstantos c > 0 ir n0 > 0, tokios, kad cg(n) < f(n) visiems n\geq n_0.

[taisyti] Žymėjimo ypatumai

Žymėjimas f(n) = O(g(n)), kai vietoj O gali būti O,o,Θ,Ω,ω 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))

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

[taisyti] Pavyzdžiai

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