analiza complexitatatii (1)

Analiza complexitatii (eficientei) algoritmilor

A.Scop: estimarea volumului de resurse de calcul necesare pentru executia algoritmului.

Resursele sint :1. Spatiul de memorie.2. Timpul de executie.

Dintre aceste resurse cea critica este timpul de executie.

1. Volumul resurselor necesare depinde de dimensiunea problemei de rezolvat - de volumul datelor de intrare, de exemplu:- Un numar- Numarul de elemente dintr-un tablou de memorie- Numarul de caractere/ cuvinte dintr-un text (daca prelucrarea sirului se face la nivel de caracter sau de cuvint).

2. In analiza timpului de executie este necesara stabilirea unei unitati de masura – determinarea unei operatii elementare relavante.

Analiza cazurilor extreme:2.1. Cazul cel mai favorabil /Cazul cel mai defavorabil2.2. Cazul mediu

B. Ordinul de complexitate

C. Clase de complexitate

- logaritmica O(log n)- liniara O(n)- patraticaO(n2) - cubicaO(n3) - exponentialaO(2n) - factorialaO(n!)

*Analiza algoritmilor de sortare:-prin selectie (cu alegerea minimului/maximului);-prin insertie;-prin interschimbare;-prin numarare;-Bubble ;-quicksort;-mergeSort;

**Analiza algoritmilor de cautare:-secventiala;-binara;

***Analiza altor algoritmi: