Časovna zahtevnost
Iz Wikipedije, proste enciklopedije
Č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(logn) | logaritemska |
| O(n) | linearna |
| O(nlogn) | vmesna |
| O(n2) | kvadratna |
| O(nc), c > 1 | polinomska |
| O(cn) | eksponentna |
[uredi] Glej tudi
[uredi] Zunanje povezave
- Časovna zahtevnost na MaFiRa
