Analiza algoritma predstavlja postupak kojim se predviđa ponаšanje i vrši procena potrebnih resursa
algoritma. Tačno ponašanje algoritma je nemoguće predvideti, zato se za njegovu analizu razmatraju
samo glavne karakteristike, a zanemaruju neki manji faktorisa kojima ćemo se kasnije upoznati.
Osnovni metod koji se pri tome koristi je aproksimacija. Na ovaj način se, iz skupa mogućih algoritama
za rešavanje nekog konkretnog problema, može izdvojiti najefikasniji (ili klasa efikasnih algoritama).
U ovom članku ćemo razmatrati vremensku složenost
algoritma – memorijski zahtevi će biti pomenuti samo ako nisu u nekim "normalnim" granicama.
Većina učenika, neretko i studenata, nije upoznata sa ovim pojmom i njegovom važnošću. Često u toku
takmičenja dobijamo pitanja vezana za ograničenja ulaznih podataka, jer većina takmičara ne razume zašto
su ona bitna. Ideja ovog dokumenta je da takmičarima približi ovaj pojam i njegovu značajnost.
U mnogim knjigama ovoj priči nije posvećeno dovoljno pažnje. Neretko se ovaj pojam uvodi jako formalno
što predstavlja problem čitaocu da razume njegovu suštinu. Akcenat u ovom dokumentu će biti na razmatranju
i analizi konkretnih problema. Razni primeri koje ćemo analizirati će vam pomoći da uočite razlike između
algoritama koji rešavaju isti problem.
Slika 1.Strip o složenosti problema putujućeg trgovca
(preuzeto sa xkcd.com – sajt posvećen stripovima o ljubavi, sarkazmu, matematici i jeziku)
Ukoliko imate komentara ili dodatnih sugestija povodom teksta, nemojte oklevati da se obratite bilo autoru
bilo takmičarskoj komisiji. Takođe ukoliko naiđete na neku grešku, kojih svakako ima, bili bi zahvalni
kada bi ste obavestili autora o istoj.
Preuzmite kompletan članak.