Časovna zahtevnost

Iz Wikipedije, proste enciklopedije
Skoči na: navigacija, iskanje

Časovna zahtevnost je podatek o tem, koliko časa se bo program (oziroma algoritem) pri danih vhodnih podatkih izvajal, preden bo vrnil rešitev. Čas običajno merimo v osnovnih operacijah stroja, ki program izvaja. Časovno zahtevnost podamo kot funkcijo velikosti vhodnih podatkov (npr. velikost tabele). Poznamo tri vrste časovne zahtevnosti:

  • fB - najboljša možnost (best case) ali spodnja meja zahtevnosti (primer že urejene tabele)
  • fW - najslabša možnost (worst case) ali zgornja meja zahtevnosti (primer nasprotno urejene tabele)
  • fE - pričakovana zahtevnost (expected case) pri povprečnih podatkih

Ker je običajno natančno število operacij težko ali nemogoče določiti, uporabimo O-notacijo, ki označuje red rasti problema. Če velikost vhoda označimo z n, c pa je neka konstanta, potem imamo naslednje zahtevnosti, od najugodnejše do najneugodnejše:

Notacija zahtevnost
O(1) konstantna
O(\log n) logaritemska
O(n) linearna
O(n \log n) vmesna
O(n^2) kvadratna
O(n^c), c > 1 polinomska
O(c^n) eksponentna

Glej tudi[uredi | uredi kodo]

Zunanje povezave[uredi | uredi kodo]