Algoritmi

Već smo zaključili da su za rad računara potrebni programi, koji nastaju zahvaljujući posebnoj vrsti aplikacija – programskom softveru. U programski softver spadaju sve aplikacije koje služe za pisanje drugih programa. Ponekad je za to dovoljan najjednostavniji tekst editor, a ponekad su u pitanju veoma složeni softverski paketi.

Najjednostavnije rečeno, algoritam predstavlja neki precizno opisan postupak. Taj postupak je obično svrsishodan, što znači da nas vodi do nekog cilja (rešenja problema) do koga možemo doći praćenjem niza koraka. Tako možemo reći da je algoritam precizno definisan postupak za rešavanje nekog problema u konačnom broju koraka.

U algoritmu koraci moraju biti jasno odvojeni, a sam algoritam mora biti nedvosmislen i mora se završiti posle nekog određenog broja koraka. Za iste početne vrednosti, algoritam uvek daje iste rezultate i primenljiv je za veći broj različitih početnih vrednosti.

Algoritmi su značajni za programiranje iz prostog razloga što sami programi predstavljaju konkretnu realizaciju algoritama na računaru.

Algoritmi mogu biti opisani na razne načine, od kojih su neki više (pseudokod) ili manje (prirodan jezik) formalizovani. Jedan od najpoznatijih i najpreglednijih načina za predstavljanje algoritama je putem algoritamske šeme (blok-dijagrama).

Postoji nekoliko podela algoritama, a najpoznatija je prema načinu izvršavanja koraka. Po njoj, algoritmi mogu biti:

• linijski - algoritmi kod kojih se svaki korak izvršava tačno jedanput;
• razgranati - algoritmi kod kojih se neki koraci mogu izvršiti jednom ili nijednom;
• ciklični - algoritmi kod kojih se neki koraci mogu izvršiti više puta.

Naravno, svaki malo složeniji algoritam u sebe uključuje elemente sva tri tipa.

Treba da znamo da se kvalitet svakog programa, a samim tim i algoritma, ocenjuje po dva osnova, a to su brzina i korišćenje memorije. Iz ranijih tekstova o hardveru, sećamo se da brzina i memorija predstavljaju dva ključna elementa u razvoju računara – procesori postaju sve moćniji i brži, a kapaciteti unutrašnje i spoljne memorije se sve više povećavaju.

To znači da, sa jedne strane, proizvođači hardvera pokušavaju sve više da ubrzaju računare i da im ugrade što je moguće više memorije, dok se, sa druge strane, programeri trude da pišu bolje programe koji će raditi brže i zauzimati manje memorije. Na taj način računari mogu da rade sa većom količinom podataka i time budu upotrebljiviji.

Bolji algoritam je onaj koji je efikasniji po pitanju korišćenja memorije i koji u manjem broju izvršenih koraka dolazi do rezultata.

Kompleksnost algoritma

Programi i algoritmi se obično posmatraju kao niz instrukcija koje za zadati ulaz (početne podatke) kreiraju određeni izlaz (rezultat). Kompleksnost algoritma se procenjuje na osnovu toga kako se povećava broj koraka koji se moraju izvršiti sa povećanjem ulaza. Što je više koraka potrebno da se dođe do rezultata, algoritam će raditi sporije. Tako postoji nekoliko klasa algoritama, od kojih će ovde biti pomenute samo najznačajnije.[1]

• O(1) - bez obzira na ulaz (količinu podataka koji se zadaju na početku), ne menja se broj koraka. Primer predstavlja pretraga preko tzv. heš (hash) tabele (pretraga se obavlja veoma brzo na osnovu posebne funkcije koja izračunava poziciju elementa koji se traži).
• O(n) - linearna kompleksnost, koliko se poveća ulaz, toliko se poveća i broj koraka. Primer bi bilo sabiranje dva broja sa po N cifara.
• O(log n) - dobri algoritmi kod kojih sa povećanjem ulaza dolazi do relativno malog povećanja broja koraka. Primer je binarna pretraga (najbolje je možemo zamisliti kao deljenje intervala prilikom pogađanja brojeva).
• O(n log n) - takođe veoma dobri algoritmi gde se broj koraka ne povećava puno. Jedan od primera je „zavadi pa vladaj“ (divide and conquer) metod, primenjen u quicksort algoritmu za sortiranje podataka.
• O(n²) - algoritmi sa dva koncentrična ciklusa u kojima se obično pojavljuje upoređivanje „svaki sa svakim“. Neki od najpoznatijih algoritama za sortiranje su upravo ovog tipa (bubble sort, shell sort, insertion sort, selection sort...)
• O(2ⁿ) - ovo su obično najgori algoritmi kod kojih se broj koraka drastično povećava sa malim povećanjem ulaznih podataka. Primer su algoritmi tzv. „grube sile“ (brute force), koji obično do rešenja dolaze isprobavanjem svih mogućih kombinacija.