Izpitno vprašanje RAČ2PRA 3900

Iz MaFiRaWiki

Ta članek ali del članka je v delu. Veseli bomo, če ga boste dopolnili in popravili.

Kaj pomeni to opozorilo?

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 primere uporabe časovne zahtevnosti :

  • Algoritem za iskanje minimalnega elementa z direktnim iskanjem (zaporedno primerjanje)

  1. direktno_iskanje_min(int[] a, int n, int amin){
  2.  
  3. amin = a[0];
  4. for(i = 1 do n){
  5. if(a[i] < amin){
  6. amin = a[i];
  7. }
  8. }
  9. }

Časovna zahtevnost: O(n)
n-1 primerjav, če elementi niso vnaprej urejeni

  • Primer:potenciranje

Algoritem, ki nam izračuna b n.

  1. static double poten2 (double b, int n)
  2. { // Vrne b^n (kjer je n ne-negativen)
  3. double p = 1.0, q = b;
  4. int m = n;
  5. while(m > 0) {
  6. if (m % 2 != 0) p = p * q; // množenje s q
  7. m = m / 2; q = q * q; // podvojimo
  8. }
  9. return p;
  10. }

Analiza (štejemo množenja):
Maks. št. množenj = 2 floor(log2 n) + 2;

Časovna zahtevnost je reda O(log n).

  • Poglejmo si algoritem, s katerim urejamo z vstavljanjem:

  1. public static void uredi_z_vstavljanjem(int[] a) {
  2. for (int i = 1; i < a.length; i = i + 1) {
  3. int j = i;
  4. int t = a[j];
  5. while (j > 0 && a[j-1] > t) {
  6. a[j] = a[j-1];
  7. j = j - 1;
  8. }
  9. a[j] = t;
  10. }
  11. }

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

  1. public static void uredi_z_izbiranjem(int[] a) {
  2. for (int i = 0; i < a.length; i = i + 1) {
  3. int j = i;
  4. for (int k = i; k < a.length; k = k + 1) {
  5. if (a[k] < a[j]) {
  6. j = k;
  7. }
  8. }
  9. int t = a[i];
  10. a[i] = a[j];
  11. a[j] = t;
  12. }
  13. }

Č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;            
 
d :            ponavljaj_za  k := 1 do n
 
e :                   vsota  := vsoat + a[i,k]*b[k,j];
 
f :            C[i,j] := vsota }
  • a: 1 povečanje števca, 1 vpis, 1 primerjava = 3
  • b: 1 povečanje števca, 1 vpis, 1 primerjava = 3
  • c: 1 vpis = 1
  • d: 1 povečanje števca, 1 vpis, 1 primerjava = 3
  • e: 1 vpis, 2 aritm. oper., 2 rač. indeksa = 5
  • f: 1 vpis, 1 rač. indeksa = 2

Č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 = 8*n3 + 6*n2 + 3*n.

Osebna orodja