Klase složenosti algoritama (O notacija)

Uvod

U članku o algoritmima nagovestili smo da efikasnost predstavlja (praktično) najbitniju osobinu određenog postupka za obradu podataka (naravno, uz preduslov da je postupak ispravan), i stoga ne čudi da je od samog početaka razvoja računarske industrije postojala težnja da se navedena efikasnost izrazi matematičkim putem, to jest, da se na neki način "kvantifikuje".

Efikasnost algoritama ne može se za prave izraziti matematičkim metodama (na iole praktičan način), ali, može se utvrditi:

na koji način vreme izvršavanja algoritma zavisi od veličine ulaznih podataka
na koji način dodatno memorijsko zauzeće programa zavisi od veličine ulaznih podatka

Dve prethodno navedene stavke predstavljaju vremensku i prostornu složenost algoritama.

Na donjem grafiku, prikazane su različite matematičke funkcije preko kojih se vremenska i prostorna složenost algoritama opisuje (pri čemu posebnu pažnju treba obratiti na brzinu rasta različitih funkcija).

Klase složenosti algoritama - grafik — Slika 1. - Grafički prikaz različitih klasa složenosti algoritama.

U praktičnom smislu, na grafiku se može uočiti da određene funkcije mnogo brže dostižu određene vrednosti (na y osi), u odnosu na druge funkcije.

Ili, ako situaciju posmatramo "u suprotnom smeru" - mnogo sporije ....

linearna funkcija, f(x)=x, kojoj odgovara klasa složenosti O(n), dostiže vrednost 10 za x=10, a vrednost 1000000, tek kada je i x=1000000
kvadratna funkcija, f(x)=x², kojoj odgovara klasa složenosti O(n²), dostiže vrednost 10 za x~=3.16, a vrednost 1000000, već za x=1000
logaritamska funkcija, f(x)=log₂ x, kojoj odgovara klasa složenosti O(logn), dostiže vrednost 10 tek kada x poraste na 1024, a što se tiče dostizanja vrednosti kao što je 1000000 .... recimo da bi bilo potrebno da vrednost na x osi bude izrazito velika (za vrednost 4294967296 na x osi, funkcija dostiže tek vrednost 32).

Takođe, zbog malog raspona vrednosti koje su prikazane na grafiku, moglo bi se pomisliti da nema prevelike razlike između grafika O(nlogn) i O(n²), međutim, ako bismo posmatrali ulaznu vrednost 1024, lako se zaključuje da grafik O(nlogn) dostiže vrednost 10240, a grafik O(n²), vrednost 1048576 - što jeste velika razlika!

Vremenska složenost algoritama

Kao što smo prethodno naveli, vremenska složenost algoritma opisuje na koji način vreme izvršavanja programa zavisi od veličine ulaznih podataka, ili (drugim rečima), na koji način veličina ulaznih podataka utiče na ukupan broj operacija koje je potrebno obaviti zarad rešavanja problema (na primer, koliko puta je potrebno, pri pretrazi ili sortiranju niza i sl, pristupiti svakom elementu i obaviti određene operacije koje se tiču pojedinačnog elementa).

Može se reći da je vremenska složenost algoritma praktično 'sinonim' za složenost algoritma u opštem smislu, dok se o prostornoj složenosti ipak manje vodi računa.

Takođe, kada se govori o nekom konkretnom algoritmu (pogotovo kada je u pitanju vremenska složenost), tipično se posmatra najgori slučaj izvršavanja, pored čega se još može posmatrati:

kako se algoritam ponaša u najboljem slučaju
kako se algoritam ponaša tipično

Razlog za takav pristup, jeste to što većina algoritama u najboljem slučaju ima složenost (pogotovo, vremensku složenost), koja je daleko manja od najgoreg slučaja (ponekad je složenost u najboljem slučaju čak i konstantna), dok se tipično ponašanje algoritma (u praktičnom smislu), u većini situacija poklapa sa najgorim slučajem (što ćemo detaljnije objasniti u nastavku).

Za opisivanje 'najgoreg slučaja' izvršavanja algoritama koristi se poseban zapis - tzv. "O notacija" (ispred zagrade stoji veliko slovo O, a unutar zagrade je navedena konkretna klasa složenosti).

O(1) - konstantna složenost

Za algoritme klase složenosti O(1) svojstveno je to da vreme izvršavanja i broj operacija koje je potrebno obaviti - ne zavise od veličine ulaznih podataka (da bi problem koji se tiče određene strukture podataka bio rešen: potrebno je pristupiti samo jednom elementu, i uvek se obavlja isti broj operacija).

