Izpitno vprašanje RAČ2PRA 3900

Iz MaFiRaWiki

(Razlika med različicami)
Različica od 18:54, 6 maj 2006
AleksandraVujasin (Pogovor | prispevki)
Odgovor
← Prejšnja različica
Različica od 18:55, 6 maj 2006
AleksandraVujasin (Pogovor | prispevki)
Primeri
Naslednja različica →
Vrstica 50: Vrstica 50:
</table> </table>
-=Primeri=+==Primeri==

Različica od 18:55, 6 maj 2006

Vprašanje

Naštej tipične razrede časovnih zahtevnosti! Za vsakega poišči konkreten primer algoritma in pokaži, da je časovna zahtevnost res takšnega reda.

Odgovor

Č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
  • fW - najslabša možnost (worst case) ali zgornja meja zahtevnosti
  • 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 (preproste operacije kot so izpis vzorca,...)
O(logn) logaritmska (množenje)
O(n) linearna (vsota n - števil)
O(nlogn) vmesna (quicksort)
O(n2) kvadratna (množenje matrik)
O(n3) kubična (reševanje sistema linearnih enačb)
O(nc), c<1 polinomska
O(cn) eksponentna (rekurzija)

Primeri

Osebna orodja