Različni algoritmi za isti problem

Program, funkcija, naravni jezik, psevdokoda in diagram poteka so različni načini za zapis istega algoritma, torej istega postopka za reševanje programerskega problema. Včasih pa lahko problem rešimo na več bistveno različnih načinov, torej z več različnimi smiselnimi algoritmi.

Problem MIN3 smo doslej reševali tako, da smo primerjali prvi dve števili, nato pa manjše od prvih dveh še s tretjim. Po dveh primerjavah smo natančno vedeli, katero število v podani trojici je najmanjše. Lahko pa se »pomikamo« od prvega števila do tretjega in v pomožni spremenljivki naj hranimo doslej najmanjše število. Na ta način dobimo drugačen algoritem:

Kako lahko različne algoritme primerjamo med seboj? Algoritmi, ki ne dajejo pravilnih rezultatov ali pa se pri nekaterih vhodih ne ustavijo, nas običajno ne zanimajo. Pravilne in ustavljive algoritme pa lahko primerjamo po teh kriterijih:

• Poraba časa: Med dvema algoritmoma za podani problem bomo seveda raje izbrali tistega, ki bo za svoje izvajanje z računalnikom pri večini vhodov (ali pa vsaj pri »povprečnem« vhodu) porabil manj časa. Ta kriterij je tako pomemben, da mu namenjamo celotno naslednjo učno enoto.

• Poraba prostora: V računalniku imamo resda na voljo zelo veliko pomnilniškega prostora, vendar pa je ta še vedno omejen. Če obdelujemo velike množice podatkov, moramo paziti, da algoritem ne porabi preveč dodatnega pomnilniškega prostora za svoje izvajanje.
• Razumljivost: Če pri porabi časa ali prostora ni bistvenih razlik, imamo raje algoritme, ki jih lažje razumemo.
• Prilagodljivost: Kako enostavno lahko algoritem prilagodimo tako, da bo deloval tudi za večje ali splošnejše različice problema?

Primerjajmo algoritma za problem MIN3. Kot bomo videli v naslednji učni enoti, lahko porabo časa ocenimo tako, da štejemo osnovne korake izvajanja algoritma; v našem primeru so to medsebojne primerjave dveh števil in prirejanja. Pri obeh algoritmih imamo pri poljubnem vhodu po dve primerjavi: pri prvem algoritmu najprej primerjamo prvo število z drugim, nato pa še manjše od obeh s tretjim, pri drugem algoritmu pa primerjamo najprej drugo, nato pa še tretje število s spremenljivko naj. Pri drugem algoritmu nekaj dodatnega časa vzamejo prirejanja, ki jih je lahko več kot pri prvem. Zaradi hitrosti današnjih računalnikov pa je ta razlika zanemarljiva. Glede porabe prostora sta oba algoritma enakovredna: poleg treh vhodnih spremenljivk uporabljata še spremenljivko naj. Razumljivost je subjektiven kriterij, zato presojo o tem prepuščamo vam, našim bralkam in bralcem. Glede prilagodljivosti pa ima drugi algoritem prednost pred prvim. To boš spoznal(-a) pri reševanju naslednje naloge:

Vaja