Izpitno vprašanje RAČ2PRA 3700

Iz MaFiRaWiki

Vsebina

Vprašanje

Dana sta dva algoritma. Prvi je časovne zahtevnosti O(n), drugi pa O(n2). Kaj lahko pove o času izvajanja algoritmov na istem računalniku na istih problemih?

Odgovor

Podamo primer algoritmov časovnih zahtevnosti O(n) in O(n2):

Algoritem časovne zahtevnosti O(n)

Imamo algoritem, za katerega vemo, da je njegova časovna zahtevnost O(n). Recimo, da se bo naš algoritem izvajal 5 sekund. Algoritem ima lahko tudi konstantni del (nekaj naredi na začetku, potem pa se posveti obdelavi podatkov), ki bo trajal recimo 3 sekunde. Torej naše podatke bo obdeloval 2 sekundi. Ko ga zaženemo na 4x večjih podatkih, bo potreboval 4x2s = 8s, plus 3s, ki ga porabi za konstantni del. Torej, naš algoritem bo, za izvajanje podatkov na 4x večjem problemu, porabil vsega skupaj 8+3 = 11 sekund.

Algoritem časovne zahtevnosti O(n2)

Za algoritem s kvadratno časovno zahtevnostjo je značilno, da čas za obdelavo večjih količin podatkov narašča hitreje od linearnega - če podvojimo količino podatkov, se bo čas obdelave linearnega algoritma približno podvojil, kvadratni algoritem pa bo za obdelavo porabil kar približno štirikrat več časa! Velikokrat se zgodi, da so kvadratni algoritmi za obdelavo manjših količin podatkov hitrejši od linearnih, zato je odločitev, katerega uporabiti v praksi, odvisna od količine podatkov, ki jih z algoritmom nameravamo obdelovati (kdaj je kvadratni algoritem hitrejši lahko preverimo tudi eksperimentalno - z merjenjem časa, ki ga porabi za obdelavo dane količine podatkov).

Osebna orodja