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 $c\; g(n)\backslash geq\; f(n)$ visiems $n\backslash geq\; n\_0$.

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

$\backslash Omega$ žymėjimas: Asimptotiškai "apatinė" riba.

• Apibrėžtis:$f(n)=\backslash Omega(g(n))$ jei egzistuoja konstantos $c$ ir $n\_0$ tokios kad $c\; g(n)\backslash leq\; f(n)$ visiems $n\backslash geq\; n\_0$.

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

$\backslash Theta$ žymėjimas: Asimptotiškai "ankšta" riba.

• Apibrėžtis:$f(n)=\backslash Theta(g(n))$ jei egzistuoja konstantos $c\_1,\; c\_2$ ir $n\_0$, tokios kad $c\_1\; g(n)\backslash leq\; f(n)\backslash leq\; c\_2\; g(n)$ visiems $n\backslash geq\; n\_0$.

Big_theta2.png

Asimptotiškai "ankštai" ribai taip pat galioja savybė, $f(n)=\backslash Theta(g(n))\; \backslash iff\; f(n)=O(g(n))\backslash wedge\; f(n)=\backslash Omega(g(n))$. Asimtotiškai "viršutinė" riba $O(g(n))$ dažnai yra neteisingai naudojama ankštai ribai $\backslash Theta(g(n))$ apibrėžti, kuri nepadengia $\backslash 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\backslash geq\; n\_0$.

$\backslash omega$ žymėjimas: Asimptotiškai "negriežta apatinė" riba.

• Apibrėžtis:$f(n)=\backslash omega(g(n))$ jei egzistuoja konstantos $c>0$ ir $n\_0>0$, tokios kad visiems $n\backslash geq\; n\_0$.

Žymėjimo ypatumai

Žymėjimas $f(n)=O(g(n))$, kai vietoj $O$ gali būti $O,o,\backslash Theta,\backslash Omega,\backslash omega$ yra konceptualiai klaidingas, tačiau yra plačiai naudojamas analizuojant algorithmų sudėtingumą. Korektiškumo dėlei reikėtų vartoti $f(n)\backslash 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(nc)	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

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

• Paieškos algoritmas tiesinėje nesurūšiuotų duomenų struktūroje - O(n)
• Paieškos algoritmas tiesinėje surūšiuotų duomenų struktūroje - O(log n)
• Rūšiavimo algoritmas tiesinėje duomenų struktūroje - O(n · log n)

Matematika | Algoritmai

Komplexitätstheorie | Θεωρία Πολυπλοκότητας | Computational complexity theory | Complejidad computacional | Complexité algorithmique | סיבוכיות | 計算複雑性理論 | Złożoność obliczeniowa | Komplexitetsteori | ทฤษฎีความซับซ้อนในการคำนวณ | 計算複雜性理論