Algoritmi/Matematičke osnove

Pre nego što počnemo da se bavimo algoritamskim tehnikama, moramo da izučimo neophodne matematičke osnove (matematički aparat). Prvo ćemo da pokrijemo matematičke definicije termina koji se koriste u knjizi. Proširenjem matematičkog vokabulara, bićete mnogo precizniji i u stanju da mnogo jednostavnije formulišete problem. Zatim ćemo obraditi tehnike analize vremena izvršenja algoritma. Posle svakog bitnog algoritma koji je obrađen u knjizi, sledi analiza vremena izvršenja i dokaz ispravnosti.

Asimptotska notacija

Uz ispravnost, važna odlika korisnog algoritma je vreme izvršenja i utrošeni memorijski prostor. Vreme i memorija su važni resursi i među njima postoji bitna razlika u načinu korišćenja, čak i ako ih ima u izobilju. Kako se može izmeriti potrošnja resursa? Jedan način je da napravite funkciju koja odražava njihovo upotrebu u odnosu na neke karakteristike ulaza. Jedna od uobičajenih karakteristika ulaza je veličina skupa podataka. Na primer, pretpostavimo da je ulaz nekog algoritma vektor od $n$ celih brojeva. Vreme izvršenja algortma možemo da opišemo funkcijom $f$ koja zavisi od $n$.

$f(n)=n^{2}+3n+14$

gde je vrednost funkcije $f(n)$ izražena u nekoj jedinici vremena. (U ovom razmatranju glavni fokus je na vremenu, ali isto može da se primeni i na utrošak memorije). Retko se kao jedinica vremena koristi sekunda, jer vreme izvršenja zavisi od mašine, njenog operativnog sistema i trenutnog opterećenja. Umesto u sekundama, vreme se najčešće izražava kao potreban broj nekih osnovnih operacija računara. Na primer, neke od osnovnih operacija koje se koriste su: potreban broj sabiranja ili množenja; broj poređenja (komparacija); izvedeni broj zamena memorijskih lokacija; ili broj izvršenih mašinskih instrukcija. Generalno, mogli bismo se referisati samo na izvršenje navedenih osnovnih operacija.

Da li je ovo dobar pristup za određivanje utroška resurs jednog algoritma? I da i ne. Kada su dva algoritma slična po utrošku vremena, može da pomogne precizna funkcija koja bi odredila koji je algoritam brži u datim uslovima. Ali u mnogim slučajevima je teško ili nemoguće dati tačan analitički opis potrebnog broja operacija, naročito kada algoritam izvršava operacije uslovno - u zavisnosti od vrednosti ulaza. Umesto toga, ono što je zaista važno nije tačno vreme potrebno da se izvrši određena funkcija, već stepen promene utroška resursa u zavisnosti od ulaza. Konkretno, razmotrićemo dve prikazane funkcije koje daju potrebno vreme izvršenja u odnosu na veličinu ulaznog skupa podataka:

$f(n)=n^{3}-12n^{2}+20n+110$

$g(n)=n^{3}+n^{2}+5n+5$

One izgledaju prilično različito, ali kako se ponašaju? Pogledajmo nekoliko grafika ovih funkcija ($f(n)$ u crvenoj, $g(n)$ u plavoj boji):

Grafikoni f i g, za opseg 0 do 5	Grafikoni f i g, za opseg 0 do 15
Grafikoni f i g, za opseg 0 do 100	Grafikoni f i g, za opseg 0 do 1000

U prvom, jako ograničenom grafiku krive izgledaju različito. U drugom krive kreću u sličnom pravcu, u trećem postoji samo mala razlika i u poslednjem su skoro identične. U stvari one se približavaju dominantnom članu. Što je n veće, ostali članovi postaju manje značajni u odnosu na $n^{3}$. Kao što se može videti, promena koeficijenata članova nižeg reda algoritma polinomijalnog vremena ne pomaže mnogo. Ono što je stvarno važno je koeficijent člana najvišeg reda. Zato smo usvojili posebnu notaciju za ovu vrstu analize. Tako je:

