Izpitno vprašanje RAČ2PRA 3900

Iz MaFiRaWiki

(Razlika med različicami)
Različica od 13:47, 12 maj 2006
AleksandraVujasin (Pogovor | prispevki)
Primeri
← Prejšnja različica
Različica od 20:33, 13 maj 2006
AleksandraVujasin (Pogovor | prispevki)
Primeri
Naslednja različica →
Vrstica 53: Vrstica 53:
==Primeri== ==Primeri==
-Poglejmo si nekaj primerov uporabe časovne zahtevnosti :+Poglejmo si primere uporabe časovne zahtevnosti :
 + 
 +* Algoritem za iskanje minimalnega elementa z direktnim iskanjem (zaporedno primerjanje)
 +<java>direktno_iskanje_min(int[] a, int n, int amin){
 + 
 + amin = a[0];
 + for(i = 1 do n){
 + if(a[i] < amin){
 + amin = a[i];
 + }
 + }
 +}</java>
 + 
 +Časovna zahtevnost: '''O(n)'''<br/>
 +n-1 primerjav, če elementi niso vnaprej urejeni
 + 
 +* Primer:potenciranje<br/>
 +Algoritem, ki nam izračuna b <sup>n</sup>.
 + 
 +<java>static double poten2 (double b, int n)
 +{ // Vrne b^n (kjer je n ne-negativen)
 + double p = 1.0, q = b;
 + int m = n;
 + while(m > 0) {
 + if (m % 2 != 0) p = p * q; // množenje s q
 + m = m / 2; q = q * q; // podvojimo
 + }
 + return p;
 +}</java>
 +Analiza (štejemo množenja):<br/>
 +Maks. št. množenj = 2 floor(log<sub>2</sub> n) + 2;<br/>
 + 
 +Časovna zahtevnost je reda '''O(log n)'''.
* Poglejmo si algoritem, s katerim urejamo z vstavljanjem: * Poglejmo si algoritem, s katerim urejamo z vstavljanjem:

Različica od 20:33, 13 maj 2006

GFDL Avtor tega članka je študent/ka AleksandraVujasin.

Pripravil/a ga je pri predmetu Računalništvo 2 (FMF PRA).


Kljub temu ste vsi vabljeni k urejanju in popravkom, saj je bistvo wikija ravno v sodelovalnem delu.

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