Klase složenosti algoritama (O notacija)
Uvod
U uvodnom članku o algoritmima pokazali smo da algoritmi imaju razna svojstva, međutim, takođe se 'prećutno provukla' ideja da je efikasnost (praktično) najbitnija osobina određenog postupka za obradu podataka, naravno, uz preduslov da je postupak ispravan i (poželjno) što jednostavniji, a pošto navedene ideje nisu 'nove i neobične' već (naprotiv) oduvek prisutne, od samog početaka razvoja računarske industrije takođe je postojala težnja da se efikasnost algoritama 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 navedene stavke, predstavljaju vremensku i prostornu složenost algoritama.
Kratak osvrt na nekoliko uobičajenih funkcija
Budući da se složenost algoritama opisuje preko matematičkih funkcija, osvrnućemo se ukratko (pre nego što se posvetimo glavnim temama), na nekoliko funkcija koje se poklapaju sa najuobičajenijim klasama složenosti (takav osvrt biće od koristi u daljem praćenju članka).
Za sada, najvažnije je primetiti da postoje 'prilično nezanemarljive' razlike u brzinu rasta različitih funkcija (a kasnije, sa svakim novim poglavljem članka, razlike među prikazanim funkcijama, tj. klasama složenosti, postaće još jasnije).
Vremenska složenost algoritama
"Vremenska složenost algoritma" je termin koji označava odnos između količine ulaznih podataka i vremena izvršavanja programa, odnosno, u najpraktičnijem smislu (kao što smo na početku nagovestili), u pitanju je funkcija koja opisuje uticaj veličine ulaznih podataka na ukupan broja operacija koje je potrebno obaviti u cilju rešavanja određenog problema (na primer: koliko puta je potrebno, pri pretrazi ili sortiranju niza i sl, pristupiti svakom elementu i obaviti operacije koje se tiču pojedinačnog elementa).
Može se reći da je vremenska složenost praktično 'sinonim' za složenost algoritama 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), uobičajeno je da 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"
U 'svakodnevnim' uslovima, najviše pažnje posvećuje se najgorem slučaju izvršavanja, zato što (1) većina algoritama u najboljem slučaju ima složenost (pogotovo vremensku složenost), koja je daleko manja od najgoreg slučaja, i zato što (2) tipično ponašanje algoritma često odgovara najgorem slučaju izvršavanja. *
Za opisivanje 'najgoreg slučaja' izvršavanja algoritama, ** koristi se poseban zapis - tzv. "O notacija": ispred zagrade stoji veliko slovo O, unutar zagrade je navedena konkretna klasa složenosti, ili (praktično), funkcija koja opisuje vremensku ili prostornu složenost algoritma (smisao takvog zapisa biće prikazan u nastavku).
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 (npr) 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.
int a[7320];
// U praktičnom smislu, "vreme pristupa"
// je isto u sva tri slučaja:
a[0] = 1;
a[1419] = 15;
a[7319] = 20;
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 an = x tako da važi: loga x = n ("logaritam vrednosti x, za osnovu a, iznosi n").
Osnova a u računarskim algoritmima ima vrednost 2, te stoga važi: log2 32 = 5 (25 = 32), i takođe važi: log2 64 = 6 (26 = 64).
Logaritam sa osnovom 2 ima i poseban naziv - binarni logaritam.
Ako pored prethodno navedenih jednakosti uzmemo u obzir i sledeće jednakosti: log2 1048576 = 20 (220 = 1048576), kao i log2 4294967296 = 32, lako je zaključiti da logaritamska funkcija raste veoma sporo!
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:
int binarna_pretraga(int niz[], int broj_elemenata, int vrednost)
{
int levi, desni, srednji;
levi = 0;
desni = broj_elemenata -1;
// Pri pokretanju binarne pretrage,
// podrazumeva se da je niz uređen,
// i stoga se u svakom koraku može
// isključiti "jedna polovina preostalog
// dela niza":
while (levi <= desni) {
// Definisanje "središnjeg" indeksa:
int srednji = levi + (desni - levi) / 2;
// Ukoliko je element pronađen,
// dalja pretraga se obustavlja:
if (niz[srednji] == vrednost) {
return srednji;
}
if (niz[srednji] < vrednost) {
// Ukoliko element na središnjem indeksu
// sadrži vrednost koja je veća od tražene
// vrednosti, iz dalje pretrage se isljučuje
// leva "polovina" preostalog dela niza:
levi = srednji + 1;
}
else {
// Ukoliko element na središnjem indeksu
// sadrži vrednost koja je manja od tražene
// vrednosti, iz dalje pretrage se isljučuje
// desna "polovina" preostalog dela niza:
desni = srednji - 1;
}
}
// Ukoliko traženi element nije pronađen
// ni na jednom indeksu, pretraga vraća
// indeks -1 (kao informaciju o tome da
// traženi element ne postoji u nizu):
return -1;
}
Ako za primer uzmemo prethodno pomenute vrednosti 32, 64 i 1 milion: u nizu od 32 elementa, traženi element se može pronaći 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!
int linearna_pretraga(int niz[], int broj_elemenata, int vrednost)
{
int i = 0;
// Pri pokretanju binarne pretrage,
// pretpostavlja se da niz nije uređen,
// i stoga se redom pretražuju svi elementi:
while (i < broj_elemenata) {
if (niz[i] == vrednost) {
// Čim funkcija pronađe traženi element,
// dalja pretraga se obustavlja:
return i;
}
i++;
}
// I ovoga puta - ukoliko traženi element
// nije pronađen ni na jednom indeksu -
// funkcija vraća indeks -1 kao informaciju
// o tome da se traženi element ne nalazi u nizu:
return -1;
}
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 106 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 najviše 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) je svojevrsna 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, * algoritam Quick sort ima složenost O(n2), kao primer će poslužiti (samo) algoritam Heap sort.
Heap je binarno stablo sa sledećim odlikama:
- u svakom podstablu, koreni čvor ima celobrojnu vrednost koja je (u zavisnosti od toga da li se vrednosti iz stabla sortiraju u neopadajući ili nerastući poredak), ili obavezno veća, ili obavezno manja od pojedinačnih vrednosti čvorova potomaka (u donjem primeru, pošto ćemo niz uređivati u neopadajući poredak, vrednost korenog čvora u svakom podstablu biće veća od ostalih vrednosti)
- visina stabla je binarni logaritam broja elemenata stabla (slično kao u AVL stablima)
- sortiranje niza upotrebom strukture heap, podrazumeva uklanjanje čvorova (po posebnom postupku)
// Pomoćna funkija za razmenu vrednosti
// dve celobrojne promenljive:
void razmena(int *a, int *b)
{
int p = *a;
*a = *b;
*b = p;
}
// Pretvaranje niza u strukturu 'max heap'
// (ali - bez korišćenja dodatnog prostora):
void heapify(int niz[], int n, int i)
{
int najveci = i;
int levi = 2 * i + 1;
int desni = 2 * i + 2;
if (levi < n && niz[levi] > niz[najveci])
najveci = levi;
if (desni < n && niz[desni] > niz[najveci])
najveci = desni;
if (najveci != i) {
razmena(&niz[i], &niz[najveci]);
heapify(niz, n, najveci);
}
}
void heap_sort(int niz[], int n)
{
// Kreiranje strukture 'max heap':
for (int i = n / 2 - 1; i >= 0; i--) {
heapify(niz, n, i);
}
// Uređivanje niza:
for (int i = n - 1; i >= 0; i--) {
razmena(&niz[0], &niz[i]);
heapify(niz, i, 0);
}
}
Da pojasnimo dodatno: 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(n2) - kvadratna složenost
Klasa složenosti O(n2), odnosno klasa 'kvadratne složenosti', odlikuje se vremenom 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 klase O(n2) 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, što ćemo dodatno pojasniti preko jednostavnog primera.
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.
void selection_sort(int niz[], int broj_elemenata)
{
// Algoritam Selection sort podrazumeva
// "biranje" odgovarajuće vrednosti za
// svaku poziciju od prve do pretposlednje:
for (int i = 0; i < broj_elemenata - 1; i++) {
// Ukoliko se na nekom indeksu nalazi
// vrednost koja je veća od "odgovarajuće"
// vrednosti, dve vrednosti zamenjuju pozicije:
for (int j = i + 1; j < broj_elemenata; j++) {
if (niz[i] > niz[j]) {
int p = niz[i];
niz[i] = niz[j];
niz[j] = p;
}
}
}
}
Sa druge strane, mnogi algoritmi iz oblasti dinamičkog programiranja odlikuju se upravo kvadratnom složenošću, 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" pronađeno rešenje za određeni problem (ili ne).
Kao tipične primere klase složenosti O(n2), možemo navesti prethodno pomenute neefikasne algoritme za sortiranje nizova, bubble sort i Selection sort (kod kojih se elementi porede "svaki sa svakim"), a usput ćemo prikazati i 'pokretački kod' za dosadašnje primere:
int main()
{
int niz[] = { 2, 4, 3, -1, 9, 7, 12, 11 };
int broj_pozicija = sizeof(niz) / sizeof(niz[0]);
int vrednost = 4;
int indeks_lin = linearna_pretraga(niz, broj_pozicija, vrednost);
int indeks_bin = binarna_pretraga(niz, broj_pozicija, vrednost);
ispis_niza(niz, broj_pozicija);
printf("Indeks (lin): %d\n", indeks_lin);
printf("Indeks (bin): %d\n", indeks_bin);
// selection_sort(niz, broj_pozicija);
heap_sort(niz, broj_pozicija);
indeks_lin = linearna_pretraga(niz, broj_pozicija, vrednost);
indeks_bin = binarna_pretraga(niz, broj_pozicija, vrednost);
ispis_niza(niz, broj_pozicija);
printf("Indeks (lin): %d\n", indeks_lin);
printf("Indeks (bin): %d\n", indeks_bin);
}
Još malo teorije ....
Pominjali smo u uvodu: najbolji, najgori i tipični slučaj izvršavanja algoritma, pri čemu smo nagovestili da se najgori slučaj i tipični slučaj često poklapaju, što možemo pokazati na primeru algoritma binarne pretrage.
Što se tiče "krajnosti": u najboljem slučaju, traženi element je moguće pronaći već u prvom koraku, ali, u velikoj većini situacija - to se neće desiti (praktično, ako se desi, u pitanju je 'sreća', splet okolnosti i sl), a najgori slučaj podrazumeva traženje elementa na nivoima koji su najudaljeniji od korenog čvora.
Što se tiče "tipičnog slučaja", ako se usmerimo (upravo) na elemente sa 'najudaljenijih' nivoa u stablu koje smo koristili u članku o binarnoj pretrazi) ....
.... može se primetiti da su na poslednjem nivou prisutni: najmanji element, najveći element, kao i razni elementi čija vrednost postepeno raste od najmanjeg ka najvećem (a slično je i u većini drugih iole razgranatih stabala pretrage).
Jednostavnije: može se reći da su u pitanju tipični elementi niza, i stoga, budući da su u pitanju (nasumični) elementi kakvi se "tipično" potražuju, ali, pozicionirani tako da se nalaze na mestu na kome 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 'baš 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(n3) - kubna složenost, i O(kn) - eksponencijalna složenost (gde k može ali i ne mora biti 2).
Naravno, u pitanju su algoritmi velike složenosti, i poželjno je ovakve algoritme izbegavati (ukoliko je ikako moguće).
O(n3) - 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, 23x).
Trostruko ugnežđene petlje, sa kakvima se ne srećemo suviše često (ali isto tako - ni izdaleka retko), verovatno su najočigledniji primer algoritma kubne složenosti:
// Svaka pozicija u prvoj dimenziji niza ....
for (i = 0; i < n; ++i) {
// .... uparuje se sa odgovarajućim
// pozicijama iz druge dimenzije niza ....
for (j = 0; j < m; ++j) {
// .... i treće dimenzije niza ....
for (k = 0; k < p; ++k) {
// .... nakon čega se obavljaju
// predviđene naredbe.
}
}
}
O(kn) - eksponencijalna složenost
Za algoritme eksponencijalne složenosti važi da je veličina ulaznih podataka, eksponent (tj. stepen), u funkciji koja opisuje složenost algoritma.
Uzmimo za primer algoritam za pronalaženje lozinke metodom "grube sile".
#include <stdio.h>
// Radna funkcija koja generiše sve kombinacije
// čija je dužina određena vrednošću promenljive
// broj_pozicija:
void generisanje_kombinacija(char *bafer, char *znakovi, int indeks, int broj_pozicija, int broj_znakova)
{
if (indeks == broj_pozicija) {
printf("%s\n", bafer);
return;
}
for (int i = 0; i < broj_znakova; i++) {
bafer[indeks] = znakovi[i];
generisanje_kombinacija(bafer, znakovi, indeks + 1, broj_pozicija, broj_znakova);
}
}
// Funkcija preko koje se pokreće radna
// funkcija generisanje_lozinki.
// Za svaku dužinu lozinke, od 1 do 'max dužine',
// kreiraju se sve kombinacije znakova:
void generisanje_lozinki(char *znakovi, int broj_pozicija, int broj_znakova)
{
for (int i = 1; i <= broj_pozicija; i++) {
// Pomoćni bafer:
char bafer[i + 1];
generisanje_kombinacija(bafer, znakovi, 0, i, broj_znakova);
}
}
// Pomoćni kod za pokretanje
// funkcije za generisanje lozinki:
int main()
{
char *znakovi = "ABCabc123+-*/!#";
int broj_pozicija = 5;
int broj_znakova = 15;
generisanje_lozinki(znakovi, broj_pozicija, broj_znakova);
}
Složenost prikazanog postupka se može izraziti kao O(kn), gde vrednost k predstavlja broj mogućih znakova (za svako mesto), a n predstavlja broj mesta.
Kratka analiza
U najpraktičnijem smislu, može se reći da algoritme klase složenosti O(n3) odlikuje složenost koja je .... donekle umerena .... pod uslovom da je veličina ulaznih podataka takođe umerena (bar 'koliko-toliko'), * 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 veliki obim (ni izdaleka)).
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!
Prostorna složenost algoritama
Na početku smo se upoznali i sa terminom "prostorna složenost algoritma" koji opisuje uticaj količine ulaznih podataka na dodatno memorijsko zauzeće, pri čemu je nagovešteno da prostorna složenost različitih algoritama najčešće nema praktičan značaj kakav ima vremenska složenost, međutim - poznavanje osnovnih principa nikako ne može 'štetiti' ....
Š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), i pri tom se prostorna složenost algoritma takođe izražava preko klasa sa kojima smo se već upoznali, O(1), O(n), O(n2) i sl, a zanimljivo je primetiti i to 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).
Međutim (da se vratimo na jednu od ranijih primedbi), u praksi, teoretska razmatranja u vezi sa prostornom složenošću algoritama (kako u početnom periodu razvoja računarske industrije tako i u današnje vreme), * 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)).
Drugim rečima: ako određeni algoritam pripada (primera radi) klasi prostorne složenosti O(n4), što "ne deluje dobro", ali je zato (u najgorem slučaju), maksimalno memorijsko zauzeće manje od (recimo) ~80MB, što je količina memorije koja se u današnje vreme gotovo sigurno može obezbediti bilo kom programu, može se smatrati da, u odlučivanju koje se tiče toga da li će algoritam biti izabran kao konačno rešenje (ili neće), klasa prostorne složenosti, verovatno neće igrati preveliku ulogu (to jest, pažnja će verovatno biti usmerena na klasu vremenske složenosti, realnu brzinu izvršavanja na uobičajenim računarima, i druge slične detalje).
Osvrnućemo se 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.
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 stoje stvari 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(n2) u obradi većih kolekcija ....
Deluje (u prethodno navedenom kontekstu), da smo ranije "neopravdano ocrnili" algoritme za sortiranje nizova čija je složenost O(n2)?!
Naravno da O(n2) 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(n2) 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(n2), a da pri tom rezultati izvršavanja programa budu veoma 'očigledni'.
Slobodno obavite samostalni eksperiment putem koga ćete isprobati prethodno navedene algoritme za sortiranje i sami ustanoviti da li se veliki nizovi sortiraju toliko dugo preko O(n2) algoritama - ako baš imate vremena. :)