Nakon što se upoznamo s nekim programskim jezikom i naučimo ga relativno dobro, teoretski možemo napisati bilo kakvu aplikaciju. Evo primjer: Dolazi do Vas školski kolega i kaže kako ima određene obaveze ali ne zna kako ih rasporediti. Vi naravno, kao vrhunski programer prihvatite ponudu i kažete, eto prijatelju gotov sam za 10 minuta, samo da natipkam to. I super, zaista natipkali ste to, i to radi. Kolega napiše obaveze, označi kada bi koje obaveze mogao obavljati, a program mu izbaci raspored (ili više njih). I tako prođe neko vrijeme, i vidite oglas u kojem piše da se traži honorarni programer koji će napraviti generator rasporeda za jednu poveću tvrtku. Trebalo bi sinkronizirati sve radnike, s time da svaki radnik ponudi svoje vrijeme kada bi htio raditi. Odmah pomislite, pa to sam napravio već za kolegu, samo malo prilagodim aplikaciju, stavim neki super GUI i eto zarade. I eto Vi to napišete, uredite i kreće testiranje. Imate datoteku od 10 ljudi i generira se lijep raspored. Pokažete riješenje upravi, oni sretni jer ste brzo napraviti i odmah Vam daju test datoteku s 200 ljudi (samo 20 puta više) i Vi pokrenete program. U 90% (i više) Vaša aplikacija radi i radi i radi... Što se dogodilo? Problem je što algoritam nije "brz". Pomislite to je zato jer pišem nekom visokom jeziku, ajde da prebacim to u strojni kod. I opet algoritam je spor. Pretpostavimo da algoritam radi tako da isproba sve kombinacije i kao rezultat vrati one dobre. Ovo rješenje je iscrpna pretraga (engl. brute-force). Vremenska složenost je O( n! ). Ok, ali što je vremenska složenost? Za početak budimo neprecizni pa kažemo da je vremenska složenost mjera koja pokazuje kako algoritam "brzo" radi u ovisnosti ulaznih podataka. Prostorna složenost je isto to samo za memoriju.
Na ovom primjeru vidjeli smo da je analiza algoritma bitna. Kada se jamči mali broj ulaznih podataka i najgore rješenje je dobro, ako ono radi u vremenskom ograničenju. Općenito kada se pojava faktorijeli to je jako jako loše, iako ponekad teorijski ne možemo brže. Postoji cijela teorija koja se bavi formalnim opisima složenosti i ima puno lijepe matematike u tome. Sada ćemo se posvetiti načinu na koji se izračunava vremenska i prostorna složenost algoritma. Bez ulaženja u dubinu, prva stvar koja se obično radi s analizom algoritama je "veliko O notacija". Što znači O( n! ) ili pak O( log n ). Ideja je da se traži funkcija koja će reći kako je algoritam brz, tj. koja će reći kako vrijeme izvođenja teoretski ovisi o ulaznim podacima (analogno za memoriju). Ako je vremenska složenost algoritma O( n ), to znači da vrijeme raste linearno u ovisnosti ulaznih podataka. Može biti da je f(n) = 5*n ili f(n) = 10n + 120023, navedene funkcije spadaju u O( n ), pri čemu je f(n) broj operacija koje se obave. Primijetimo da konstante nisu bitne. Zadan je program koji učitava dimenzije matrice i popunjava ih slučajnim brojevima. Koja je vremenska složenost? (neka je n broj redaka i broj stupaca) Imamo dvije for-petlje, jedna unutar druge. Ukupni broj operacija pridjeljivanja je n*n. Vremenska složenost je O( n^2 ). Tvrdim da je vremenska složenost i O( n! ), za navedeni algoritam popunjavanja matrice. Pa kako sad to? Problem je što ne znamo što zapravo veliko O predstavlja. Kratko napisano ali matematički neprecizno, funkcija f pripada O( g(n) ) ako za neki n0 i za neku konstantu c vrijedi da je f(n) = c*g(n). Iz ovoga se vidi da f(n) mora biti nakon nekog n0 pa sve do beskonačnosti manja ili jednaka c*g(n). Ako je f(n) = n^2, tada vrijedi f(n) = c*n!, za neki n0 i c. U praksi je bitno da g(n) bude ona koja je najmanja. Konkretno, najmanja je g(n) = n^2. Veliko O notacija najčešće se koristi kako bi se opisalo ponašanje algoritma za najgori slučaj.
Kako mogu analizirati program? Najjednostavnije je brojati koliko se jednostavnih operacija izvrši. Pod jednostavnim operacijama mislim na one čija je vremenska složenost O( 1 ). Evo primjera:
Kolika je vremenska složenost algoritma za množenje matrica: O( n^3).
Kolika je vremenska složenost algoritma koji traži najveći broj u nizu: O( n ).
Zadani program: ucitaj n, za i = 1 do n: i = i * 10 vremenska složenost je O( log( n ) ).
Memorijske složenost za navedene primjere su redom: O( n^2 ), O( n ), O( 1 ).
Za prvi primjer koristimo matrice i ako je svaka dimenzije n^2, ukupno je to 3*n^2 memorije, što je prema prethodnoj definiciji O( n^2 ). Treći primjer koristi samo jednu varijablu, što znači da korištenje memorije ne ovisi o ulaznom podatku n.
Osim veliko O notacije postoje i druge notacije, koje se koriste (neke više neke manje) ako Vas zanima pogledajte u literaturi koju sam naveo par postova prije.
Nadam se da će ovo biti dovoljno za daljnje razumijevanje jednostavnih analiza koje će biti rađene kod algoritama. Sljedeći korak je master teorem, za kojeg će se samo pokazati kako se računa ali neće biti izvod (barem ne u sklopu ovih tutorial postova). Ali prije toga par jednostavnih ali korisnih algoritama (i struktura podataka)