Drugi naziv za klasu složenosti O(1) je konstantna složenost, a što se tiče konkretnih primera, prvo ćemo se osvrnuti na verovatno najpoznatiji primer algoritma konstantne složenosti - pristup elementu statičkog niza.

Kao što je poznato, u nizu koji je deklarisan kao int a[7320], za očitavanje elemenata: a[0] (element na početku niza), a[1419] ('udaljeni' element) i a[7319] (element na kraju niza) - potrebno je isto vreme.

Dodavanje elemenata na stek i uklanjanje elemenata sa steka (o čemu smo pisali u članku o strukturama podataka), takođe su algoritmi složenosti O(1).

O(logn) - logaritamska složenost

Logaritam je matematička funkcija preko koje se određuje eksponent n, u funkciji aⁿ = x, tako da važi: log_a x = n ("logaritam vrednosti x, za osnovu a, iznosi n").

Osnova a u računarskim algoritmima ima vrednost 2, pa stoga važi: log₂ 32 = 5 (2⁵ = 32) i, takođe, log₂ 64 = 6 (2⁶ = 64).

Logaritam sa osnovom 2 ima i poseban naziv - binarni logaritam.

Ako pored prethodno navedenih jednakosti uzmemo u obzir i sledeće jednakosti: log₂ 1048576 = 20 (2²⁰ = 1048576), kao i log₂ 4294967296 = 32, lako je zaključiti da logaritamska funkcija veoma sporo raste!

U algoritmima logaritamske složenosti, vreme izvršavanja proporcionalno je logaritmu veličine ulaznih podataka i, takođe, algoritmi logaritamske složenosti (za razliku od algoritama konstantne složenosti), nisu retki.

Verovatno najpoznatiji primer je algoritam binarne pretrage, koji u nizu od 32 elementa (uzećemo prethodno pomenute vrednosti), pronalazi traženi element u najviše pet koraka, u nizu od 64 elemenata - u najviše šest koraka, ili, u nizu od milion elemenata - u najviše dvadeset koraka (sistematičnim pregledom svega 5, 6 ili 20 elemenata, problem je rešen, i sve tri vrednosti predstavljaju binarne logaritme broja elemenata ulaznih nizova).

O(n) - linearna složenost

Algoritmi linearne složenosti su jednostavni za prepoznavanje: za rešavanje problema potrebno je jedanput pristupiti svakom elementu ulazne strukture (to jest, broj operacija koje je potrebno obaviti, direktno je proporcionalan veličini ulaznih podataka).

Što se tiče 'opšteg utiska' o efikasnosti, O(n) algoritmi se smatraju prilično efikasnim u većini situacija, ali - ne uvek.

Na primer, ukoliko je potrebno ispisati sve elemente ulančane liste ili statičkog niza, svako je potrebno (i) obići sve elemente.

Međutim, ukoliko je potrebno pronaći, samo jedan element, linearna pretraga se nikako ne može smatrati efikasnim algoritmom!

Zarad pronalaženja elementa (u najgorem slučaju):

u nizu od 32 elementa, potrebno je obići, tj pregledati, upravo 32 elementa
u nizu od 64 elementa potrebno je obići 64 elementa
u nizu od 10⁶ elemenata, potrebno je obići svih milion elemenata (odnosno, napraviti milion koraka pretrage)

Ako se setimo da u slučaju binarne pretrage pretraživanje niza od milion elemenata podrazumeva ~20 koraka, lako je uvideti da je razlika - prilično drastična.

O(nlogn) - "međukorak" između linearne i kvadratne složenosti

Klasa O(nlogn), svojevrsna je kombinacija logaritamske složenosti i linearne složenosti, i često se sreće u računarskim algoritmima.

U smislu vremenske složenosti, klasa O(nlogn) se nalazi između linearne i kvadratne složenosti - s tim da je znatno bliža linearnoj * i (u većini situacija), algoritmi klase O(nlogn) se i dalje smatraju efikasnima.

Kada se pomene klasa složenosti O(nlogn), većini programera prvo će pasti na pamet dva najpoznatija efikasna algoritma za sortiranje nizova: Quick sort i Heap sort, ali, pošto bi neko od starijih i upućenijih čitalaca mogao da se seti da u najgorem slučaju (koji svakako nije tipičan), algoritam Quick sort ima složenost O(n²), kao primer će poslužiti (samo) algoritam Heap sort.

