Pored svojstva ispravnosti programa, važno pitanje za praktičnu primenu je koliko resursa program zahteva za svoje izvršavanje. Najvažniji resursi su vreme potrebno za izvršavanje programa i količina memorije zauzete tokom izvršavanja (mada se mogu analizirati i drugi resursi, na primer, kod mobilnih uređaja važan resurs je utrošena energija). U skladu sa ovim, razmatraju se:
Prostorna složenost odnosi se i na prostor koji zahvataju ulazni podaci. Kada se govori o potrebnom memorijskom prostoru ne računajući prostor koji zahvataju ulazni podaci, onda se govori o dodatnoj prostornoj složenosti.
Iako konkretno vreme izvršavanja zavisi od računara i sistema na kom se program izvršava, relevantne procene utrošenog vremena mogu se dati razmatrajući samo algoritam koji se koristi. Loš algoritam za neki težak problem praktično je neupotrebljiv čak iako bi se koristili računari koji su za nekoliko redova veličina efikasniji nego ovi današnji. Umesto o efikasnosti programa obično se govori o složenosti algoritama. Ovi termini koriste se sinonimno: algoritmi velike složenosti dovode do neefikasnih programa, dok algoritmi male složenosti dovode do efikasnih programa.
Zadatak programera je često da napravi balans između potrošnje različitih vrsta resursa. Neki programi zahtevaju više memorije kako bi se brže izvršavali. Na primer, ako jedan program vrši potrebno izračunavanje za 10 sekundi, a drugi za dva i po minuta, jasno je da je prvi program praktično primenjiviji. Međutim, ako prvi program za svoje izvršavanje zahteva preko 10 gigabajta memorije, drugi oko 1 gigabajt, a mi imamo računar sa 4 gigabajta memorije, prvi program nam je praktično neupotrebljiv (iako radi mnogo brže od drugog). Ipak, s obzirom na to da savremeni računarski sistemi imaju prilično veliku količinu memorije (desetine gigabajta), vreme je ograničavajući faktor češće nego memorija i u nastavku ćemo se više baviti analizom vremenske nego memorijske složenosti algoritama. Sa druge strane, treba imati u vidu da se programi izvršavaju i na nekim specijalizovanim platformama (uređajima sa ugrađenim računarom) i da je moguće da oni imaju mnogo manje memorije nego klasični računari i mobilni uređaji, pa ni prostornu složenost ne treba zanemariti.
Koliko brzo program treba da radi da bismo ga smatrali efikasnim zavisi od konkretne primene. Na primer, ako program uspe da za pola dana reši neki do tada nerešen matematički problem, koji ljudi godinama nisu mogli da reše, on je svakako koristan i možemo ga smatrati veoma efikasnim. Sa druge strane, ako program ugrađen u automobil kontroliše kočnice prilikom proklizavanja, njemu i nekoliko stotinki za izračunavanje može biti previše, jer za to vreme automobil može da nekontrolisano sleti sa puta.
Kod programa koji obrađuju samo male količine podataka, vremenska i prostorna složenost nisu mnogo važne (jer se takvi zadaci izvršavaju brzo čak i ako se koriste naivni algoritmi, i ne zahtevaju mnogo memorije). Međutim, u mnogim situacijama se sasvim prirodno javlja potreba za obradom velikih količina podataka i tada su neefikasni programi praktično neupotrebljivi (na primer, digitalna slika veličine hiljadu puta hiljadu piksela sadrži milion piksela, pa svi algoritmi obrade slika barataju sa ogromnom količinom podataka i moraju koristiti veoma efikasne algoritme).
Iako su spori, naivni programi praktično neupotrebljivi, u razvoju softvera, posebno u nekim oblastima, ponekad se preporučuje da je poželjno prvo kreirati najjednostavniji program koji obavlja dati zadatak, a onda ga modifikovati ako je potrebno da se uklopi u zadata vremenska ili prostorna ograničenja. Naime, naivni algoritmi se često jednostavno implementiraju, lako se razumeju i njihova ispravnost se lako dokazuje, a tokom njihove implementacije programer može steći neke uvide o problemu koji se rešava, dobiti ideje za efikasnija rešenja, generisati testove za testiranje efikasnijih rešenja, uvideti da se neki delovi koda jako retko izvršavaju (pa nema potrebe gubiti vreme na njihovu optimzaciju) i slično.
Ocena potrebnih resursa se obično vrši:
U nekim situacijama nas zanima ponašanje programa za konkretne ulazne podatke koje imamo zadatak da obradimo na konkretnom računaru i tada se analiza programa može izvršiti i eksperimentalno, pokretanjem programa i merenjem utrošenih resursa.
Najjednostavnija mera vremenske efikasnosti programa (ili nekog njegovog dela) je njegovo vreme izvršavanja za neke konkretne vrednosti na konkretnom računaru.
U jeziku C++, pogodan način za merenje utrošenog vremena pružaju funkcije deklarisane u zaglavlju <chrono>. Naredni primer ilustruje kako se može dobiti utrošeno vreme izraženo u mikrosekundama1. Ovako dobijeno vreme nije vreme utrošeno za tekući proces nego apsolutno vreme koje je proteklo uzmeđu dva merenja. Ako je vreme izvršavanja funkcije kratko, savetuje se da se ono izmeri više puta, pa da se izračuna prosečno utrošeno vreme.
#include <iostream>
#include <chrono>
using namespace std;
void f(void) { ... }
int main() {
const int BROJ_POZIVA = 1000;
auto pocetak = chrono::high_resolution_clock::now();
for (int i = 0; i < BROJ_POZIVA; i++)
f();
auto kraj = chrono::high_resolution_clock::now();
auto trajanje =
chrono::duration_cast<chrono::microseconds>(kraj-pocetak);
cout << "Procena vremena rada jednog poziva funkcije f: "
<< trajanje.count() / BROJ_POZIVA << " mikrosekundi"
<< endl;
return 0;
}Postoje i druge funkcije koje se koriste za merenje utrošenog vremena. U programima na programskom jeziku C++, merenje vremena može da se vrši i korišćenjem funkcija iz jezika C.
Kada se ustanovi da neki veći program zahteva previše vremena, postavlja se pitanje šta je tačno uzrok tome, odnosno koji deo programa troši najviše vremena i treba da se optimizuje. Informacije ovog tipa nam daju profajleri (engl. profiler). Njihova osnovna uloga je da pruže podatke o tome koliko puta je koja funkcija pozvana tokom (nekog konkretnog) izvršavanja, koliko je utrošila vremena i slično. Ukoliko se razvijeni program ne izvršava željeno brzo, potrebno je unaprediti neke njegove delove. Prvi kandidati za izmenu su delovi koji troše najviše vremena.
Za operativni sistem Linux, popularan je sistem valgring koji objedinjuje mnoštvo alatki za dinamičku analizu rada programa, uključujući profajler callgrind. Profajler callgrind se poziva na sledeći način:
valgring --tool=callgrind mojprogram argumenti
gde mojprogram označava izvršivi program koji se analizira, a argumenti njegove argumente (komandne linije). Program callgrind izvršava zadati program mojprogram sa argumentima argumenti i registruje informacije o tome koja funkcija je pozivala koje funkcije (uključujući sistemske funkcije i funkcije iz standardne biblioteke), koliko je koja funkcija utrošila vremena itd. Detaljniji podaci mogu se dobiti ako je program preveden u debag režimu (gcc kompilatorom, debag verzija se dobija korišćenjem opcije -g). Prikupljene informacije program callgrind čuva u datoteci sa imenom, na primer, callgrind.out.4873. Ove podatke može da na pregledan način prikaže, na primer, program kcachegrind:
kcachegrind callgrind.out.4873
Slika 3 ilustruje rad programa kcachegrind. Uvidom u prikazane podatke, programer može da uoči funkcije koje troše najviše vremena i da pokuša da ih unapredi i slično.
Manje precizan, ali dosta brži je profajler gprof.
Za merenje utrošene količine memorije mogu se koristiti programi memcheck i massif, koji su takođe deo sistema valgrind.
Vreme izvršavanja programa ili nekih njegovih delova na nekom konkretnom računaru može i da se proceni, na osnovu analize teksta programa tj. operacija koje program izvršava. Na takvu procene utiču procene vremena izvršavanja pojedačnih operacija, ali i operativni sistema pod kojim računar radi, brzina ulazno-izlaznih hardverskih uređaja (na primer, diska) ako im program pristupa, od jezika i od kompilatora kojim je napravljen izvršivi program za testiranje, itd. Na primer, na jednom današnjem prosečnom računaru, koji radi pod operativnim sistemom Linux, operacija množenja dve vrednosti tipa int troši oko jednu nanosekundu tj. za jednu sekundu se na tom računaru može izvršiti oko milijardu množenja celih brojeva. Procene vremena izvršavanja programa može da pruži grubu sliku o trajanju izvršavanja programa, ali treba ih uzimati sa rezervom, jer možda ne uzimaju u obzir sve procese koji se odigravaju tokom izvršavanja programa, kao ni optimizacije koje su primenjene u kreiranju izvršivog programa. Ipak, procene su jako važne, jer programer i pre pisanja koda treba da ima neki grubi osećaj koliko resursa će program trošiti i da li će odabrani algoritam biti dovoljno efikasan.
Ponašanje programa (pa i količina utrošenih resursa), naravno, zavisi od njegovih ulaznih parametara. Jasno je, na primer, da će program brže izračunati prosečnu ocenu dvadesetak učenika jednog odeljenja, nego prosečnu ocenu nekoliko desetina hiljada učenika koji polažu državnu maturu.
Za veličinu ulaza može se uzeti broj ulaznih elemenata koje treba obraditi (na primer, dužina niza) ili broj bitova potrebnih za zapisivanje ulaza ili vrednost elemenata koje treba obraditi. Da bi se izbegla zabuna, uvek je potrebno eksplicitno navesti u odnosu na koju veličinu ulazne vrednosti se razmatra složenost.
Ponašanje programa često zavisi samo od ukupne količine podataka a ne i od konkretnih vrednosti koje obrađuje. U navedenom primeru, ponašanje programa zavisi samo od broja učenika, a ne i od konkretnih ocena koje su učenici dobili. Zato složenost algoritma često izražavamo u funkciji veličine (dimenzije) njegovih ulaznih parametara, a ne samih vrednosti parametara.
Mnogi algoritmi se ne izvršavaju isto za sve ulaze iste veličine, pa je potrebno naći način za opisivanje efikasnosti algoritma za razne moguće ulaze iste veličine.
Analiza najgoreg slučaja zasniva procenu složenosti algoritma na najgorem slučaju (na slučaju za koji se algoritam najduže izvršava –- u analizi vremenske složenosti, ili na slučaju za koji algoritam koristi najviše memorije –- u analizi prostorne složenosti). Ta procena može da bude varljiva, tj. previše pesimistična. Na primer, ako se program u 99,9% slučajeva izvršava ispod sekunde, dok se samo u 0,1% slučajeva izvršava za 10 sekundi, analiza najgoreg slučaja daje zaključak samo o izvršavanju za 10 sekundi. Sa druge strane, analiza najgoreg slučaja nam daje garancije da ako je program u najgorem slučaju dovoljno efikasan, onda u svim mogućim slučajevima može da se izvrši sa raspoloživim resursima. Analiza najgoreg slučaja je najčešći oblik izražavanja složenosti algoritma i ako se ne naglasi drugačije, pod složenošću algoritma se podrazumeva upravo složenost najgoreg slučaja.
U nekim situacijama moguće je izvršiti analizu prosečnog slučaja i izračunati prosečno vreme izvršavanja algoritma, ali da bi se to uradilo, potrebno je poznavati prostor dopuštenih ulaznih vrednosti i verovatnoću da se svaka dopuštena ulazna vrednost pojavi na ulazu programa. U slučajevima kada je bitna garancija efikasnosti svakog pojedinačnog izvršavanja programa, procena prosečnog slučaja može biti varljiva, previše optimistična, i može da se desi da u nekim situacijama program ne može da se izvrši sa raspoloživim resursima. Na primer, analiza prosečnog slučaja bi za pomenuti program prijavila da se u proseku izvršava ispod jedne sekunde, međutim, za neke ulaze on se može izvršavati i preko deset sekundi.
Analiza najboljeg slučaja je previše optimistična i najčešće nema smisla. Njeno poznavanje može biti korisno kao poznavanje donje granice izvršavanja.
Nekada se analiza vrši tako da se proceni ukupno vreme potrebno da se izvrši određen broj srodnih operacija. Taj oblik analize naziva se amortizovana analiza i u tim situacijama nam nije bitno vreme izvršavanja pojedinačnih operacija, već samo zbirno vreme izvršavanja svih operacija. Ovaj oblik analize je posebno pogodan u slučajevima kada vreme izvršavanja pojedinačnih operacija u nekoj seriji operacija može da varira i kada se dešava da vreme potrošeno za neko izvršavanje operacije omogućava da narednih nekoliko izvršavanja te operacije bude veoma brzo. Tipičan primer je dodavanje elemenata na kraj niza koji se dinamički širi (operacija push_back na vektorima u jeziku C++). Prilikom prvog dodavanja elemenata alocira se određena količina memorije (što je vremenski zahtevno), da bi se u narednim operacijama elementi samo upisivali u ranije alociranu memoriju (što je vremenski veoma efikasno). Kada se alocirani prostor popuni, pre dodavanja elementa potrebno je realocirati memoriju što je ponovo vremenski zahtevno. Ako se obezbedi da se proširivanje niza i realokacija memorije dešavaju dovoljno retko, ovakve strukture podataka imaju nisku amortizovanu složenost.
Vremenska i prostorna složenost algoritma određuju njegovu praktičnu upotrebljivost tj. najveće ulazne vrednosti za koje je moguće da će se algoritam izvršiti u nekom razumnom vremenu.
Neka je funkcija \(T(n)\) predstavlja meru vremena potrebnog za izvršavanje algoritma za ulaz veličine \(n\) (u najgorem slučaju, ako se ne naglasi drugačije). Pod pretpostavkom da se svaka instrukcija izvršava približno isto vreme, ova funkcija može se dobiti i na osnovu funkcije kojom se izražava broj instrukcija koje algoritam izvršava za ulaz veličine \(n\).
U analizi mnogih algoritama, funkcija \(T(n)\) izražava se kao neka kombinacija logaritamske funkcije \(\log(n)\), korene funkcije \(\sqrt{n}\), polinomskih funkcija \(n\), \(n^2\), \(n^3\), \(\ldots\), eksponencijalnih funkcija \(2^n\), \(3^n\), \(\ldots\), faktorijelne funkcije \(n!\) i slično. Njihova osnovna matematička svojstva (pre svega brzina rasta) rezimirani su u dodatku 2.A.1.
Tabela 1 prikazuje potrebno vreme izvršavanja algoritma ako se pretpostavi da jedna instrukcija traje jednu nanosekundu (\(10^{-9}\) sekundi). Ova procena je gruba, ali nije previše pogrešna i daje dobru procenu realnih vremena na današnjim računarima.
| \(n / T(n)\) | \(\log{n}\) | \(\sqrt{n}\) | \(n\) | \(n\log{n}\) | \(n^2\) | \(n^3\) |
|---|---|---|---|---|---|---|
| \(10\) | 0,003 \(\mu\)s | 0,003 \(\mu s\) | 0,01 \(\mu\)s | 0,033 \(\mu\)s | 0,1 \(\mu\)s | 1 s |
| \(100\) | 0,007 \(\mu\)s | 0,010 \(\mu s\) | 0,1 \(\mu\)s | 0,644 \(\mu\)s | 10 \(\mu\)s | 1 ms |
| \(1\,000\) | 0,010 \(\mu\)s | 0,032 \(\mu s\) | 1,0 \(\mu\)s | 9,966 \(\mu\)s | 1 ms | 1 s |
| \(10\,000\) | 0,013 \(\mu\)s | 0,1 \(\mu s\) | 10 \(\mu\)s | 130 \(\mu\)s | 0,1 s | 16,7 min |
| \(100\,000\) | 0,017 \(\mu\)s | 0,316 \(\mu s\) | 100 \(\mu\)s | 1,67 ms | 10 s | 11,57 dan |
| \(1\,000\,000\) | 0,020 \(\mu\)s | 1 \(\mu s\) | 1 ms | 19,93 ms | 16,7 min | 31,7 god |
| \(10\,000\,000\) | 0,023 \(\mu\)s | 3,16 \(\mu s\) | 10 ms | 0,23 s | 1,16 dan | \(3\times 10^5\) god |
| \(100\,000\,000\) | 0,027 \(\mu\)s | 10 \(\mu s\) | 0,1 s | 2,66 s | 115,7 dan | |
| \(1\,000\,000\,000\) | 0,030 \(\mu\)s | 31,62 \(\mu s\) | 1 s | 29,9 s | 31,7 god |
U narednom primeru je ilustrovano kako su vrednosti u ovoj tabeli izračunate.
Primer 2.2.1. Neka je \(n=10\,000\) i \(T(n)=n^2\). Broj izvršenih instrukcija je onda \(T(n)=T(10\,000)=10\,000^2=(10^4)^2 = 10^8\), a vreme je \(10^8 \cdot 10^{-9}\mathrm{s} = 0,1 \mathrm{s}\).
Neka je \(n=1\,000\,000=10^6\) i \(T(n)=n\log_2{n}\). Važi da je \(\log_2(10^6) = 2\log_2(10^3) \approx 20\) (jer je \(2^{10}=1024\approx 1000\)). Zato je \(T(n)=10^6\cdot 20 = 2\cdot 10^7\), a vreme je približno jednako \(2\cdot 10^7\cdot 10^{-9}\mathrm{s} =20\cdot 10^{-3} s =20 \mathrm{ms}\).
Algoritmi čija je složenost odozdo ograničena eksponencijalnom ili faktorijelskom funkcijom se smatraju neefikasnim.
| \(n / T(n)\) | \(2^n\) | \(n!\) |
|---|---|---|
| 10 | 1 \(\mu\)s | 3,63 ms |
| 20 | 1 \(ms\) | 77,1 god |
| 30 | 1 \(s\) | \(8,4\times 10^{15}\) god |
| 40 | 18,3 min | |
| 50 | 13 dan | |
| 100 | \(4 \times 10^{13}\) god |
Možemo postaviti i pitanje koja dimenzija ulaza se otprilike može obraditi za određeno vreme. Odgovor je dat u narednoj tabeli.
| \(t\) | \(n\) | \(n\log{n}\) | \(n^2\) | \(n^3\) | \(2^n\) | \(n!\) |
|---|---|---|---|---|---|---|
| 1 ms | \(10^6\) | \(63\,000\) | \(1\,000\) | \(100\) | \(20\) | \(9\) |
| 10 ms | \(10\cdot 10^6\) | \(530\,000\) | \(3\,200\) | \(215\) | \(23\) | \(10\) |
| 100 ms | \(100\cdot 10^6\) | \(4,5\cdot 10^6\) | \(10\,000\) | \(465\) | \(27\) | \(11\) |
| 1 s | \(10^9\) | \(40\cdot 10^6\) | \(32\,000\) | \(1\,000\) | \(30\) | \(12\) |
| 1 min | \(60\cdot 10^{9}\) | \(1,9\cdot 10^9\) | \(245\,000\) | \(3\,900\) | \(36\) | \(14\) |
Pokušajmo sada da podatke iz datih tabela predstavimo grafički (slika 4). Usled jako velike razlike u brzinama rasta analiziraćemo samo “susedne” funkcije.
Na prvom grafiku na slici 4 prikazan je odnos vremena izvršavanja eksponencijalnih i polinomskih algoritama. Već za dimenziju 30 eksponencijalni algoritam zahteva oko jedne sekunde, dok je vreme izvršavanja algoritama polinomske složenosti praktično zanemarivo (čak i u slučaju polinoma većeg stepena, poput \(n^3\)).
Na drugom grafiku prikazan je odnos brzina rasta polinomskih algoritama. Povećanjem stepena prati jako veliki porast vremena. Algoritam koji zahteva \(n^3\) instrukcija je mnogo sporiji nego onaj koji zahteva \(n^2\) instrukcija (kubnom je već za problem dimenzije oko \(1\,000\) potrebno oko jedne sekunde, dok kvadratni i linearni na tim dimenzijama posao obavljaju praktično momentalno).
Na trećem grafiku prikazan je odnos tri funkcije veoma česte u analizi algoritama: \(n^2\), \(n \log{n}\) i \(n\). Sa grafika se može uočiti da na dimenzijama na kojima su kvadratnom algoritmu potrebne već sekunde, nema velike razlike između algoritama kojima je potrebno \(n \log{n}\) i \(n\) instrukcija – oba skoro trenutno završavaju posao.
Da bi se razlika između takvih algoritama opazila, potrebno je da se dimenzija ulaza znatno poveća, što je i prikazano na četvrtom grafiku. Tek kada dimenzija ulaza dostigne milione, vidi se da je algoritam koji zahteva \(n \log{n}\) instrukcija nešto sporiji. Sa grafika se vidi da svojim oblikom ta funkcija jako liči na linearnu (otuda i naziv “kvazilinearna” funkcija). Sa grafika se može videti i da razlika između linearne i kvazilinearne funkcije nije “drastična”, jer se povećavanjem konstantnog faktora uz linearnu funkciju (faktora \(25\) na ovom grafiku) može desiti da na ulazima razmatrane dimenzije broj koraka bude veći nego kod osnovne kvazilinearne funkcije.
Na petom grafiku se vidi da je vreme izvršavanja algoritama kod kojih broj koraka logaritamski zavisi od dimenzije ulaza praktično zanemarivo (čak i za ogromne ulaze od milijardu elemenata). Treba imati na umu da je samo za učitavanje tolikog ulaza potrebno linearno vreme, pa prednost algoritama logaritamske složenosti dolazi tek kod problema kod kojih se nakon učitavanja podaci obrađuju veliki broj puta ili kod algoritama kod kojih nema potrebe za učitavanjem svih podataka.
Zaključak koji sledi iz proučavanja prikazanih grafika je da izmena algoritma takva da se broj koraka umesto nekom funkcijom iz našeg razmatranog niza funkcija izražava prethodnom u tom nizu, donosi drastično smanjenje vremena izvršavanja i mogućnost obrade mnogo većih ulaza. Izuzetak delom predstavljaju funkcije \(n \log{n}\) i \(n\), koje su veoma bliske i njihova razlika dolazi do izražaja tek kod jako velikih ulaza (ovo je jasno kada se pogleda količnik svake dve susedne funkcije – kod ove dve funkcije on je ubedljivo najmanji).
Prirodno se postavlja pitanje šta ako funkcija \(T(n)\) koja određuje zavisnost između broja potrebnih koraka tj. vremena izračunavanja i dimenzije ulaza nije ovako jednostavna.
Primer 2.2.2. Na primer, neka je \(T(n)=2n^2 + 10n + 8\)? Koliko je vreme potrebno za \(n=10^5\)? Broj potrebnih koraka je \(2\cdot (10^5)^2 + 10\cdot 10^5 + 8\), a potrebno vreme je \(2\cdot 10^{10}\cdot 10^{-9}\mathrm{s} + 10 \cdot 10^5\cdot 10^{-9}\mathrm{s} + 8\cdot 10^{-9}\mathrm{s} = 20\mathrm{s} + 1\mathrm{ms} + 8\mathrm{ns} \approx 20\mathrm{s}\). Dakle, faktor \(2n^2\) daje vreme \(20\mathrm{s}\), faktor \(10n\) daje vreme \(1\mathrm{ms}\), a faktor \(8\) daje vreme \(8\mathrm{ns}\). Očigledno je da je udeo vremena koje dolazi od članova \(10n\) i \(8\) zanemariv u ukupnom zbiru. Nema, dakle, za velike vrednosti \(n\) nikakve značajne razlike između funkcija \(T(n)=2n^2\), \(T(n)=2n^2+10n+8\), pa čak ni \(T(n) = 2n^2 + 1000n + 5000\).
Dakle, vreme izvršavanja algoritma je za velike ulaze praktično potpuno određeno dominantnim članom u funkciji koja opisuje zavisnost broja koraka od dimenzije ulaza.
Još jedno pitanje koje se nameće je koliko je značajan vodeći koeficijent uz taj dominantni član.
Primer 2.2.3. Videli smo da nema praktično nikakve razlike između \(2n^2 + 10n + 8\) i \(2n^2\). Između \(n^2\), \(2n^2\) i \(5n^2\) razlike ima, ali je ona mnogo manje značajna od razlike između, na primer, \(n^2\) i \(1000n\). Naime, već za \(n > 1000\) algoritam koji zahteva \(n^2\) koraka će biti sporiji od onog koji zahteva \(1000 n\) koraka i ta razlika će se povećavati sa porastom \(n\). Za \(n=10^6\), prvi algoritam će biti 1000 puta sporiji nego drugi drugi.
Dakle, red veličine vodećeg člana je mnogo značajniji za opis efikasnosti (za velike vrednosti \(n\)) nego što je koeficijent uz vodeći član. Razlika između, na primer, \(2n^2\) i \(5n^2\) se može nadomestiti nekim manjim optimizacijama ili boljim hardverom, dok se razlika između \(n^2\) i \(n\) ne može nikako nadomestiti osim zamenom algoritma.
Videli smo da nam je prilikom analize složenosti algoritama potrebno da grubo procenimo brzinu rasta funkcija koje opisuju zavisnost potrebnog vremena i memorije u odnosu na veličinu ulaza, tj. samo da odredimo dominantni član te funkcije, zanemarujući ostale članove i koeficijent uz dominantni član. Takva gruba procena nam može dati informaciju o tome da li se za neku veličinu ulaza vreme meri milisekundama, sekundama, satima, danima, godinama itd. Matematičke oznake \(O\), \(\Omega\) i \(\Theta\) koriste se da bi se opisala brzina rasta funkcija2.
Razmotrimo kako možemo definisati pojam \(f(n)=O(g(n))\). Želimo da iskažemo da će počevši od neke veličine ulaza vrednosti funkcije \(f\) biti manje od vrednosti funkcije \(g\). Pošto želimo da zanemarimo vrednost vodećeg koeficijenta ispred dominantnog člana, dopustićemo da se funkcija \(g\) skalira proizvoljnom konstantnom \(c\) tj. da se dopusti da vrednosti funkcije \(f\) budu manje od vrednosti funkcije \(c\cdot g\). Takođe, pošto nas odnos funkcija \(f\) i \(c\cdot g\) zanima samo za velike vrednosti \(n\), zahtevaćemo da važi \(f(n) \leq c \cdot g(n)\) za dovoljno velike vrednosti \(n\), tj. za svako \(n\) veće od neke proizvoljne vrednosti \(n_0\). Dakle, pojam \(f(n)=O(g(n))\) se formalno može definisati na sledeći način.
Definicija 2.2.1. Ako postoje pozitivna realna konstanta \(c\) i prirodan broj \(n_0\) takvi da za funkcije \(f\) i \(g\) nad prirodnim brojevima važi
\[f(n) \leq c \cdot g(n),\]
za svaki prirodan broj \(n\) veći od \(n_0\) onda pišemo \(f(n)=O(g(n))\) i čitamo “\(f\) je veliko o od \(g\)”.
Naglasimo da \(O(g(n))\) ne označava neku konkretnu funkciju, već klasu funkcija i uobičajeni zapis \(f(n)=O(g(n))\) zapravo znači \(f(n) \in O(g(n))\). Pored toga, kako \(O\) predstavlja relaciju, odnos između dve zadate funkcije \(f\) i \(g\), a ne odnos između njihovih konkretnih vrednosti, pod zapisom \(f(n) \in O(g(n))\), zapravo se misli \(f \in O(g)\) (jer su \(f\) i \(g\) funkcije, a \(f(n)\) i \(g(n)\) njihove vrednosti).
Definicija 2.2.2. Ako je \(T(n)\) vreme izvršavanja algoritma \(A\) (čiji ulaz karakteriše prirodan broj \(n\)) i ako važi \(T(n)=O(f(n))\), onda kažemo da je algoritam \(A\) složenosti ili reda \(O(f(n))\) ili da algoritam \(A\) pripada klasi \(O(f(n))\).
Primer 2.2.4. Može se dokazati da važi:
Teorema 2.2.1. Relacija \(O\) ima sledeća svojstva.
Ako su \(a\) i \(b\) realni brojevi i \(a>0\), onda važi \(a f(n)+b = O(f(n))\) (tj. multiplikativne i aditivne konstante ne utiču na klasu kojoj funkcija pripada).
Ako važi \(f_1(n) = O(g_1(n) )\) i \(f_2(n) = O(g_2(n) )\), onda važi i \(f_1(n) +f_2(n) = O(g_1(n) +g_2(n) )\) i \(f_1(n) \cdot f_2(n) = O(g_1(n) \cdot g_2(n) )\).
Relacije \(\Omega\) i \(\Theta\) se definišu slično relaciji \(O\).
Definicija 2.2.3. Ako postoje pozitivna realna konstanta \(c\) i prirodan broj \(n_0\) takvi da za funkcije \(f\) i \(g\) nad prirodnim brojevima važi
\[c \cdot g(n) \leq f(n),\]
za svaki prirodan broj \(n\) veći od \(n_0\), onda pišemo \(f(n)=\Omega(g(n))\) i čitamo “\(f\) je veliko omega od \(g\)”.
Definicija 2.2.4. Ako postoje pozitivne realne konstante \(c_1\) i \(c_2\) i prirodan broj \(n_0\) takvi da za funkcije \(f\) i \(g\) nad prirodnim brojevima važi
\[c_1 \cdot g(n) \leq f(n) \leq c_2 \cdot g(n),\]
za svaki prirodan broj \(n\) veći od \(n_0\), onda pišemo \(f(n)=\Theta(g(n))\) i čitamo “\(f\) je veliko teta od \(g\)”.
Analogno definiciji 2.2.2 definiše se kada algoritam \(A\) pripada klasi \(\Omega(g(n))\) i kada pripada klasi \(\Theta(g(n))\). Složenost algoritama najčešće se izražava u terminima \(O\) (što važi i za nastavak ove knjige).
Pojmovi veliko o (\(O\)), veliko omega (\(\Omega\)) i veliko teta (\(\Theta\)) ilustrovani su na slici 5.
Primer 2.2.5. Može se dokazati da važi:
\(5 \cdot 2^n+9 = \Theta(2^n)\)
Za \(c_1=5\), važi \(c_1 \cdot 2^n \leq 5 \cdot 2^n+9\) za sve vrednosti \(n\) veće od \(0\). Za \(c_2=6\), važi \(5 \cdot 2^n+9 \leq c_2 2^n\) za sve vrednosti \(n\) veće od \(3\). Iz navedena dva tvrđenja sledi zadato tvrđenje.
\(2^n+2^n n = \Theta(2^n n)\)
Za \(c_1=1\), važi \(c_1 \cdot 2^n n \leq 2^n+2^n n\) za sve vrednosti \(n\) veće od \(0\). Za \(c_2=2\), važi \(2^n+2^n n \leq c_2 2^n n\) za sve vrednosti \(n\) veće od \(0\). Iz navedena dva tvrđenja sledi zadato tvrđenje.
Teorema 2.2.2. Relacije \(O\), \(\Omega\) i \(\Theta\) imaju sledeća svojstva.
Informacija o složenosti algoritma u terminima \(\Theta\) (koja daje i gornju i donju granicu) preciznija je nego informacija u terminima \(O\) (koja daje samo gornju granicu) ili informacija u terminima \(\Omega\) (koja daje samo donju granicu). Međutim, obično je složenost algoritma jednostavnije iskazati u terminima \(O\) nego u terminima \(\Theta\). Štaviše, za neke algoritme složenost se ne može lako iskazati u terminima \(\Theta\). Na primer, ako za neke ulaze algoritam troši \(n\), a za neke \(n^2\) vremenskih jedinica, za taj algoritam se ne može reći ni da je reda \(\Theta(n)\) ni reda \(\Theta(n^2)\), ali jeste reda \(O(n^2)\) (pa i, na primer, reda \(O(n^3)\)). Kada se kaže da algoritam pripada klasi \(O(g(n))\) obično se podrazumeva da je \(g\) najmanja takva klasa (ili makar — najmanja za koju se to može dokazati). I \(O\) i \(\Theta\) notacija se koriste i u analizi najgoreg slučaja i u analizi prosečnog slučaja.
Složenost algoritama u terminima \(\Omega\) razmatra se ređe nego složenost u terminima \(\Theta\) i \(O\), ali ponekad takođe može da bude veoma važna. Složenost u terminima \(O\) daje gornju granicu za neku funkciju, a složenost u terminima \(\Omega\) daje donju granicu. To se može razumeti i ovako: složenost u terminima \(O\) govori nam koliko je neki algoritam dobar (“asimptotski nije lošiji nego…”), a složenost u terminima \(\Omega\) govori nam koliko je neki algoritam loš (“asimptotski nije bolji nego…”). Na primer, može se pokazati da je prosečno vreme izvršavanja nekog algoritma za sortiranje reda \(\Omega(n^2)\) i to govori da je taj algoritam loš (jer postoje algoritmi čije vreme izvršavanje pripada klasi \(O(n \log n)\).
Lako se dokazuje da funkcija koja je konstantna (koliko god da je ta konstanta velika) pripada klasama \(O(1)\), \(\Omega(1)\) i \(\Theta(1)\). Štaviše, svaka funkcija koja je ograničena odozgo nekom konstantom pripada klasama \(O(1)\) i \(\Theta(1)\).
Za algoritme složenosti \(O(1)\) kažemo da imaju konstantnu složenost, za algoritme složenosti \(O(n)\) kažemo da imaju linearnu, za \(O(n\log{n})\) da imaju kvazilinearnu, za \(O(n^2)\) kvadratnu, za \(O(n^3)\) kubnu, za \(O(n^k)\) za neko \(k\) polinomsku (negde se kaže i polinomijalnu), za \(O(a^n)\) za neko \(a\) eksponencijalnu, a za \(O(\log n)\) logaritamsku složenost.
Priroda parametra klase složenosti zavisi od samog algoritma. Složenost izračunavanja neke funkcije može da zavisi i od više parametara: na primer, klasa \(O(n)\) ima parametar \(n\), dok klasa \(O(2^{m+k})\) ima parametre \(m\) i \(k\). Na primer, algoritam koji za \(n\) ulaznih tačaka proverava da li pripadaju unutrašnjosti nekog od \(m\) zadatih trouglova, koji kombinuje svaku tačku sa svakim trouglom, ima složenost \(O(mn)\). Složenost funkcije koja sabira dva broja fiksne širine je konstantna tj. pripada klasi \(O(1)\), a brojeva proizvoljne širine je \(O(m+n)\), gde je \(m\) broj cifara prvog, a \(n\) broj cifara drugog broja. Pošto broj cifara broja odgovara veličini ulaza (tj. broju bitova potrebnih za zapis), složenost sabiranja je linearna u odnosu na broj bitova potrebnih za zapis ulaza. Sa druge strane, ako se složenost izrazi u odnosu na vrednosti brojeva koji se sabiraju, ona će biti logaritamska (jer broj cifara logaritamski zavisi od veličine brojeva). Kao što je već rečeno, potrebno je uvek eksplicitno navesti u odnosu na koju veličinu ili koje veličine se razmatra složenost algoritma.
Složenost izračunavanja je izuzetno važna i iz praktične i iz teorijske perspektive. Klasa složenosti \(P\) je klasa problema za koje postoje algoritmi koji su polinomske složenosti (u odnosu na ulaznu veličinu). Problem SAT (od engleskog satisfiability) je problem ispitivanja zadovoljivosti iskazne formule u konjunktivnoj normalnoj formi — za ulaznu formulu treba dati odgovor da ako je formula zadovoljiva, a odgovor ne inače. Trenutno nije poznato da li za ovaj problem postoji rešenje koje radi u polinomskom vremenu u odnosu na dužinu zadate formule. Nijedan trenutno poznat algoritam za SAT nema polinomsku složenost, svi imaju eksponencijalnu složenost. Pitanje da li SAT pripada klasi \(P\) jedno je od najvažnijih otvorenih pitanja u računarstvu. Pored klase \(P\), izučavaju se i mnoge druge klase problema i algoritama na osnovu njihove prostorne i vremenske složenosti.
Određivanje (vremenske i prostorne) složenosti algoritama zasniva se na određivanju funkcije \(T(n)\) tj. određivanje tačnog ili približnog broja instrukcija koje se izvršavaju i memorijskih jedinica koje se koriste. Tačno određivanje tih vrednosti najčešće je veoma teško ili nemoguće, te se obično koriste razna pojednostavljivanja. Na primer, često se smatra da sve pojedinačne instrukcije (osim poziva funkcija) troše jednako vremena. Ono što je važno je da takva pojednostavljivanja ne utiču na klasu složenosti kojoj algoritam pripada (jer, kao što je rečeno, konstantni aditivni i multiplikativni faktori ne utiču na red algoritma).
Ukoliko se deo programa sastoji od nekoliko instrukcija bez grananja i petlji, onda se procenjuje da je njegovo vreme izvršavanja uvek isto, konstantno, te da pripada klasi \(O(1)\).
Ukoliko program ima dva dela, vremenske složenosti3 \(O(f)\) i \(O(g)\), koji se izvršavaju jedan za drugim, ukupna složenost je4 \(O(f+g)\).
To važi i u slučaju kada se u tim delovima javljaju rekurzivni pozivi (tada, na primer, vremenska složenost izražena u terminima vrednosti \(f(n)\) može da zavisi od vremenske složenosti izražene u terminima vrednosti \(f(n-1)\)), ali tada efektivno izračunavanje složenosti zahteva korišćenje dodatnih tehnika (videti poglavlje 2.2.3).
Ukoliko deo programa sadrži jedno grananje i ukoliko vreme izvršavanja jedne grane pripada klasi \(O(f)\) a druge grane pripada klasi \(O(g)\), onda je ukupno vreme izvršavanja tog dela programa ograničeno vremenom koje zahteva složenija grana, pa pripada klasi \(O(\max(f, g))\), a ona je jednaka klasi \(O(f + g)\).
Ukoliko deo programa sadrži petlju koja se izvršava \(n\) puta, a vreme izvršavanja tela petlje je konstantno, onda ukupno vreme izvršavanja tog dela programa pripada klasi \(O(n)\).
Ukoliko deo programa sadrži petlju koja se izvršava za vrednosti \(i\) od \(1\) do \(n\), a vreme izvršavanja tela petlje je \(O(f(i))\), onda ukupno vreme izvršavanja tog dela programa pripada klasi \(O(f(1)+f(2)+\ldots+f(n))\).
Ukoliko deo programa sadrži dvostruku petlju – jednu koja se izvršava \(m\) puta i, unutar nje, drugu koja se izvršava \(n\) puta i ukoliko je vreme izvršavanja tela unutrašnje petlje konstantno, onda ukupno vreme izvršavanja tog dela programa pripada klasi \(O(m \cdot n)\). Ova pravila mogu se dalje uopštiti.
Analogno se računa vremenska složenost za druge vrste kombinovanja linearnog koda, grananja i petlji.
Analiza prostorne složenosti se vrši slično.
Ukoliko deo programa ne sadrži pozive funkcija, dinamičku alokaciju, niti deklaracije objekata čija veličina zavisi od nekih parametera, onda je prostorna složenost tog dela programa konstanta tj. pripada klasi \(O(1)\).
Ukoliko neki deo programa vrši dinamičku alokaciju nekih \(n\) objekata veličine \(O(1)\) – onda to doprinosi njegovoj prostornoj složenosti \(O(n)\).
Ukoliko program ima dva dela, prostorne složenosti \(O(f)\) i \(O(g)\), koji se izvršavaju jedan za drugim, ukupna složenost je \(O(f+g)\).5
Ukoliko se u programu javljaju pozivi funkcija, svaki poziv zauzima neki fiksni prostor na programskom steku (veličina tog prostora može biti ograničena jednom konstantom zajedničkom za sve funkcije) kao i dodatni prostor koji zauzimaju lokalne promenljive te funkcije (koje zauzimaju prostor na pozivnom steku ili su delom, kao na primer, elementi vektora, smešteni u hipu).
Ukoliko se javljaju rekurzivni pozivi, onda u prostornu složenost ulazi maksimalni broj stek okvira koji se mogu naći na programskom steku tokom izvršavanja i čija je veličina konstantna,6 ali i elementi lokalnih promenljivih koji se čuvaju u hip segmentu.
Ukoliko deo programa prostorne složenosti \(O(f)\) poziva funkciju prostorne složenosti \(O(g)\), onda ukupna prostorna složenost tog dela programa pripada klasi \(O(f + g)\). Analogno se računa prostorna složenost za druge vrste kombinovanja koda.
Prikažimo sada kroz nekoliko primera analizu složenosti iterativno implementiranih algoritama. Da bi mogla da se analizira složenost programa potrebno je vladati određenim matematičkim aparatom (na primer, izračunavanjem ili procenom određenih suma, postavljanjem i rešavanjem rekurentnih jednačina i slično). Neke matematičke tehnike koje su potrebne za analizu složenosti rezimirane su u dodatku 2.A.
Primer 2.2.6. Izračunajmo vremensku složenost naredne funkcije koja ispisuje trougaoni deo tablice množenja:
void mnozenje(int n)
{
int i, j;
if (n == 0)
return;
else {
for (i = 1; i <= n; i++) {
for (j = i; j <= n; j++)
cout << i << "*" << j << " = " << i*j << "\t";
cout << endl;
}
}
}Za n jednako \(5\), funkcija daje izlaz:
1*1 = 1 1*2 = 2 1*3 = 3 1*4 = 4 1*5 = 5 2*2 = 4 2*3 = 6 2*4 = 8 2*5 = 10 3*3 = 9 3*4 = 12 3*5 = 15 4*4 = 16 4*5 = 20 5*5 = 25
Smatraćemo da se telo unutrašnje petlje u else grani izvršava konstantno vreme \(c\). Unutrašnja petlja ima \(n-i+1\) iteracija, te je njeno vreme izvršavanja \((n-i+1)c\). Spoljašnja petlja ima \(n\) iteracija, a \(i\)-ta iteracija ima vreme izvršavanja \((n-i+1)c\). Ukupno vreme izvršavanja spoljašnje petlje je
\[\sum_{i=1}^n (n-i+1)c = \sum_{i=1}^n ic = \frac{n(n+1)c}{2}.\]
Grana if izvršava se konstantno vreme \(c'\), pa je ukupna složenost funkcije mnozenje \(O\left(c' + \frac{n(n+1)c}{2}\right) = O(n(n+1)) = O(n^2)\).
Funkcija mnozenje nema poziva drugih funkcija i ne koristi dinamičku alokaciju, niti objekte čija veličina zavisi od ulaznih parametara, te je njena prostorna složenost konstantna, tj. pripada redu \(O(1)\).
U narednim primerima ćemo se potruditi da pokrijemo oblike petlji koji se javljaju u velikom broju konkretnih algoritama i rešenja konkretnih zadataka. U primerima petlji koji slede, pretpostavlja se da kôd u telu petlji koji nije prikazan ne utiče na brojačke promenljive i ne menja granice petlji. Za razliku od prethodnog zadatka nećemo detaljno izračunavati broj instrukcija, već ćemo ga samo procenjivati na osnovu oblika petlji.
Primer 2.2.7. Razmotrimo nekoliko čestih oblika petlje for.
for (int i = 0; i < n; i++)
// kod slozenosti O(1)Složenost prethodne petlje je \(O(n)\).
for (int i = m; i < n; i++)
// kod slozenosti O(1)Složenost prethodne petlje je \(O(n-m)\).
for (int i = 0; i < n; i += 2)
// kod slozenosti O(1)Složenost prethodne petlje je \(O(n)\). Pošto se petlja izvršava za parne vrednosti brojačke promenljive, telo petlje se izvršava oko \(\frac{n}{2}\) puta i konstantni faktor je \(\frac{1}{2}\), ali je složenost i dalje linearna.
for (int i = 0, j = n-1; i < j; i++, j--)
// kod slozenosti O(1)Složenost prethodne petlje je \(O(n)\). Pokazivači se susreću približno na sredini opsega, a telo petlje se izvršava oko \(\frac{n}{2}\) puta.
Moglo bi se pomisliti da je složenost svake petlje linearna, ali to nije uvek slučaj.
for (int i = 0; i < 10; i++)
// kod slozenosti O(1)Složenost prethodnog koda je \(O(1)\). Iako je prisutna petlja, broj njenih izvršavanja je uvek 10 i ne zavisi ni od jednog parametara, pa ga možemo smatrati malom konstantom.
for (int i = 1; i*i <= n; i++)
// kod slozenosti O(1)Iako sadrži jednu petlju, složenost prethodnog koda nije \(O(n)\), već \(O(\sqrt{n})\). Naime, petlja se izvršava sve dok je \(i^2 \leq n\) tj. dok je \(i \leq \sqrt{n}\).
for (int i = 1; i < n; i *= 2)
// kod slozenosti O(1)Iako prethodni kod sadrži petlju, njegova složenost je \(O(\log{n})\), jer se vrednost promenljive i duplira u svakom koraku, sve dok ne prestigne graničnu vrednost \(n\).
Primer 2.2.8. Razmotrimo sada primere programa u kojima se javlja nekoliko petlji.
for (int i = 0; i < m; i++)
// kod slozenosti O(1)
for (int i = 0; i < n; i++)
// kod slozenosti O(1)Složenost prethodnih petlji je \(O(m+n)\). Naime, telo prve petlja se izvrši \(m\) puta, a zatim telo druge petlje \(n\) puta, pa se tela obe petlje ukupno izvrše \(m+n\) puta.
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
// kod slozenosti O(1)Složenost prethodnih petlji je \(O(n^2)\). Zaista, spoljašnja petlja se izvršava \(n\), a u njenom telu se unutrašnja petlja izvršava \(n\) puta, pa se telo unutrašnje petlje izvrši tačno \(n^2\) puta.
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
// kod slozenosti O(1)Složenost prethodnih petlji je \(O(mn)\). Zaista, spoljašnja petlja se izvršava \(m\), a u njenom telu se unutrašnja petlja izvršava \(n\) puta, pa se telo unutrašnje petlje izvrši tačno \(mn\) puta.
for (int i = 0; i < n; i++)
for (int j = i+1; j < n; j++)
// kod slozenosti O(1)Složenost prethodnih petlji je \(O(n^2)\). Broj izvršavanja tela unutrašnje petlje je \((n-1) + (n-2) + \ldots + 2 + 1\), što je jednako \(\frac{n(n-1)}{2} = \frac{1}{2}n^2 - \frac{1}{2}n\). Konstantni faktor je \(\frac{1}{2}\), ali je složenost kvadratna. Do istog rezultata možemo doći ako shvatimo da u svakom koraku unutrašnje petlje par brojača određuje jednu kombinaciju brojeva od \(0\) do \(n-1\). Zato broj izvršavanja tela odgovara broju dvočlanih kombinacija skupa od \(n\) elemenata, što je jednako \(\binom{n}{2} = \frac{n(n-1)}{2}\).
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
for (int k = 0; k < n; k++)
// kod slozenosti O(1)Složenost prethodnih petlji je prilično očigledno \(O(n^3)\).
for (int i = 0; i < n; i++)
for (int j = i+1; j < n; j++)
for (int k = j+1; k < n; k++)
// kod slozenosti O(1)Složenost prethodnih petlji je \(O(n^3)\). Najlakši način da se ovo zaključi je da se primeti da svakom izvršavanju tela odgovara jedna tročlana kombinacija elemenata skupa \(0\), \(\ldots\), \(n-1\). Pošto tročlanih kombinacija ima \(\binom{n}{3} = \frac{n(n-1)(n-2)}{3\cdot 2 \cdot 1}\), složenost je kubna, a konstantni faktor je \(\frac{1}{6}\).
for (int i = 0; i < n; i++)
for (int j = i+1; j < n; j++)
// kod slozenosti O(1)
for (int i = 0; i < n; i++)
// kod slozenosti O(1)Složenost prethodnih petlji je \(O(n^2)\). Naime, telo ugnežđenih petlji se izvrši \(\frac{n(n-1)}{2}\) puta, a zatim telo druge petlje \(n\) puta, što je zapravo zanemarivo malo u odnosu na broj izvršavanja tela ugnežđenih petlji. Dakle, prvi deo koda dominira vremenom izvršavanja i složenost je \(O(n^2)\).
for (int i = 1; i <= n; i++)
for (int j = 1; j < i; j *= 2)
// kod slozenosti O(1)Složenost prethodnog koda je \(O(n \log{n})\). Složenost unutrašnje petlje, za svako konkretno i je \(O(\log{i})\), pa je ukupna složenost otprilike jednaka \(\log{1} + \log{2} + \ldots + \log{n}\), a za ovo se može pokazati da je \(O(n \log{n})\) (jasno je da je izraz manji ili jednak \(n \log{n}\) jer je svaki sabirak manji ili jednak \(\log{n}\), međutim, može se pokazati i da je zbir veći ili jednak od \(\frac{n}{2}\log{\frac{n}{2}}\) (što je takođe \(\Theta(n \log{n})\)), zanemarivanjem prvih \(\frac{n}{2}\) sabiraka, nakon čega ostaju samo sabirci koji su veći ili jednaki \(\log{\frac{n}{2}}\)).
for (int i = n; i >= 1; i /= 2)
for (int j = 1; j < i; j++)
// kod slozenosti O(1)Složenost prethodnog koda je \(O(n)\). Naime, broj izvršavanja unutrašnje petlje je \(n + \frac{n}{2} + \frac{n}{4} + \ldots\), za šta se lako može pokazati da je odozgo ograničeno sa \(2n\).
int j = 0;
for (int i = 0; i < n; i++) {
while (j < n && P[j]) {
// kod slozenosti O(1)
j++;
}
// kod slozenosti O(1)
}Iako postoje ugnežđene petlje, složenost prethodne petlje je \(O(n)\). Ključni detalj je to što unutrašnja petlja nema inicijalizaciju promenljive j na nulu i brojač j u unutrašnjoj petlji se sve vreme samo uvećava (isto kao i brojač i u spoljašnjoj petlji). Ukupan broj koraka je stoga ograničen sa \(2n\).
int l = 0, d = n-1;
while (l < d) {
do l++; while (l < d && P(a[l]));
do d--; while (l < d && !P(a[d]));
if (l < d)
// kod slozenosti O(1)
}Sličan kôd se, na primer, može sresti u algoritmu particionisanja niza tako da se elementi razdvoje na one koji ne zadovljavaju svojstvo P i na one koji zadovoljavaju svojstvo P. I prethodni algoritam je složenosti \(O(n)\) iako i on sadrži ugnežđene petlje. To ponovo možemo utvrditi amortizovanom analizom (jer ne znamo pojedinačni broj izvršavanja unutrašnjih petlji, ali možemo lako proceniti ukupan broj koraka koji se u njima napravi). Naime, promenljiva l se samo uvećava krenuvši od početka, a d se samo smanjuje krenuvši od kraja niza, dok se ne susretnu, što će se desiti u najviše \(n\) koraka.
Dakle, iako nam u većini slučajeva ugnežđenost petlji opisuje složenost algoritma, treba biti obazriv i kod analizirati pažljivije, da se složenost ne bi precenila.
Često procenu složenosti grubo vršimo tako što analiziramo strukturu petlji u programu, zanemarući ostale operacije (obično za sve sem petlji smatramo da je \(O(1)\)). To može biti prilično varljivo, jer se u kodu mogu pozivati funkcije (bilo korisnički definisane, bilo bibliotečke) koje nisu konstantne složenosti. Još gore, i neki operatori mogu biti nekonstantne složenosti (obično linearne).
string rez = "";
for (char c : s)
rez = c + rez;Iako ima samo jednu petlju, prethodni fragment može biti složenosti \(O(n^2)\), gde je \(n\) dužina niske s. Naime, dodavanje karaktera na početak niske u jeziku C++ može biti linearne složenosti \(O(n)\), gde je \(n\) dužina niske (jer zahteva pomeranje narednih karaktera nadesno).
U narednom primeru analiziramo složenost rekurzivno definisane funkcije (mnogo više reči o ovome biće dato u delu udžbenika posvećenom rekurzivnim pristupima rešavanja problema).
Primer 2.2.9. Izračunajmo vremensku složenost naredne rekurzivne funkcije koja izračunava faktorijel svog argumenta:
unsigned faktorijel(unsigned n)
{
if (n == 0)
return 1;
else
return n * faktorijel(n-1);
}Neka \(T(n)\) označava broj instrukcija koje zahteva poziv funkcije faktorijel za ulaznu vrednost \(n\). Za \(n=0\), važi \(T(n)=a\), gde je \(a\) neka konstanta. Za \(n>0\), važi \(T(n)=b+T(n-1)\), gde je \(b\) neka konstanta (u tom slučaju izvršava se jedno poređenje, jedno oduzimanje, broj instrukcija koje zahteva funkcija faktorijel za argument \(n-1\), jedno množenje i jedna naredba return). Dakle, \(T(n) =b+T(n-1)=b+b+T(n-2)=\ldots=\underbrace{b+b+\ldots+b}_{n}+T(0)=bn + a\) Dakle, navedena funkcija ima linearnu vremensku složenost. Skrenimo pažnju i na to da vrednost faktorijela jako brzo raste i da zato veoma brzo dolazi do prekoračenja.
Razmotrimo i prostornu složenost \(S(n)\) funkcije faktorijel. Jedna instanca funkcije faktorijel zauzima (na programskom steku) konstantan prostor \(c\). Najviše prostora je zauzeto kada se izvršava rekurzivni poziv, te za prostornu složenost važi:
\[S(0) = c\]
\[S(n) = S(n-1) + c\]
odakle se dobija da \(S(n)\) pripada klasi \(O(n)\).
Za izračunavanje složenosti komplikovanijih rekurzivnih funkcija potreban je matematički aparat za rešavanje rekurentnih jednačina, u poglavlju 2.A.3.
Ključni savet za poboljšanje složenosti je to da računar radi samo ono što je neophodno da bi se dobio konačan rezultat. Kada se ta ideja malo detaljnije razradi, dobijamo sledeći niz veoma jednostavnih saveta koji nas često dovode do algoritama manje složenosti:
Ova lista saveta, naravno, nije iscrpna, ali iznenađujuće veliki broj značajnih efikasnih algoritama se suštinski zasniva na primeni baš ovih saveta.
Ukoliko performanse programa nisu zadovoljavajuće, pre bilo čega drugog treba razmotriti zamenu ključnih algoritama – algoritama koji dominantno utiču na složenost. Postoji niz važnih i elementarnih i naprednih tehnika koje mogu pomoći da se snizi složenost algoritama i njima ćemo se baviti u narednim poglavljima.
Ukoliko zamena algoritama efikasnijim ne uspeva tj. ukoliko se smatra da je asimptotsko ponašanje najbolje moguće, preostaje da se pokuša popravljanje efikasnosti snižavanjem konstantnih faktora u funkciji koja opisuje složenost (time se ne menja asimptotsko ponašanje, ali se ponekad može donekle smanjiti ukupno utrošeno vreme – na primer, program se može modifikovati tako da izvršava \(6n+3\) instrukcija umesto \(7n+2\)). Ubrzavanje programa često zahteva specifična rešenja, ali postoje i neke ideje koje su primenljive u velikom broju slučajeva.
Moderni kompilatori omogućavaju dodatno podešavanje za generisanje efikasnijeg koda. Iako značajno poboljšavaju performanse (često konstantno, ali nekada i asimptotski), napredne optimizacije nose određene izazove:
Kompilatori obično imaju mogućnost da se eksplicitno izabere neka tehnika optimizacije ili nivo optimizovanja (što uključuje ili ne uključuje više pojedinačnih tehnika). Na primer, za kompilator gcc nivo optimizacije se bira korišćenjem opcije -O iza koje može biti navedena oznaka stepena optimizacije:
| Opcija | Opis optimizacije |
|---|---|
-O0 |
Podrazumevani režim; koristi samo bazične tehnike bez značajnog uticaja na kod. |
-O1 |
Balansira veličinu i brzinu; izbegava tehnike koje drastično produžavaju kompilaciju. |
-O2 |
Fokus na brzini izvršavanja; ne dozvoljava povećanje memorijskog otiska programa. |
-O3 |
Najagresivnija brzina; dozvoljava veći memorijski prostor zarad boljih performansi. |
-Os |
Optimizacija isključivo za smanjenje veličine izvršive datoteke. |
Moderni kompilatori su, dakle, u stanju da samostalno primene izmene koda slične onima koje ćemo opisati u nastavku. Zato treba imati na umu pre svega opšti duh navedenih primera i način razmišljanja koji ih prati. Pored toga, nije dobro uvek se oslanjati na to da će kompilator sve optimizacije izvršiti automatski. Zadatak programera je da proveri da li se to događa i ako se ne događa, da program samostalno optimizuje, ako je to moguće. Takođe, treba imati u vidu da će se program u nekim situacijama prevoditi na drugoj platformi, pomoću drugačijeg prevodioca, za koji nije sigurno kakve će optimizacije vršiti. Zato, opšti savet može biti da u delovima programa za koje programer očekuje da mogu predstavljati usko grlo, programer od početnih faza piše program tako da izbegne neefikasnosti, ukoliko taj način pisanja programa ne dovodi do komplikovanog i nerazumljivog koda. Nakon inicijalnog razvoja korektnog programa, trebalo bi pažljivo izmeriti vreme izvršavanja programa i njegovih pojedinih delova (profilisanje), utvrditi koji kritični delovi koda nisu automatski optimizovani dovoljno kvalitetno i zatim pokušati njihovu optimizaciju samostalno.
Programeri često pogrešno procenjuju koji delovi programa troše najviše resursa. Neproverene optimizacije mogu nepotrebno iskomplikovati kôd i otežati održavanje, a da pritom ne donesu realno poboljšanje. Zato je ključno:
Uvek se treba fokusirati na delove programa koji zaista troše najviše vremena. Ako je uticaj nekog dela na ukupne performanse zanemarljiv, bolje je da on ostane jednostavan i lako razumljiv.
Čuvene su reči Donalda Knuta: ,,Programeri troše enormne količine vremena razmišljajući ili brinući o brzini nekritičnih delova svojih programa i to zapravo stvara jak negativan uticaj u fazama debagovanja i održavanja. Treba da zaboravimo na male efikasnosti, recimo \(97\%\) vremena dok programiramo: prerana optimizacija je koren svih zala. Ipak, ne treba da propustimo mogućnosti u preostalih kritičnih \(3\%\).``
Prilikom optimizacije programa, ključno je razumeti kolika su realna očekivanja od ubrzanja pojedinačnih delova koda. Amdalov zakon nam pomaže da kvantifikujemo maksimalno moguće ubrzanje celog sistema na osnovu poboljšanja samo jednog njegovog dela.
Pretpostavimo da program ima segment koji možemo tehnički unaprediti. Definišimo sledeće parametre:
Ako je ukupno vreme izvršavanja pre optimizacije \(T\), ono se može predstaviti kao zbir vremena koje troši deo koji se ne menja i deo koji se optimizuje:
\[T = (1 - p)T + pT\]
Nakon primene optimizacije, vreme izvršavanja dela \(p\) se smanjuje za faktor \(s\), pa novo vreme \(T'\) iznosi:
\[T' = (1 - p)T + \frac{pT}{s}\]
Ukupno ubrzanje programa (\(S\)) definiše se kao odnos starog i novog vremena izvršavanja:
\[S = \frac{T}{T'} = \frac{T}{(1 - p)T + \frac{pT}{s}}\]
Skraćivanjem vrednosti \(T\), dobijamo konačnu formulu Amdalovog zakona:
\[S = \frac{1}{(1 - p) + \frac{p}{s}}\]
Da bismo bolje razumeli limite optimizacije, pogledajmo dva scenarija gde određenu funkciju ubrzavamo tačno 10 puta (\(s = 10\)).
Primer 2.3.1. Pretpostavimo da određena funkcija zauzima samo 10% ukupnog vremena izvršavanja programa (\(p = 0,1\)). Ako tu funkciju ubrzamo 10 puta, ukupno ubrzanje će biti:
\[S = \frac{1}{(1 - 0,1) + \frac{0,1}{10}} = \frac{1}{0,9 + 0,01} \approx 1,1\]
Zaključak: Iako smo funkciju ubrzali drastično (10 puta), ceo program je postao brži samo za oko 10%.
Primer 2.3.2. Pretpostavimo da ista ta funkcija zauzima čak 90% vremena izvršavanja (\(p = 0,9\)). Uz isto ubrzanje od 10 puta, rezultat je:
\[S = \frac{1}{(1 - 0,9) + \frac{0,9}{10}} = \frac{1}{0,1 + 0,09} \approx 5,3\]
Zaključak: U ovom slučaju, ubrzanje čitavog programa iznosi oko 5,3 puta. Primetite da čak i kada ubrzamo 10 puta deo koji dominira izvršavanjem, ukupno ubrzanje je daleko manje od 10 puta.
Iz ovih primera možemo izvući neke ključne zaključke.
Primer 2.3.3. Ilustrujmo, na kraju, optimizaciju jednim Lojdovim7 problemom: “Ribolovac je sakupio 1kg crva. Sakupljeni crvi imali su \(1\%\) suve materije i \(99\%\) vode. Sutra, nakon sušenja, crvi su imali \(95\%\) vode u sebi. Kolika je tada bila ukupna masa crva?” Na početku, suva materija činila je 1% od 1kg, tj. 10gr. Sutradan, vode je bilo 19 puta više od suve materije, tj. 190gr, pa je ukupna masa crva bila 200 grama.
Ako bi program činile funkcije \(f\) i \(g\) i ako bi \(f\) pokrivala \(99\%\) a funkcija \(g\) 1% vremena izvršavanja, glavni kandidat za optimizovanje bila bi, naravno, funkcija \(f\). Ukoliko bi njen udeo u konačnom vremenu pao sa \(99\%\) na \(95\%\), onda bi ukupno vreme izvršavanja programa bilo svedeno na samo \(20\%\) početnog.
Identično skupo izračunavanje ne bi trebalo ponavljati. Umesto direktnog pozivanja zahtevnih funkcija više puta, bolje je sačuvati njihove vrednosti u pomoćnim promenljivama.
Primer 2.3.4. Uvođenjem pomoćnih promenljivih u narednom primeru se smanjuje broj poziva trigonometrijskih funkcija (koje se izvršavaju relativno sporo).
// Manje efikasno: cos i sin se racunaju po dva puta
x = x0*cos(0.01) - y0*sin(0.01);
y = x0*sin(0.01) + y0*cos(0.01);
// Efikasnije:
cs = cos(0.01); sn = sin(0.01);
x = x0*cs - y0*sn;
y = x0*sn + y0*cs;Moderni kompilatori (npr. gcc uz -O1) često sami vrše ovu optimizaciju. Međutim, to nije uvek trivijalno jer kompilator mora analizom potvrditi da funkcija nema propratnih efekata i da uvek vraća istu vrednost za isti argument.
Svako izračunavanje čiji se rezultat ne menja tokom iteracija treba izneti ispred petlje.
Primer 2.3.5. Veoma slično prethodnom primeru u narednom kodu je još značajnije izračunavanje vrednosti trigonometrijskih funkcija izdvojiti van petlje i sačuvati u pomoćnim promenljivama.
for (i=0; i < N; i++) {
x = x0*cos(0.01) - y0*sin(0.01);
y = x0*sin(0.01) + y0*cos(0.01);
...
} Ovo je posebno važno kada se radi o funkcijama čija složenost zavisi od veličine podataka.
Primer 2.3.6. U sledećem primeru, pozivanje strlen(s) za C-ovsku niska karatkera unutar uslova petlje drastično narušava performanse:
// Losa praksa: slozenost O(n^2) jer se strlen poziva u
// svakoj iteraciji
for (i = 0; i < strlen(s); i++) { ... }
// Bolja praksa: slozenost O(n)
int len = strlen(s);
for (i = 0; i < len; i++) { ... }
...Pošto strlen ima linearnu složenost \(O(n)\), njenim pozivanjem unutar petlje ukupno vreme izvršavanja postaje kvadratno \(O(n^2)\) (ovo je još jedan primer skrivene složenosti). Ovo je primer optimizacije koja poboljšava asimptotsku složenost programa.
Za iteraciju kroz nisku u jeziku C, najbolje je koristiti proveru terminirajućeg karaktera \0, čime se potpuno izbegava pozivanje funkcije strlen:
for (i = 0; s[i] != '\0'; i++)
if (s[i] == c)
...Ova tehnika podrazumeva zamenu računski zahtevnih („skupih“) operacija matematički ekvivalentnim, ali hardverski „jeftinijim“ operacijama koje se izvršavaju u manjem broju ciklusa procesora. Na primer, ukoliko je moguće dobro je izbegavati skupe trigonometrijske funkcije, korenovanje i slično.
Primer 2.3.7. Čest primer je poređenje rastojanja između tačaka. Umesto direktnog poređenja \(\sqrt{x_1^2 + y_1^2} > \sqrt{x_2^2 + y_2^2}\), daleko je efikasnije porediti kvadrate rastojanja: \(x_1^2 + y_1^2 > x_2^2 + y_2^2\). Time se u potpunosti eliminiše poziv funkcije sqrt, koja je interno složena i zahteva mnogo procesorskog vremena.
Slično, površinu trougla je mnogo bolje računati pomoću vektorskog proizvoda i determinante, nego pomoću Heronovog obrasca (koji uključuje korenovanje).
I operacije nad celim brojevima se mogu oslabiti. Na primer, množenja ili deljenja stepenom dvojke pomoću bitovskog šiftovanja (na primer, x * 8 je isto što i x << 3, što je operacija koju procesor izvršava trenutno). Ipak, pošto kompilatori ovakve transformacije veoma često vrše u procesu optimizacije, ovakvim transformacijama treba pristupiti s rezervom, jer mogu narušiti čitljivost koda bez ikakvog doprinosa na brzinu izvršavanja.
Pored zamene skupih funkcija jefinijim, umesto “većih” tipova dobro je koristiti manje, poželjno celobrojne. Procesori su najbrži kada rade sa celobrojnim vrednostima (int). Prelazak sa decimalnih (double) na celobrojne tipove, gde god logika programa to dozvoljava, donosi značajna ubrzanja. Takođe, manji tipovi podataka bolje koriste keš memoriju, što smanjuje broj sporih pristupa glavnoj memoriji (RAM).
Osnovna ideja pripreme i upotrebe unapred izračunatih vrednosti (koje zovemo i pretprocesiranje, ali se ne sme mešati sa pretprocesiranjem koje vrši kompilator) je prebacivanje tereta izračunavanja iz faze izvršavanja u fazu kompilacije ili inicijalizacije. Ako se u programu često koriste vrednosti iz konačnog i relativno malog skupa, efikasnije je izračunati ih unapred.
Na primer, ako nam je u nekom programu često potrebno da koristimo vrednosti korena brojeva od 1 do 100, umesto da ih stalno iznova izračunamo, možemo ih smestiti u konstantni niz (tabelu) u izvornom kodu i izračunati prilikom inicijalizacije programa. Ovo direktno menja složenu funkciju običnim pristupom memoriji, što je znatno brže. Ovaj pristup je klasičan primer kompromisa između vremena i prostora (engl. time-memory tradeoff). Žrtvujemo malu količinu memorije (prostor za niz) kako bismo drastično uštedeli na vremenu izvršavanja.
U jeziku C++, na primer, koristi se ključna reč constexpr koja primorava kompilator da izračuna vrednost nekog izraza već tokom samog prevođenja programa, tako da izvršivi program već sadrži gotov rezultat.
Izbor programskog jezika je jedna od najvažnijih odluka u fazi dizajna softvera. Taj izbor direktno utiče na balans između brzine razvoja (vreme programera) i brzine izvršavanja (vreme procesora).
Danas se većina aplikacija piše u jezicima visokog nivoa kao što je Python. Idealan je za prototipove, analizu podataka, veštačku inteligenciju i skripte gde je bitno da se kôd napiše brzo i da bude čitljiv. Međutim, Python je interpretiran jezik, što ga čini znatno sporijim od kompiliranih jezika. Međutim, on često koristi biblioteke (poput NumPy ili TensorFlow) koje su interno napisane u C-u, čime se dobija “najbolje od oba sveta”.
Kada su resursi ograničeni ili je brzina kritična, programeri se okreću jezicima C i C++. Koriste se za razvoj operativnih sistema, video-igara, sistema za upravalje bazama podataka i veb-servera. Ovi jezici omogućavaju direktno upravljanje memorijom i blisku interakciju sa hardverom, ali zahtevaju mnogo pažljivije programiranje jer greške često dovode do rušenja celog programa.
Iako se danas teži ka višim nivoima apstrakcije, pitanje jezika u kojem se piše kritični deo koda ostaje relevantno za sistemsko programiranje i razvoj softvera visokih performansi.
Iako savremeni kompilatori za C i C++ generišu izvanredan mašinski kôd koji retko koji čovek može nadmašiti, asembler i dalje ima svoje mesto. Nekada je pisanje kritičnih delova na asembleru bilo standard za izvlačenje maksimuma iz procesora. Danas, zahvaljujući naprednim optimizacijama kompilatora ova praksa se sve ređe koristi. Ipak, asembler ostaje neophodan u sistemskom programiranju, pisanju drajvera ili kada je potrebno iskoristiti specifične vektorske instrukcije procesora (npr. SIMD) koje kompilator možda ne koristi optimalno.
Od kako se hardverski razvoj više ne oslanja na drastično povećanje radne frekvencije jednog jezgra, već na dodavanje novih jezgara, paralelizacija je postala ključna za performanse. Savremeni procesori imaju 4, 8, 16 ili više jezgara. Ako je vaš algoritam sekvencijalan, on koristi samo delić snage računara. Paralelizacija omogućava da se veliki zadatak podeli na manje delove koji se izvršavaju istovremeno. Iako pisanje programa koji se mogu izvršavati na taj način zahteva specifične programerske veštine i poznavanje specijalizovanih biblioteka, ono je sve češće opcija.
Za razliku od nekadašnjih računara, na savremenim računarima memorija obično nije kritični resurs. Optimizacije se obično usredsređuju na štednju vremena ili energije, a ne prostora. Ipak, postoje situacije u kojima je potrebno štedeti memoriju, na primer, onda kada program barata ogromnim količinama podataka, kada je s^am kôd programa veliki i zauzima značajan deo radne memorije (što je danas veoma retko) ili kada se program izvršava na nekom specifičnom uređaju koji ima malo memorije.
Naravno, ključni put ka optimizaciji je ponovo optimizacija asimptotske memorijske složenosti programa tj. zamena algoritama i struktura podataka. Ipak, u nekim slučajevima popravljanje konstantnog faktora može biti značajno (na primer, razlika samo u faktoru 2 može činiti razliku da li će izračunavanje biti uspešno ili neuspešno). Često ušteda memorije zahteva specifična rešenja, ali postoje i neke ideje koje su primenljive u velikom broju slučajeva:
Koristiti najmanje moguće tipove. Za celobrojne podatke, umesto tipa int često je dovoljan tip short ili čak char. Za predstavljanje realnih brojeva, ukoliko preciznost nije kritična, može se, umesto tipa double koristiti tip float. Za predstavljanje logičkih vrednosti dovoljan je jedan bit a više takvih vrednosti može da se čuva u jednom bajtu (i da im se pristupa koristeći bitovske operatore).
Ne čuvati ono što može da se lako izračuna. U prethodnom delu je, u slučaju da je kritična brzina, a ne prostor, dobro da se vrednosti koje se često koriste u programu izračunaju unapred i uključe u izvorni kod programa. Ukoliko je kritična memorija, treba uraditi upravo suprotno i ne čuvati nikakve vrednosti koje se mogu izračunati u fazi izvršavanja.
Smanjenje prostorne složenosti često se postiže povećavanjem vremenske i obratno, ali postoje i mnoge situacije u kojima je dobrim rešenjem moguće popraviti istovremeno i vremensku i prostornu složenosti.
Mikrosekunda je milioniti deo sekunde, tj. hiljaditi deo milisekunde i označava se sa \(\mu s\).↩︎
Pojmovi “veliko o”, “veliko omega” i “veliko teta” mogu da se uvedu i za funkcije nad realnim brojevima, ali za potrebe analize složenosti izračunavanja dovoljne su verzije za funkcije nad prirodnim brojevima.↩︎
Gde su \(f\) i \(g\) funkcije koje zavise od jednog ili više parametara programa.↩︎
Na primer, ako je prvi deo složenosti \(O(n)\) a drugi složenosti \(O(n^2)\), onda je ukupna vremenska složenost \(O(n + n^2)\), što je opet \(O(n^2)\). Tada kažemo da drugi deo programa dominira u vremenu izvršavanja.↩︎
Primetimo da ovo važi i ako prvi deo oslobađa prostor koji je zauzeo. Naime, \(O(f+g)\) daje prostornu složenost u najgorem slučaju koja istovremeno ograničava odozgo i \(O(f)\) i \(O(g)\). U ovakvoj situaciji prostorna složenost ponaša se drugačije od vremenske: ako postoje dva dela programa koja se izvršavaju jedan za drugim, ukupno vreme izvršavanja (ne asimptotsko ograničenje nego konkretno utrošeno vreme) jednako je zbiru dva vremena izvršavanja, a ukupni zauzeti prostor jednak je maksimumu dva zauzeta prostora: jedan deo programa je koristio i oslobodio neki prostor a drugi deo programa je onda delom koristio isti taj prostor (na primer, na programskom steku).↩︎
Treba imati na umu da je veličina stek okvira za svaku funkciju konstanta, ali ona može biti veoma velika, na primer – ako je u funkciji deklarisan niz velike dimenzije. Dodatno, treba imati na umu da stek okviri funkcija zauzimaju prostor na programskom steku, a prostor za njega je obično daleko manji od memorije u ostalim segmentima.↩︎
Samuel Loyd, 1841-1911↩︎