$f(n)=n^{3}-12n^{2}+20n+110=O(n^{3})$

Zanemarujemo članove nižeg reda. Možemo da kažemo da je:

$O(\log {n})\leq O({\sqrt {n}})\leq O(n)\leq O(n\log {n})\leq O(n^{2})\leq O(n^{3})\leq O(2^{n})$

Ovo nam pruža način da lakše poredimo različite algoritme. Za sortiranje $n$ elemenata umetanjem (insertion sort), potrebno je reda veličine $O(n^{2})$ koraka. Za sortiranje spajanjem (merge sort) potrebno je $O(n\log {n})$ koraka. Tako, ako je skup ulaznih podataka dovoljno velik, sortiranje spajanjem je brže od sortiranja umetanjem.

Generalno pišemo da važi:

$f(n)=O(g(n))$

kada je zadovoljeno:

$\exists c>0,\exists n_{0}>0,\forall n\geq n_{0}:0\leq f(n)\leq c\cdot g(n).$

Ovo znači da $f(n)=O(g(n))$ važi ako i samo ako postoje konstante $c$ i $n_{0}$ veće od nule, tako da za svaki $n>n_{0}$, $f(n)$ funkcija je pozitivna i manja ili jednaka $cg(n)$. Primetimo da znak jednakosti koji se koristi u gornjem zapisu, opisuje relaciju između $f(n)$ i $g(n)$ , a ne istinsku ekvivalentnost. U svetlu toga, neki definišu veliko O u terminima skupova, tako da je:

$f(n)\in O(g(n))$

kada je:

$f(n)\in \{f(n):\exists c>0,\exists n_{0}>0,\forall n\geq n_{0}:0\leq f(n)\leq c\cdot g(n)\}.$

Veliko O notacija je samo gornja granica – supremum; oba sledeća iskaza su tačna:

$n^{3}=O(n^{4})$

$n^{4}=O(n^{4})$

Ako uzmemo da znak jednakosti označava ekvivalenciju, dobićemo jako čudan rezultat, tj. da je:

$n^{3}=n^{4}$

što je očigledna besmislica. Zato je definicija na bazi teorije skupova zgodna. Zabuna može da se izbegne time što ćete znak jednakosti interpretirati kao jednosmeran tj.:

$n^{3}=O(n^{4})$

ne implicira da važi i:

$O(n^{4})=n^{3}$

Uvek držite O na desnoj strani znaka jednakosti.

Veliko omega

Ponekad nam nije dovoljno da odredimo samo gornju granicu vremena izvršenja neke funkcije. Veliko omega nam daje donju granicu – infinum. Generalno, kažemo da je:

$f(n)=\Omega (g(n))$

kada važi:

$\exists c>0,\exists n_{0}>0,\forall n\geq n_{0}:0\leq c\cdot g(n)\leq f(n).$

tj. $f(n)=\Omega (g(n))$ ako i samo ako postoje konstante c i n₀ takve da je za svako n>n₀, f(n) pozitivna i veća ili jednaka cg(n). Tako, na primer, možemo da tvrdimo da je:

$n^{2}-2n=\Omega (n^{2})$, (c=1/2, n₀=4) ili

$n^{2}-2n=\Omega (n)$, (c=1, n₀=3),

ali ne možemo da je

$n^{2}-2n=\Omega (n^{3}).$

Veliko teta

Kada je data funkcija istovremeno i O(g(n)) i Ω(g(n)), kažemo da je Θ(g(n)), i tada imamo tesne granice funkcije. Funkcija f(n) je Θ(g(n)) kada važi:

$\exists c_{1}>0,\exists c_{2}>0,\exists n_{0}>0,\forall n\geq n_{0}:0\leq c_{1}\cdot g(n)\leq f(n)\leq c_{2}\cdot g(n),$

Ali u većini slučajeva kada pokušavamo da utvrdimo da je zadata funkcija $f(n)=\Theta (g(n))$, umesto da koristimo gornju definiciju, pokazujemo da je ona istovremeno i O(g(n)) i Ω(g(n)).

Malo o i omega