Heap je binarno stablo, čija se visina može shvatiti kao binarni logaritam broja elemenata stabla, a sortiranje niza upotrebom strukture heap podrazumeva uklanjanje čvorova.

Uklanjanje jednog elementa (tj. čvora) sa heap-a, zahteva (upravo) log(n) koraka, ali, pošto je u pitanju samo jedan element (kojih ima ukupno n), jasno je da se procedura uklanjanja čvora mora ponoviti n puta, i stoga je ukupna složenost algoritma: n * log(n).

O(n²) - kvadratna složenost

Klasu složenosti O(n²), za koju se takođe koristi i odrednica kvadratna složenost, odlikuje vreme izvršavanja koje raste sa kvadratom veličine ulaznih podataka (ili, drugačije: broj operacija koje je potrebno izvršiti zarad rešavanja problema, proporcionalan je kvadratu veličine ulaznih podataka).

Algoritmi kase O(n²) tipično se smatraju neefikasnim, ali, takva klasifikacija je takođe podložna interpretaciji i zavisi od toga da li se za određeni (konkretan) problem može pronaći bolje rešenje.

Da pojasnimo: sa jedne strane, postoje algoritmi za sortiranje nizova čija je složenost kvadratna (bubble sort, selection sort i sl) - i pri tom se navedeni algoritmi (i slični), smatraju izuzetno neefikasnim.

Sa druge strane, mnoge algoritme iz oblasti dinamičkog programiranja odlikuje upravo kvadratna složenost, ali - takvi se algoritmi smatraju (veoma) efikasnim.

Situacija je relativna i (kao što smo već naveli), zavisi od toga da li algoritam o kome se diskutuje predstavlja "najoptimalnije" (do tada pronađeno) rešenje za određeni problem (ili ne).

Kao tipične primere klase složenosti O(n²), možemo navesti prethodno pomenute neefikasne algoritme za sortiranje nizova, bubble sort i selection sort (kod kojih se elementi porede "svaki sa svakim").

Još malo teorije ....

Pominjali smo u uvodu: najbolji, najgori i tipični slučaj izvršavanja algoritma (i takođe smo nagovestili da se najgori slučaj i tipični slučaj često poklapaju).

Ponovo ćemo za primer uzeti algoritam binarne pretrage.

U najboljem slučaju, traženi element može biti pronađen već u prvom koraku, ali, u ogromnoj većini situacija - to se neće desiti (i praktično, ako se desi, u pitanju je čista sreća ili splet okolnosti).

Najgori slučaj podrazumeva traženje elementa na nivou koji je najudaljeniji od korenog čvora.

Što se tiče "tipičnog slučaja", ako se usmerimo na elemente sa 'najudaljenijih' nivoa u stablu koje smo koristili u članku o binarnoj pretrazi) ....

Binarno stablo pretrage — Slika 2. Primer binarnog stabla pretrage.

.... možemo primetiti da se na poslednjem nivou nalaze: najmanji element, najveći element, kao i razni elementi čija vrednost postepeno raste od najmanjeg ka najvećem (a situacija je slična i u ogromnoj većini drugih iole razgranatih stabala pretrage).

Jednostavnije: može se reći da su u pitanju tipični elementi niza.

Stoga, budući da su u pitanju (nasumični) elementi kakvi se tipično potražuju, ali, pozicionirani tako da se nalaze na mestu gde algoritam pokazuje najveće vreme izvršavanja, vidimo (praktično) da se najgori slučaj izvršavanja i tipični slučaj izvršavanja algoritma - poklapaju (naravno, to što smo naveli, ipak ne važi za sve algoritme).

Ostale klase složenosti

Kada se govori o "ostalim" klasama složenosti (kao što je navedeno u gornjem naslovu), tipično se misli na algoritme čija je složenost veća od kvadratne, pri čemu se najčešće srećemo sa klasama O(n³) - kubna složenost i O(kⁿ) - eksponencijalna složenost (gde k može ali i ne mora biti 2) i, naravno - u pitanju su algoritmi velike složenosti, kakve je poželjno izbegavati (ukoliko je ikako moguće).

O(n³) - kubna složenost

Algoritme kubne složenosti odlikuje vreme izvršavanja koje raste sa kubom veličine ulaznih podatka (ukoliko se količina ulaznih podataka duplira, vreme izvršavanja raste 8 puta, to jest, 2³*x).

