Introducere in Stiinta Calculatoarelor 2013 | Page 92

Cât de complexă este rezolvarea problemei relativ la timpul de
calcul necesar?
Complexitatea algoritmului
În acest paragraf se vor stabile mărimi de evaluare a complexităţii
algoritmilor. Analiza algoritmilor priveşte în principal timpul de
execuţie, dar acesta depinde puternic de sistemul de calcul şi de
contextul de rezolvare. O modalitate mai generală este calculul
numărului de operaţii executate de algoritm pentru rezolvarea
problemei – aceasta fiind dependentă doar de metoda de rezolvare şi de
numărul n al pieselor de date de intrare. În acest sens, compararea
programelor se poate face urmărind în principal numărul de operaţiuni
costisitoare ca timp de execuţie, cum sunt: apeluri de funcţii, înmulţiri
şi împărţiri, atribuiri, comparaţiile, etc.
Pentru un număr n de piese de date la intrare, ne interesează:
complexitatea temporală – notată T(n), care reprezintă numărul
de operaţii executate de algoritm asupra setului de intrare
(considerând o operaţie în unitatea de timp);
complexitatea spaţială – notată S(n), care reprezintă numărul de
locaţii de memorie folosite de algoritm (memoria de date, stiva,
regiştrii);
unde T(n) şi S(n) nu sunt funcţii ci relaţii, fiindcă pot avea pentru acelaşi
n rezultate diferite (dependente de modul în care algoritmi diferiţi
rezolvă o problemă).
Analiza unui algoritm se face pentru un număr generic de n date în cele
trei cazuri de interes:
cel mai defavorabil – indicând maximul numărului de operaţii
efectuate,
mediu – indicând media numărului de operaţii efectuate,
cel mai favorabil - indicând minimul numărului de operaţii
efectuate.
Uzual, se analizează cazul cel mai defavorabil, apreciat prin Ordinul
algoritmului, notat O (O mare), acesta corespunzând timpului cel mai
lung (sau spaţiului cel mai mare) necesar algoritmului pentru a prelucra
92