LUCRARE DE LABORATOR NR. 1

Tema: Analiza algoritmilor (Timpul de execuţie al algoritmilor).

Scopul lucrării:1. Analiza empirică a algoritmilor.2. Analiza teoretică a algoritmilor.3. Determinarea complexităţii temporale şi asimptotice a algoritmilor

Sarcina pentru lucrarea nr.1: Numerele lui Fibonacci

Şirul lui Fibonacci este definit prin următoarea recurenţa:

Acest celebru şir a fost descoperit în 1202 de către Leonardo Pisano (Leonardo din Pisa), cunoscut sub numele de Leonardo Fibonacci. Cel de-al n-lea termen al şirului se poate obtine direct din definiţie:

function fib1(n)     if n < 2   then   return n                   else   return fib1(n-1) + fib1(n-2)

Această metodă este foarte ineficienta, deoarece recalculează de mai multe ori aceleaşi valori. Iată acum o altă metodă, mai performantă, care rezolvă aceeaşi problemă.

function fib2(n)     i 1; j 0     for k 1 to n do  j i + j                                 i j - i     return j

Mai există un algoritm :

function fib3(n)     i 1; j 0; k 0; h 1     while n > 0 do          if n este impar then   t jh                                           j ih+jk+t                                           i ik+t          t   h2

          h 2kh+t          k k2+t          n n div 2     return j

1

Anexa 1: Listingul programului:#include <iostream>#include <time.h>#include <conio.h>#include <stdio.h>using namespace std;int fib1(int n);int fib2(int n);int fib3(int n);int main(){

int n;time_t start, end;cout << "Dati n: "; cin >> n;start = time(NULL);cout << endl << fib1(n);end = time(NULL);printf("\ntimp de %.2f\n", difftime(end, start));cout<<endl;start = time(NULL);cout << endl << fib2(n);end = time(NULL);printf("\n timp de %.2f\n", difftime(end, start));cout<<endl;start = time(NULL);cout << endl << fib3(n);end = time(NULL);printf("\n timp de %.2f\n", difftime(end, start));cout<<endl;return 1;

}int fib3(int n){int i=1,j =0, k=0, h=1,t;

while (n > 0){if (n%2==1) {

t= j*h;j= i*h+j*k+t;i= i*k+t;

}t = h*h;h= 2*k* h+ ;k = k*k+t;n = n/2;

}return j;

}int fib2 (int n){int i=1,j =0;for (int k=0;k<n;k++) {

j=i+j;i=j-i;

}return j;}int fib1 (int n){

if (n < 2) return n;else return fib1(n - 1) + fib1(n - 2);

}

2

Anexa 2: Screenshot

SARCINA DE BAZĂ:1. Efectuaţi analiza empirică a algoritmilor propuşi.2. Determinaţi relaţia ce determină complexitatea temporală pentru aceşti algoritmi.3. Determinaţi complexitatea asimptotică a algoritmilor.4. Faceţi o concluzie asupra lucrării efectuate.

Întrebări de control:1. Enumeraţi factorii ce influenţează timpul de execuţie al algoritmului.2. Când timpul de execuţie al algoritmului este dat de o relaţie de recurenţă ?3. Care sunt regulile generale pentru evaluarea timpului de execuţie?4. Care sunt etapele analizei empirice şi în care cazuri se face analiza empirică a

algoritmilor?5. Ce proprietăţi posedă funcţiile asimptotice?

3