Trostruko ugnežđene petlje, sa kakvima se ne srećemo suviše često (ali isto tako - ni iz daleka retko), verovatno su najočigledniji primer kubne složenosti:

		
for (i = 0; i < n; ++i) {
	for (j = 0; j < m; ++j) {
		for (k = 0; k < p; ++k) {
			// naredbe
		}
	}
}

Slika 3. - Primer trostruko ugnežđene petlje koju odlikuje složenost O(n³).

O(kⁿ) - eksponencijalna složenost

Za algoritme eksponencijalne složenosti važi da je veličina ulaznog podatka, eksponent (tj. stepen), u funkciji koja opisuje složenost algoritma.

Uzmimo za primer algoritam za pronalaženje lozinke metodom "grube sile".

Složenost se može izraziti kao O(kⁿ), gde vrednost k predstavlja broj mogućih znakova (za svako mesto), a n predstavlja broj mesta.

Kraća analiza

Može se reći da algoritme klase složenosti O(n³) odlikuje složenost koja je .... "donekle" .... umerena - pod uslovom da je veličina ulaznih podataka takođe (bar 'koliko-toliko') umerena. *

Međutim, eksponencijalna složenost podrazumeva (u najvećem broju situacija), da vreme izvršavanja raste izrazito velikom brzinom, pri čemu ulazni podaci ne moraju imati (ni iz daleka) veliki obim.

Na primer, u članku koji je posvećen lozinkama, prikazali smo situaciju u kojoj, ukoliko se broj mesta u lozinki poveća sa četiri na osam (pri čemu smo računali da je broj mogućih znakova 26), ** vreme izvršavanja programa poraste sa nekoliko desetina milisekundi na nekoliko - sati!

* Algoritmi klase O(n²), a pogotovo algoritmi čija je složenost još veća, ni izdaleka nisu efikasni kada je u pitanju obrada velikih kolekcija podataka. Videćemo, u poslednjem odeljku članka, očigledan i ubedljiv primer u kome se koristi algoritam složenosti O(n²), pa neće biti teško zaključiti kako bi se u svemu ponašao znatno neefikasniji algoritam složenosti O(n³).

Međutim, na ovom mestu ćemo se za trenutak zadržati na nizovima manjih dimenzija, i razmatranjima koja se tiču klasa složenosti O(n³) i O(kⁿ) - između kojih postoji poveća razlika.

Probajte sami: dopunite kod sa slike #2, tako što ćete (za početak), inicijalizovati promenljive m, n i p vrednošću 4, a među naredbe dodajte: usleep(100);, čime ćete postići da jedna iteracija unutrašnje petlje traje ~1mikrosekundu (da bi kod proradio, potrebno je da uključite biblioteku unistd.h).

Pokrenite kod i zapamtite vreme izvršavanja, a potom promenite vrednosti promenljivih m, n i p, na 8 (i ponovo pokrenite program).

Videćete da se vreme izvršavanja nije drastično povećalo - što nije bio slučaj sa algoritmom složenosti O(kⁿ) koji smo prethodno opisali.

Međutim, da ne biste ostali pod utiskom da korišćenje algoritama složenosti O(n³) "nema cenu", probajte i vrednosti 20, 40 i 50. :)

** U praksi, za svako mesto se koristi znatno više od 26 znakova (u kom slučaju je razlika između četvoroslovnih lozinki i osmoslovnih - još ubedljivija).

Prostorna složenost algoritama

Kao što smo na početku već nagovestili, prostorna složenost algoritama (tj. uticaj količine ulaznih podataka na dodatno memorijsko zauzeće), u praksi najčešće nema toliki značaj kao vremenska složenost, međutim, poznavanje osnovnih principa - nikako ne može štetiti.

Pre svega, rekli bismo da u današnje vreme (koje se razlikuje od početnog perioda razvoja računarske industrije, kada je memorija bila izrazito skupa i prilično nedostupna), teoretska razmatranja u vezi sa prostornom složenošću algoritama, nemaju toliki značaj koliki ima praktična analiza maksimalnog (očekivanog) memorijskog zauzeća (u smislu: da li se za pokretanje programa uvek može obezbediti dovoljno memorije u realnim uslovima eksploatacije, ili ne može).

Što se tiče 'tehnikalija', pri razmatranju prostorne složenosti algoritama, u obzir se uzima samo dodatno memorijsko zauzeće (nezavisno od memorijskog prostora za smeštaj ulaznih podataka).

