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