U jednom od prethodnih postova, načeli smo temu algoritama i njihove složenosti. Trudićemo se da pristupimo temi sa što manje „matematičkih” detalja, ali neće uvek biti moguće.
Veoma nam je važno da znamo koliko brzo će se naš program odnosno algoritam izvršavati. Jedan od faktora koji utiče na to je hardver na kom se program/algoritam izvršava. Moderniji i moćniji hardver će omogućiti da se program brže izvrši nego na lošijoj platformi. S obzirom da se trudimo da procenimo kvalitet samog algoritma (a s tim i programa baziranim na tom algoritmu), u razmatranjima ćemo se truditi da faktor hardvera neutrališemo i zanemarimo.
Drugi faktor koji utiče na vreme izvršavanja je veličina ulaza. Program će brže obraditi manje podataka nego više. Treći faktor je puka sreća. Na primer, tražimo element u kolekciji i nađemo ga na prvom mestu. Da li to znači da je algoritam toliko efikasan u svim slučajevima? Naravno da ne. Da bi procena bila osnovana, fokusiraćemo se na najgori mogući slučaj jer on određuje gornju granicu vremena izvršavanja.
Da bismo mogli da uporedimo algoritam sa algoritmom i pritom zanemarimo uticaj hardvera, odlučeno je da se za merenje ne koriste vremenske odrednice (sekunde, milisekunde) nego da uzimamo u obzir broj izvršenih operacija kao meru kompleksnosti rešenja. Ipak, često se koristi termin “vreme izvršavanja” bez obzira što ne merimo vreme.
Primer
Objasnićemo ovo na algoritmu maksimuma.
int[] array = {1, 2, 3, 4, 5};
int max = array[0];
for (int i = 0; i < array.length; i++) {
if (max < array[i]) {
max = array[i];
}
}
Za pronalaženje maksimalnog elementa niza potrebno je:
- Dodeliti promenljivoj max vrednosti jednog od elemenata niza. Ovde imamo operaciju pristupa elementu niza i operaciju dodele vrednosti promenljivoj, dakle 2 operacije.
- Potrebno je iterirati kroz elemente niza.
- Svakom elementu treba pristupiti (1 operacija),
- uporediti ga sa dotadašnjim maksimumom (1 operacija)
- Eventualno izmeniti dotadašnji maksimum na novu vrednost (1 operacija)
Ukoliko niz ima 10 elemenata, korake a. b. i c. treba da ponovimo 10 puta.
Koliko je to operacija ukupno:
2 + 10 * (1 + 1 + 1) = 2 + 10 * 3 = 32 operacije
Ako se broj elemenata niza poveća na 20:
2 + 20 * (1 + 1 + 1) = 2 + 20 * 3 = 62 operacije
S obzirom da na ukupan broj operacija utiče jedino broj elemenata niza, možemo uzeti da je u pitanju promenljivi broj n pa na osnovu toga, ukupan broj operacija je:
2 + n * (1 + 1 + 1) = 2 + 3 * n
Generalno govoreći, kod procenjivanja broja operacija nije važno odrediti tačan broj operacija (npr. da li u prvom koraku ima 2 ili 4 operacije) ali je bitno odrediti da li je broj konstantan ili zavisi od veličine ulaza n i na koji način.
U sledećem članku na ovu temu, posvetićemo se veliko O notaciji.
Otkrijte tajne algoritama sa FTN Informatike: Osnove programiranja
Zanima vas kako programi “razmišljaju” i rešavaju probleme? Želite da razumete kako se procenjuje efikasnost algoritama i šta čini dobar kod? Naš kurs „Osnove programiranja“ nudi priliku da se upustite u fascinantan svet informatike i naučite kako da analizirate i konstruišete algoritme efikasno.
Šta možete očekivati?
- Temeljno razumevanje algoritama: Naučite osnove algoritamskog razmišljanja, uključujući procenu vremenske složenosti i Big O notaciju.
- Praktični projekti i vežbe: Primena naučenog kroz zanimljive zadatke i realne projekte.
- Interaktivna predavanja: Rad sa iskusnim predavačima i pristup bogatim online resursima.
- Druženje i timski rad: Saradnja sa drugim studentima na zajedničkim projektima i kodiranjem u paru.
Ovaj kurs je savršen za sve koji počinju svoje putovanje u programiranju, kao i za one koji žele da prodube svoje znanje i veštine. Bez obzira da li ste srednjoškolac, student ili profesionalac koji teži promeni karijere, naš kurs nudi nešto novo i uzbudljivo za svakoga.
