Časovna zahtevnost

Č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:

• f_B - najboljša možnost (best case) ali spodnja meja zahtevnosti (primer že urejene tabele)
• f_W - najslabša možnost (worst case) ali zgornja meja zahtevnosti (primer nasprotno urejene tabele)
• f_E - 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

• prostorska zahtevnost krnekej

Zunanje povezave

• Časovna zahtevnost na MaFiRa