Izpitno vprašanje DIRI2005 3700

Iz MaFiRaWiki

Predmet Dopolnilno izobraževanje iz računalništva in informatike (DIRI)

Vprašanje

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

Odgovor

Časovna zahtevnost algoritma (O) nam pove, kako raste čas (t) v odvisnosti od velikosti problema (n). Slika1 prikazuje razmerje v času delovanja računalnika pri istem problemu z različnim številom podatkov npr. (od 0 do 100) ob uporabi različnih algoritmov O(n) in O(n2).

Levo poravnano drevo
Slika1: Primerjava časovne zahtevnosti algoritmov O(n) in O(n2).

Vidimo lahko, da se pri večanju števila podatkov oz večanju velikosti problema v primeru, ko gre za algoritem s časovno zahtevnostjo O(n), čas povečuje linearno, v drugem primeru pa s kvadratom velikosti problema.

Če imamo le en problem, ne moremo povedati ničesar. Lahko bi bil drugi algoritem v nekem primeru celo dosti hitrejši, vendar pa bi, z naraščanjem velikosti problema, prvi algoritem prej ali slej zagotovo postal hitrejši.

Osebna orodja