Prostorna složenost algoritma (to jest, dodatno memorijsko zauzeće), takođe se izražava preko klasa sa kojima smo se već upoznali: O(1), O(n), O(n²) i sl, pri čemu je zanimljivo primetiti da se klasa prostorne složenosti određenog algoritma, vrlo često ne poklapa sa klasom vremenske složenosti istog algoritma (nije neočekivano, ali, vredi primetiti). :)

Na primer, neefikasni algoritmi za sortiranje nizova koje smo pominjali (bubble sort i selection sort), koje odlikuje "nezavidna" klasa vremenske složenosti, zapravo imaju prostornu složenost O(1), jer dodatno memorijsko zauzeće, podrazumeva - samo pomoćnu promenljivu koja se koristi u pomoćnoj funkciji za razmenu vrednosti dve promenljive (a isto važi i za efikasni algoritam za sortiranje heap sort, koji ne koristi dodatne strukture podataka za razmeštanje elemenata niza).

Nasuprot navedenim primerima, drugi efikasni algoritam koji smo pominjali, quick sort, ima prostornu složenost O(n). *

* U algoritmu quick sort, rekurzivni pozivi generišu se za svaki element (kojih ima n).

Da se osvrnemo na još dva primera koji se tiču prostorne složenosti algoritama (odnosno, složenosti algoritama u opštem smislu).

Algoritmi iz oblasti dinamičkog programiranja, u većini slučajeva se ne odlikuju malom prostornom složenošću, međutim, 'poenta' dinamičkog programiranja je, doslovno, u primetnom umanjivanju vremenske složenosti algoritma nauštrb prostorne složenosti.

(Naravno, prava poenta je 'samo' u umanjivanju vremenske složenosti, a uvećanje prostorne složenosti je 'nusprodukt'. :))

Drugi primer je 'suprotan': algoritam za pronalaženje lozinke metodom grube sile, odlikuje se zanemarljivim dodatnim prostornim zauzećem, međutim, to - u praktičnom smislu - 'pada u vodu' kada uzmemo u obzir izrazito veliku vremensku složenost.

Preko dodatnih primera, želeli smo da (dodatno) potcrtamo da se pri izboru algoritma moraju uzeti u obzir razne pojedinosti.

Za kraj - još malo prakse ....

Vraćamo se (za sam kraj), na vremensku složenost algoritama.

Videli smo kako stvari stoje sa algoritmima eksponencijalne složenosti, koji se koriste za obradu manjih kolekcija podataka, pa preostaje da se osvrnemo i na primer koji smo najavili, koji se tiče primene algoritama složenosti O(n²) u obradi većih kolekcija ....

U tom smislu, deluje da smo ranije "neopravdano ocrnili" algoritme za sortiranje nizova čija je složenost O(n²)?!

Naravno da O(n²) algoritmi za sortiranje nisu "loši" sami po sebi (u tom smislu da postupci nisu 'nerazumni' i da navedeni algoritmi imaju izvesnu pedagošku vrednost), ali, što se tiče toga da li su O(n²) algoritmi za sortiranje "brzi ili spori", u praksi se da primetiti sledeće:

za sortiranje statičkog niza od pola miliona elemenata, brzi(nski)m algoritmima za sortiranje tipično je potrebno između jedne i dve sekunde
Bubble sort i Selection sort isti posao obavljaju (verovatno već znate šta sledi :)) - više sati *

Dakle, možemo videti da složenost neefikasnijeg (od dva) algoritma ne mora biti veća od O(n²), a da pri tom rezultati izvršavanja programa budu veoma 'očigledni'.

Slobodno obavite samostalni eksperiment kojim ćete isprobati prethodno navedene algoritme za sortiranje i sami ustanoviti da li se veliki nizovi sortiraju toliko dugo preko O(n²) algoritama - ako baš imate vremena. :)

Autor članka Nikola Vukićević Za web portal codeblog.rs

Napomena: Tekstovi, slike, web aplikacije i svi ostali sadržaji na sajtu codeblog.rs (osim u slučajevima gde je drugačije navedeno) predstavljaju intelektualnu svojinu autora sajta codeblog.rs i zabranjeno je njihovo korišćenje na drugim sajtovima i štampanim medijima, kao i bilo kakvo drugo korišćenje u komercijalne svrhe, bez eksplicitnog pismenog odobrenja autora.