BAZA ZNANJA

Kurs: Strukture podataka i algoritamsko modelovanje

Modul: Algoritamsko modelovanje

Autor:

Naziv jedinice: Efikasnost algoritma

Efikasnost algoritama

Složenost algoritma se razmatra po vremenskoj složenosti, odnosno prema tome koliko vremena je potrebno da se stigne do rezultata i po prostornoj složenosti, odnosno koliko memorije će algoritam da iskoristi prilikom izvršavanja. Cilj svakog programera je da konstruiše algoritam koji je korektan i koji je što efikasniji.
Za potrebe ocene efikasnosti algoritma koristi se RAM model:

• Svaka elementarna operacija traje tačno jedan korak. Elementarne operacije su sabiranje, oduzimanje, poređenje, izjednačavanje, višestruka selekcija.
• Petlje i pozivi potprograma nisu elementarne operacije. One zavise od veličine podataka sa kojima rade i od broja sopstvenih podkoraka.

Pristup memoriji bi bio jedan korak, dok sortiranje niza nije elementarna operacija.
Motiv za traženjem što efikasnijeg algoritma je taj da i najprostiji programi mogu da budu krajnje neefikasni. Primer bi bio množenje dva cela broja. Množenje možemo da shvatimo kao uzastopno sabiranje broja samog sa sobom, određen broj puta. Ako bi ti brojevi bili 7562 i 423 imali bismo, u najboljem slučaju, 423 operacije sabiranja. Ali, ako 423 zapišemo kao 400 + 20 + 3 i pomnožimo delove, pa potom saberemo rezultate, imaćemo daleko manje osnovnih operacija.

7562 * 423  = 7562 * ( 400 + 20 + 3)

= 7562 * 400 + 7562 * 20 + 7562 * 3
= 756200 * 4 + 75620 * 2 + 7562 * 3

Složenost algoritma se opisuje funkcijom koja se zove growth-rate i koja je data na slici 1. Ona je direktno proporcionalna vremenskim zahtevima samog algoritma. Njom se meri vreme izvršavanja za najgori slučaj.

Efikasnost algoritma se meri potrošnjom vremena i prostora. Međutim, kako je u poslednje vreme prostor postao manje bitna stavka, to se sve više okrećemo vremenskoj potrošnji. Vreme izvršavanja zavisi od:

• skupa mašinskih instrukcija računara na kom se algoritam izvršava, odnosno vremena njihovog trajanja u ciklusima
• kvaliteta mašinskog koda generisanog od strane prevodioca
• ulaznih podataka
• vremenske složenosti

Prve dve stavke zavise od samog računara i ne odražavaju suštinu algoritma. Vremenska složenost se meri u odnosu na prebrojani broj upotrebljenih koraka.

Složenost može da bude složenost najboljeg, prosečnog i najgoreg slučaja. Najboljeg jeste mera u odnosu na najmanji broj upotrebljenih koraka za obradu n ulaza. Najgoreg jeste mera u odnosu na najveći broj upotrebljenih koraka za obradu n ulaza, a prosečnog je mera upotrebljenih koraka u normalnom korišćenju algoritma primenjenog na n ulaza.

Veliko O

Prilikom opisa vremenske složenisti koristi se funkcija growth-rate:

Slika 1. Growth-rate funkcija

• O() - čita se veliko O od broja u zagradi, označava vremenske zahteve za najgori slučaj korišćenja proporcionalne broju ulaza zapisanih u zagradi. Taj broj u zagradi označava red vremenske zavisnosti. Na krajevima krivih, koje su prikazane na slici 1., date su najčešće vrednosti koje mogu da se nađu u zagradi funkcije. Što kriva ima strmiji rast, to je algoritam neefikasniji.
• O(n) - čita se veliko O od n, i označava vremensku zahtevnost algoritma za n ulaza. Ovo odgovara pojmu da je za tih n ulaza potrebno n koraka.
• O(n2) - označava da je broj koraka potrebnih za n ulaza oblika an2+bn+c gde konstante ne utiču na red vremenske zavisnosti. Primetite da je red zavisnosti najveći stepen poslednjeg izraza.

Kao što vidimo na sledećoj slici, u zavisnosti od toga da li je kriva oblika log2n, n□, n2 ili 2n i od broja ulaznih vrednosti n=16 ili n=256 u najgorem slučaju bi rešavanje algoritma trajalo milijardama godina.

Slika 2. Vreme izvršavanja dato u zavisnosti od strmine krive u growth-rate funkciji, za različit broj ulaznih vrednosti