Izpitno vprašanje RAČ2PRA 3900

Iz MaFiRaWiki

(Razlika med različicami)
Različica od 17:25, 6 maj 2006
AleksandraVujasin (Pogovor | prispevki)
Vprašanje
← Prejšnja različica
Različica od 18:54, 6 maj 2006
AleksandraVujasin (Pogovor | prispevki)
Odgovor
Naslednja različica →
Vrstica 4: Vrstica 4:
=Odgovor= =Odgovor=
 +
 +Časovna zahtevnost je podatek o tem, koliko časa se bo program (oziroma [[Algoritem|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 [[Funkcija|funkcijo]] velikosti vhodnih podatkov (npr. velikost tabele). Poznamo tri vrste časovne zahtevnosti:
 +*f<sub>B</sub> - najboljša možnost (best case) ali spodnja meja zahtevnosti
 +*f<sub>W</sub> - najslabša možnost (worst case) ali zgornja meja zahtevnosti
 +*f<sub>E</sub> - 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-notacija|O-notacijo]], ki označuje red rasti problema. Če velikost vhoda označimo z n, c pa je neka [[Konstanta|konstanta]], potem imamo naslednje zahtevnosti, od najugodnejše do najneugodnejše:
 +
 +<table border=1 cellpadding=2 cellspacing=0>
 +<tr>
 +<th>Notacija</th>
 +<th>Zahtevnost</th>
 +</tr>
 +<tr>
 +<td>''O(1)''</td>
 +<td>konstantna (preproste operacije kot so izpis vzorca,...)</td>
 +</tr>
 +<tr>
 +<td>''O(logn)''</td>
 +<td>logaritmska (množenje)</td>
 +</tr>
 +<tr>
 +<td>''O(n)''</td>
 +<td>linearna (vsota n - števil)</td>
 +</tr>
 +<tr>
 +<td>''O(nlogn)''</td>
 +<td>vmesna (quicksort)</td>
 +</tr>
 +<tr>
 +<td>''O(n<sup>2</sup>)''</td>
 +<td>kvadratna (množenje matrik)</td>
 +</tr>
 +<tr>
 +<td>''O(n<sup>3</sup>)''</td>
 +<td>kubična (reševanje sistema linearnih enačb)</td>
 +</tr>
 +<tr>
 +<td>''O(n<sup>c</sup>), c<1''</td>
 +<td>polinomska</td>
 +</tr>
 +<tr>
 +<td>''O(c<sup>n</sup>)''</td>
 +<td>eksponentna (rekurzija)</td>
 +</tr>
 +</table>
 +
 +=Primeri=

Različica od 18:54, 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