Kada asimptotske granice nisu tesne, to možemo da izrazimo tako što kažemo da je $f(n)=o(g(n))$ ili $f(n)=\omega (g(n)).$. Definiše se:

f(n) je o(g(n)) akko $\forall c>0,\exists n_{0}>0,\forall n\geq n_{0}:0\leq f(n)<c\cdot g(n)$ i

f(n) je ω(g(n)) akko $\forall c>0,\exists n_{0}>0,\forall n\geq n_{0}:0\leq c\cdot g(n)<f(n).$

Primetimo da je funkcija f u o(g(n)) kada za svaki koeficijent g, g na kraju postaje veća od f, dok je za O(g(n)) potrebno da postoji jedan koeficijent za koji g postaje najmanje jednak f.

Analiza algoritama: rešavanje diferencnih jednačina

Za sortiranje n elemenata spajanjem: $T(n)=2*T(n/2)+c(n)$. Ovo opisuje jednu iteraciju sortiranja: prostor problema $n$ se svodi na dve polovine ($2*T(n/2)$), koje se spajaju po okončanju svih rekurzivnih poziva ($c(n)$). Ovaj sistem obeležavanja (notacija) je osnova za analizu algoritama, tako da treba što pre da se na njega naviknete. Postoje teoreme koje možete da koristite da bi procenili vreme velikog O za funkciju čija se diferencna (rekurentna) jednačina uklapa i određeni šablon.

Glavna teorema

Razmotrimo diferencnu jednačinu koja se uklapa u formulu:

$T(n)=aT\left({\frac {n}{b}}\right)+O(n^{k})$

za a ≥ 1, b > 1 i k ≥ 0. Ovde je a broj rekurzivnih poziva za jedan poziv funkcije, n je veličina ulaza, b je faktor za koji se ulaz smanjuje i k je polinomijalni red operacije koja se pojavljuje svaki put kada se pozove funkcija (osim za bazne slučajeve). Na primer, kod algoritma sortiranja spajanjem, koji ćemo pokriti kasnije, imamo da je

$T(n)=2T\left({\frac {n}{2}}\right)+O(n)$

zato što se dva potproblema pozivaju (rešavaju) za svaku iteraciju slučaja koji nije bazni i veličina vektora se svaki put deli na pola. $O(n)$ je na kraju „pobednički“ deo ove podele i pobednički algoritam: on troši linearno vreme za spajanje rezultata dva rekurzivna poziva u jedan konačni rezultat.

Ako zamislimo rekurzivne pozive T kao formiranje stabla, postoje tri moguća slučaja u kojima može da se utvrdi gde se većina vremena izvršenja algoritma troši („većina“ u smislu koji se odnosi na njegovo asimptotsko ponašanje):

1. stablo može da bude razgranato pri vrhu i tada se većina vremena se troši za vreme poziva blizu korena;
2. stablo može da bude uravnoteženo, kada je utrošak vremena ravnomerno raspoređen;
3. stablo može da bude razgranato pri dnu, kada se većina vremena troši na pozive blizu listova.

U zavisnosti od toga u kom se od tri navedena statusa stablo nalazi, T će imati drugačiju složenost:

Glavna teorema

Dato $T(n)=aT\left({\frac {n}{b}}\right)+O(n^{k})$ for a ≥ 1, b > 1 and k ≥ 0:

• Ako je $a<b^{k}$, onda $T(n)=O(n^{k})\$ (razgranato pri vrhu)
• Ako je $a=b^{k}$, onda $T(n)=O(n^{k}\cdot \log n)$ (uravnoteženo)
• Ako je $a>b^{k}$, onda $T(n)=O(n^{\log _{b}a})$ (razgranato pri dnu)

Za gornji slučaj sortiranja spajanjem

$T(n)=2T\left({\frac {n}{2}}\right)+O(n)$

imamo da je

$a=2,b=2,k=1\implies b^{k}=2$

iz čega sledi da je $a=b^{k}$, što čini da je stablo uravnoteženo. Prema glavnoj teoremi složenost sortiranja spajanjem je

$T(n)=O(n^{1}\log n)=O(n\log n)$.