Pe scurt
Analiza complexității algoritmilor evaluează eficiența acestora în funcție de timp și spațiu, utilizând notația asimptotică O mare (Big O) pentru a descrie rata de creștere a resurselor consumate. Scopul principal este anticiparea comportamentului algoritmului pe seturi mari de date, nu doar pe cazuri particulare. Înțelegerea acestor concepte ajută la alegerea celui mai potrivit algoritm pentru o problemă dată și la optimizarea codului.
Noțiuni fundamentale
Analiza complexității algoritmilor este o componentă fundamentală a informaticii, care ne permite să evaluăm eficiența unui algoritm în funcție de resursele consumate: timp (complexitate temporală) și spațiu (complexitate spațială).
Scopul principal este de a anticipa comportamentul algoritmului pe seturi mari de date, nu doar pe cazuri particulare.
Notația asimptotică
Notația asimptotică, în special O mare (Big O), descrie rata de creștere a timpului sau spațiului în funcție de dimensiunea intrării n.
Exemple de complexități
- O(1) – timp constant
- O(n) – liniar
- O(n²) – pătratic
- O(log n) – logaritmic
În practică, ignorăm constantele și termenii de ordin inferior (de exemplu, 3n² + 5n + 2 devine O(n²)).
Concepte cheie
- Notația asimptotică (O mare, Omega, Theta)
- Cazul cel mai favorabil, cazul mediu și cazul cel mai defavorabil
Complexitatea temporală
Complexitatea temporală se măsoară numărând operațiile elementare (comparații, atribuiri, operații aritmetice) pe măsură ce n crește.
Algoritmii eficienți au complexități polinomiale mici (de exemplu, O(n log n), O(n)). Algoritmii cu complexitate exponențială (O(2ⁿ)) sunt de evitat.
Complexitatea spațială
Complexitatea spațială măsoară memoria suplimentară necesară (stivă, heap, vectori auxiliari) în funcție de n.
Este important să distingem între memoria folosită de datele de intrare și cea alocată suplimentar de algoritm.
Analiza algoritmilor de căutare și sortare
În cadrul bacalaureatului, se analizează algoritmi pentru
- Căutare – O(n) secvențial, O(log n) binar
- Sortare – O(n²) prin selecție/bule, O(n log n) prin interclasare/quick sort
- Prelucrare a vectorilor
Exemple practice
Exemplul 1: Căutarea secvențială într-un vector nesortat de n elemente
- Pentru a găsi o valoare, parcurgem elementele până la găsirea acesteia
- În cazul cel mai defavorabil (elementul nu există sau e ultimul), se efectuează n comparații
- Complexitatea temporală este O(n)
- Spațial, nu alocăm memorie suplimentară, deci O(1)
Exemplul 2: Sortarea prin selecție
- Pentru n elemente, se găsește minimul din restul vectorului și se plasează pe poziție
- Numărul total de comparații este n(n-1)/2, deci O(n²)
- Spațial, algoritmul lucrează pe loc (in-place), fără memorie suplimentară semnificativă: O(1)
Exemplul 3: Algoritmul de căutare binară într-un vector sortat
- La fiecare pas, intervalul de căutare se înjumătățește
- Numărul de pași este log₂(n), deci complexitatea temporală este O(log n)
- Memoria suplimentară este O(1) (doar câteva variabile), dar recursiv poate fi O(log n) din cauza stivei
Verifică-te!
- Ce reprezintă notația O mare (Big O) în analiza complexității algoritmilor?
- Care este diferența principală între complexitatea temporală și complexitatea spațială?
- De ce se ignoră constantele și termenii de ordin inferior în analiza asimptotică?