Poređenje vremenske složenosti algoritama sortiranja
Uvod
Algoritmi sortiranja su osnovni deo mnogih računarskih problema. Njihova efikasnost se meri vremenskom složenošću, koja opisuje koliko operacija algoritam izvršava u zavisnosti od veličine ulaza.
Osnovni pojmovi
Vremenska složenost je funkcija T(n) koja opisuje broj osnovnih operacija u zavisnosti od veličine niza n. Najčešće osnovna operacija kod sortiranja je poređenje elemenata.
Algoritmi kvadratne složenosti
Ovi algoritmi imaju složenost proporcionalnu kvadratu veličine ulaza, najčešće O(n²).
Bubble sort
Prolazi niz i menja mesta susednim elementima dok niz ne bude sortiran.
Selection sort
Pronalazi najmanji element u nesortiranom delu niza i postavlja ga na odgovarajuće mesto u nizu.
Insertion sort
Ubacuje nove elemente sa desne, nesortirane, strane niza u levu, sortiranu, stranu niza dok leva strana ne postane ceo niz. jako brz za male ili delimično sortirane nizove.
Tabela kvadratnih algoritama
| Algoritam | Formula složenosti | Napomena |
|---|---|---|
| Bubble sort | T(n) = n(n-1)/2 | najgori i prosečan slučaj su spori |
| Selection sort | T(n) = n(n-1)/2 | Broj poređenja ne zavisi od rasporeda elemenata već je uvek kvadratan |
| Insertion sort | T(n) = O(n²) (najgori), O(n) (najbolji) | Efikasan za male ili već delimično sortirane nizove |
Algoritmi logaritamske složenosti
Ovi algoritmi imaju složenost proporcionalnu prozivodu velicine ulaza i njegovog logaritma, najčešće O(n log(n)).
Teorijska donja granica
Nijedan algoritam zasnovan samo na poređenju elemenata ne može imati složenost bolju od O(n log n) u najgorem slučaju.
Merge sort
Koristi pristup "podeli pa vladaj". Niz se deli na polovine dok se ne dobiju nizovi dužine 1, zatim se spajaju u sortiran niz. Formula vremenske složenosti: T(n) = 2T(n/2) + n.
Quick sort
Quick sort je efikasan algoritam koji koristi pristup "podeli pa vladaj". Algoritam bira jedan element niza, tzv. pivot, i raspoređuje ostale elemente tako da su svi manji od pivota levo, a svi veći desno. Zatim se ista procedura rekurzivno primenjuje na leve i desne podnizove dok ceo niz ne bude sortiran.
Tabela efikasnih algoritama
| Algoritam | Formula složenosti | Napomena |
|---|---|---|
| Merge sort | T(n) = O(n log n) | složenost optimalna za sve ulaze. |
| Quick sort | O(n log n) prosečno, O(n²) najgore | Brz u proseku, ali loš pivot može biti problem |
Zaključak
Jednostavni algoritmi (Bubble, Selection, Insertion) su edukativni, dok Merge i Quick sort predstavljaju praktičan izbor za velike nizove u stvarnim primenama.