Složenost algoritama sortiranja
Tekst o složenosti algoritama preuzet iz skripte Programiranje II - dr Gordana Pavlović-Lažetić.
Složenost algoritma (vremenska ili prostorna) je obično neka funkcija koja povezuje veličinu problema (ulaza) sa brojem koraka izvršavanja algoritma (vremenska složenost) ili brojem potrebnih memorijskih lokacija (prostorna složenost). Uobičajeno je da se složenost algoritama (vremenska ili prostorna) procenjuje u asimptotskom smislu, tj. da se funkcija složenosti procenjuje za dosta velike dužine ulaza. Za to se koriste "veliko O" notacija (O()), "omega notacija" (Ω()), i "tetanotacija" (Θ()). "Veliko O" notacija, poznata kao Landau ili Bahman-Landau notacija, opisuje granično ponašanje funkcije kada argument teži nekoj specifičnoj vrednosti ili beskonačnosti, obično u terminima jednostavnijih funkcija. "Veliko O" notacija - dobila je ime od "order of" ili "red veličine" pa ćemo za vremensku složenost koja je reda O(f(n)) govoriti da je "proporcionalna" sa f(n). Analiza vremenske složenosti algoritma ne mora biti precizna (da prebroji svaki korak u izvršavanju algoritma), već je dovoljno da odredi najveće elemente takvih proračuna.
| Analiza složenosti | |||
|---|---|---|---|
| Metoda sortiranja | Vremenska složenost | Prostrana složenost | Stabilnost |
| Selection sort | O(n2) | O(1) | Stabilan |
| Insertion sort | O(n2) | O(1) | Stabilan |
| Bubble sort | O(n2) | O(1) | Stabilan |
| Shell sort | O(nlog2(n)) | O(1) | Zavisi |
| Merge sort | O(nlog(n)) | O(n) | Stabilan |
| Quicksort | O(nlog(n)) | O(log(n)) | Zavisi |