Eficienta algoritmilor

Ce este „eficienta algoritmilor„?

Iata o intrebare foarte des intalnita la care multa lume nu ii cunoaste nici macar raspunsul de baza. Ideea de la care se porneste este aceea ca pentru rezolvarea unei probleme se pot scrie mai multi algoritmi corecti. Dintre acestia, este eficient sa il alegem pe cel mai scurt.

Care este criteriul dupa care se face o astfel de comparatie?

Care este mai bun sau mai putin bun? Care algoritm este mai bine sa fie folosit si care nu?

Eficienta algoritmilor se poate exprima in mai multe moduri.

Algoritmul poate fi analizat dupa implementare. Aici vorbim in primul rand de rularea si testarea algoritmului cu o baterie de teste pregatita anterior. Se analizeaza raspunsul obtinut si se constata care este cel mai bun algoritm.

O alta cale este aceea de a analiza, inainte de implementare, in linii mari bugetul de operatii si de timp pe care il va solicita acel algoritm. Din nou se poate foarte repede stabili care este cel mai eficient algoritm.

Avantajul celei de a doua metode consta in primul rand in faptul ca algoritmul nu depinde de calculatorul pe care este implementat, pentru ca eficienta lui este evaluata inainte de implementare. Se salveaza astfel foarte mult timp care s-ar consuma pentru implementarea si testarea unui algoritm care mai apoi sa se dovedeasca a fi ineficient.

Este posibil insa sa analizam eficienta algoritmilor si printr-o metoda combinata. In acest caz, valorile numerice sunt determinate dupa implementarea algoritmului iar functiile si metodele folosite in implementare sunt stabilite inainte de implementare. In acest caz, extrapolarea rezultatelor este eliminata pentru ca este imprecisa.

Cum alegem cel mai eficient algoritm?

Principiul invariantei ne ajuta sa raspundem la aceasta intrebare. Daca doua implementari ale aceluiasi algoritm difera intre ele prin intervalul de timp in care se desfasoara. Daca avem 2 intervale de timp t1 si t2 atunci exista o constanta pozitiva a, destul de mare, astfel incat t1 <= a * t2.

Acest principiu nu depinde de limbajul de programare in care se implementeaza algoritmul si nici de computerul pe care ruleaza acesta.