Informatică Algoritmi
Cum se calculeaza complexitatea unui algoritm?
Complexitatea unui algoritm se calculează analizând numărul de operații de bază în funcție de dimensiunea intrării, notată de obicei cu n. Aceasta determină eficiența algoritmului în timp (complexitate temporală) și spațiu (complexitate spațială). De exemplu, pentru o buclă care rulează de n ori, complexitatea temporală este O(n).
Pași de calcul al complexității temporale
- 1 Definește dimensiunea intrării Identifică variabila n, cum ar fi numărul de elemente într-o listă sau lungimea unui șir.
- 2 Numără operațiile dominante Contorizează operațiile care cresc cu n, cum ar fi comparații în bucle sau atribuiri.
- 3 Exprimă ca funcție de n Scrie o formulă, de exemplu T(n) = 3n + 2 pentru un algoritm cu o buclă și operații constante.
- 4 Aplică notația asimptotică Simplifică la O(n), O(n²) etc., ignorând termenii de ordin inferior și constantele.
Exemple numerice
- Algoritm liniar Pentru o buclă 'pentru i de la 1 la n, afișează i', complexitatea este O(n) deoarece rulează n pași.
- Algoritm pătratic Pentru două bucle imbricate 'pentru i de la 1 la n, pentru j de la 1 la n, calculează suma', complexitatea este O(n²).
- Algoritm logaritmic Pentru căutarea binară pe o listă sortată, complexitatea este O(log n) deoarece dimensiunea se înjumătățește la fiecare pas.
Exersează pe cod simplu pentru a înțelege cum să numeri operațiile corect.