Pe scurt
Complexitatea algoritmilor măsoară eficiența acestora din punctul de vedere al timpului de execuție și al spațiului de memorie utilizat, permițând anticiparea comportamentului pe măsură ce volumul datelor de intrare crește. Notația asimptotică Big-O (O) descrie limita superioară a ratei de creștere, ignorând constantele și factorii mici, iar tiparele comune includ O(1) pentru timp constant, O(n) pentru bucle simple, O(n²) pentru bucle imbricate și O(log n) pentru injumătățirea datelor.
Tipuri de complexitate
- Complexitatea de timp – numărul de operații elementare efectuate în funcție de mărimea intrărilor
- Complexitatea de memorie – cantitatea de memorie suplimentară necesară
Notația asimptotică Big-O
Notația Big-O (O) este folosită pentru a descrie limita superioară a ratei de creștere. Exemple comune:
- O(1) – timp constant
- O(log n) – logaritmic
- O(n) – liniar
- O(n log n) – liniar-logaritmic
- O(n²) – pătratic
- O(2ⁿ) – exponențial
Reguli importante:
- Nu se calculează exact numărul de operații, ci tendința de creștere
- Constantele și factorii mici sunt ignorați (de exemplu, 3n + 5 este considerat O(n))
Cazuri de analiză
Analiza complexității se face pe trei cazuri
- Cazul cel mai defavorabil (worst-case) – cel mai lung timp posibil
- Cazul mediu (average-case)
- Cazul favorabil (best-case)
Identificarea complexității după structura algoritmului
- Bucle simple – o buclă care rulează de n ori → O(n)
- Bucle imbricate – două bucle care rulează fiecare câte n ori → O(n²)
- Injumătățirea datelor (căutare binară) → O(log n)
- Recursivitatea – de exemplu, Fibonacci nerecursiv are O(2ⁿ), iar varianta cu memoizare are O(n)
Exemple concrete
Exemplul 1: Căutarea liniară într-un vector nesortat
- Algoritmul parcurge elementele unul câte unul până găsește valoarea căutată sau până la sfârșit
- În cel mai defavorabil caz, elementul căutat este ultimul sau nu există → se fac n comparații
- Complexitatea de timp: O(n)
- Memoria suplimentară: O(1) (doar câteva variabile)
Exemplul 2: Sortarea prin selecție
- Bucla exterioară (i de la 0 la n-2) și pentru fiecare i, o buclă interioară (j de la i+1 la n-1) pentru a găsi minimul
- Numărul total de comparații: n(n-1)/2
- Complexitatea de timp: O(n²)
- Memoria suplimentară: O(1) (doar variabile temporare)
Exemplul 3: Căutarea binară într-un vector sortat
- Algoritmul compară valoarea căutată cu elementul din mijloc, apoi restrânge intervalul la jumătatea corespunzătoare
- De fiecare dată, numărul de elemente se înjumătățește → aproximativ log₂(n) pași
- Complexitatea de timp: O(log n)
- Memoria suplimentară: O(1) (variabilele stânga, dreapta, mijloc)
Algoritmi clasici pentru Bacalaureat
La Bacalaureat, se cere identificarea complexității pentru algoritmi simpli
- Parcurgerea vectorilor
- Algoritmii de sortare (sortare prin selecție, sortare prin inserție)
- Căutarea liniară și binară
- Prelucrarea matricelor
Comparații între sortări:
- BubbleSort → O(n²)
- QuickSort (în medie) → O(n log n)
Concepte cheie
- Complexitate de timp – numărul de operații elementare în funcție de mărimea intrărilor
- Complexitate de memorie – cantitatea de spațiu suplimentar utilizat
- Notația Big-O (O) – limita superioară asimptotică
- Cazul cel mai defavorabil (worst-case) – cel mai lung timp posibil
- Bucle imbricate și creșterea pătratică O(n²)
- Injumătățirea datelor și complexitatea logaritmică O(log n)
- Comparația între sortări: O(n²) vs O(n log n)
- Analiza recursivității și a arborilor de apeluri
Verifică-te!
- Ce complexitate de timp are un algoritm care parcurge un vector de n elemente o singură dată?
- De ce se ignoră constantele și factorii mici în notația asimptotică?
- Ce complexitate de timp are căutarea binară și de ce?