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 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²).
[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
visiems
.
O dažniausia naudojamas algoritmo blogiausiam atvejui apibūdinti.
- Ω žymėjimas
- Asimptotiškai „apatinė“ riba.
- Apibrėžtis:f(n) = Ω(g(n)) jei egzistuoja konstantos c ir n0 tokios, kad
visiems
.
Ω dažniausia apibūdina algoritmo geriausią atvejį arba apatinę ribą.
- Θ žymėjimas
- Asimptotiškai „ankšta“ riba.
- Apibrėžtis:f(n) = Θ(g(n)) jei egzistuoja konstantos c1,c2 ir n0, tokios, kad
visiems
.
Asimptotiškai „ankštai“ ribai taip pat galioja savybė, . 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
.
- ω ž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
.
[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
[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:
- 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)