Izpitno vprašanje RAČ2PRA 3900

Iz MaFiRaWiki

(Razlika med različicami)
Različica od 18:55, 6 maj 2006
AleksandraVujasin (Pogovor | prispevki)
Primeri
← Prejšnja različica
Različica od 19:24, 6 maj 2006
AleksandraVujasin (Pogovor | prispevki)
Primeri
Naslednja različica →
Vrstica 51: Vrstica 51:
==Primeri== ==Primeri==
 +
 +Poglejmo si nekaj primerov uporabe časovne in prostorske zahtevnosti :
 +
 +* Poglejmo si algoritem, s katerim urejamo z vstavljanjem:
 +
 +public static void uredi_z_vstavljanjem(int[] a) {
 + for (int i = 1; i < a.length; i = i + 1) {
 + int j = i;
 + int t = a[j];
 + while (j > 0 && a[j-1] > t) {
 + a[j] = a[j-1];
 + j = j - 1;
 + }
 + a[j] = t;
 + }
 +}
 +
 +Časovna zahtevnost je v najslabšem primeru O(n<sup>2</sup>). To dobimo iz vsote 1 + 2 + ... + (n-1) = (n - 1) * n / 2 = (n2 - n) / 2 .
 +
 +Časovna zahtevnost je v najboljšem primeru O(n). To dobimo iz vsote : 1 + 1 + 1 +...+ 1 = n - 1.
 +
 +Pričakovana časovna zahtevnost je O(n<sup>2</sup>).
 +
 +* Poglejmo si algoritem, s katerim urejamo z izbiranjem:
 +
 +public static void uredi_z_izbiranjem(int[] a) {
 + for (int i = 0; i < a.length; i = i + 1) {
 + int j = i;
 + for (int k = i; k < a.length; k = k + 1) {
 + if (a[k] < a[j]) {
 + j = k;
 + }
 + }
 + int t = a[i];
 + a[i] = a[j];
 + a[j] = t;
 + }
 +}
 +
 +Časovna zahtevnost je v najslabšem primeru O(n<sup>2</sup>).<br/>
 +To dobimo iz vsote: (n*2[primerjanje in prirejanje] + 3[prirejanja]) + ((n-1)*2 + 3) +(n-2)*2 + 3) +... + (1*2 + 3) =
 +2*(n + (n-1) + ... + 2 + 1) + n*3 = n*(n + 1) + n*3 = n*(n + 4) = n<sup>2</sup> + 4*n
 +
 +Časovna zahtevnost je v najboljšem primeru O(n).
 +
 +Pričakovana časovna zahtevnost je O(n log n).
 +
 +* Poglejmo si poljuben algoritem.
 +
 + a: ponavljaj_za i := 1 do n
 +
 + b: ponavljaj_za j := 1 do n
 +
 + c: { vsota := 0;
 +
 + e: ponavljaj_za k := 1 do n
 +
 + f: vsota := vsoat + a[i,k]*b[k,j];
 +
 + g: C[i,j] := vsota }
 +
 +
 +
 +Časovna zahtevnost je O(n3). Torej imamo kubični čas. To dobimo iz vsote:
 +
 +n*(a + n*(b + c + n*(d + e) + f)) = n*a +n<sup>2</sup>*b + n<sup>2</sup>*c + n<sup>3</sup>*d + n<sup>3</sup>*e + n<sup>2</sup>*f (a, b, c ,d ,e in f nadomestimo z preštetimi povečanji števcev, vpisi in primerjavami) in dobimo:<br/> 3*n + 3*n<sup>2</sup> + n<sup>2</sup> + 3*n<sup>3</sup> + 5*n<sup>3</sup> + 2*n<sup>2</sup> = 8n<sup>3</sup> + 6n<sup>2</sup> + 3n.

Različica od 19:24, 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

Poglejmo si nekaj primerov uporabe časovne in prostorske zahtevnosti :

  • Poglejmo si algoritem, s katerim urejamo z vstavljanjem:

public static void uredi_z_vstavljanjem(int[] a) {

  for (int i = 1; i < a.length; i = i + 1) {
     int j = i;
     int t = a[j];
     while (j > 0 && a[j-1] > t) {
        a[j] = a[j-1];
        j = j - 1;
     }
     a[j] = t;
  }

}

Časovna zahtevnost je v najslabšem primeru O(n2). To dobimo iz vsote 1 + 2 + ... + (n-1) = (n - 1) * n / 2 = (n2 - n) / 2 .

Časovna zahtevnost je v najboljšem primeru O(n). To dobimo iz vsote : 1 + 1 + 1 +...+ 1 = n - 1.

Pričakovana časovna zahtevnost je O(n2).

  • Poglejmo si algoritem, s katerim urejamo z izbiranjem:

public static void uredi_z_izbiranjem(int[] a) {

   for (int i = 0; i < a.length; i = i + 1) {
       int j = i;
       for (int k = i; k < a.length; k = k + 1) {
          if (a[k] < a[j]) {
             j = k;
          }
       }
       int t = a[i];
       a[i] = a[j];
       a[j] = t;
   }

}

Časovna zahtevnost je v najslabšem primeru O(n2).
To dobimo iz vsote: (n*2[primerjanje in prirejanje] + 3[prirejanja]) + ((n-1)*2 + 3) +(n-2)*2 + 3) +... + (1*2 + 3) = 2*(n + (n-1) + ... + 2 + 1) + n*3 = n*(n + 1) + n*3 = n*(n + 4) = n2 + 4*n

Časovna zahtevnost je v najboljšem primeru O(n).

Pričakovana časovna zahtevnost je O(n log n).

  • Poglejmo si poljuben algoritem.
a:   ponavljaj_za  i := 1 do n
b:       ponavljaj_za  j := 1 do n
c:         { vsota  := 0;            
e:        ponavljaj_za  k := 1 do n
f:             vsota  := vsoat + a[i,k]*b[k,j];
g:    C[i,j] := vsota }


Časovna zahtevnost je O(n3). Torej imamo kubični čas. To dobimo iz vsote:

n*(a + n*(b + c + n*(d + e) + f)) = n*a +n2*b + n2*c + n3*d + n3*e + n2*f (a, b, c ,d ,e in f nadomestimo z preštetimi povečanji števcev, vpisi in primerjavami) in dobimo:
3*n + 3*n2 + n2 + 3*n3 + 5*n3 + 2*n2 = 8n3 + 6n2 + 3n.

Osebna orodja