Informatică Algoritmi
Cum se calculeaza complexitatea temporala a unui algoritm?
Complexitatea temporală a unui algoritm se calculează analizând numărul de operații elementare executate în funcție de dimensiunea datelor de intrare, notată de obicei cu n. Aceasta determină timpul de execuție în cel mai rău, mediu sau cel mai bun caz.
Pași de calcul
- 1 Identifică operația de bază Alege operația dominantă, cum ar fi comparații într-un sortare sau atribuiri într-o buclă. Exemplu: în căutarea liniară, operația de bază este compararea fiecărui element cu cheia.
- 2 Numără operațiile în funcție de n Exprimă numărul de operații ca o funcție de n. Pentru o buclă care parcurge un vector de n elemente, numărul de comparații este n în cel mai rău caz.
- 3 Aplică notația asimptotică Simplifică funcția folosind notația O (big O) pentru cel mai rău caz. De exemplu, dacă numărul de operații este 3n² + 2n + 1, complexitatea este O(n²).
Exemple comune
- Căutarea liniară Parcurgi un vector de n elemente; în cel mai rău caz, faci n comparații, deci complexitatea este O(n).
- Sortarea prin selecție Pentru un vector de n elemente, faci n(n-1)/2 comparații, aproximativ n²/2, deci complexitatea este O(n²).
- Căutarea binară Împărți intervalul la fiecare pas; numărul de pași este log₂(n), deci complexitatea este O(log n).
Folosește analiza asimptotică pentru a compara eficiența algoritmilor în practică.