Pe scurt
Analiza complexității algoritmilor evaluează eficiența unui algoritm prin timpul de execuție și memoria utilizată, independent de hardware sau limbaj de programare. Notația asimptotică „O mare” (O) descrie comportamentul algoritmului pentru valori mari ale datelor de intrare, notate cu n. Identificarea corectă a clasei de complexitate este esențială pentru alegerea algoritmului optim, economisind timp și resurse.
Timpul de execuție (complexitatea temporală)
Complexitatea temporală măsoară numărul de operații elementare în funcție de mărimea datelor de intrare
n. Se identifică
operațiile dominante (de exemplu, comparații sau atribuiri dintr-o buclă) și se exprimă numărul lor în funcție de n.
Reguli de bază pentru calcul:
- O secvență de instrucțiuni se însumează
- O buclă simplă se înmulțește cu numărul de iterații
- Buclele imbricate se înmulțesc
Exemple comune de complexități temporale:
- O(1) – timp constant (accesul la un element dintr-un vector)
- O(log n) – căutarea binară
- O(n) – parcurgerea liniară
- O(n log n) – sortări eficiente (merge sort, quick sort)
- O(n²) – algoritmi de sortare simpli (bubble sort) sau parcurgeri duble
Algoritmi recursivi: se utilizează relații de recurență (de exemplu, T(n) = 2T(n/2) + n pentru merge sort, care duce la O(n log n))
Cazuri de analiză:
- Cazul cel mai defavorabil (worst-case)
- Cazul mediu (average-case)
Memoria utilizată (complexitatea spațială)
Complexitatea spațială se măsoară similar, analizând
memoria suplimentară (variabile, tablouri) fără a include memoria datelor de intrare. Un algoritm
„in-place” folosește O(1) spațiu suplimentar.
Exemple practice
- Exemplul 1: Căutarea liniară într-un vector de n elemente – în cel mai rău caz, executăm n comparații, deci complexitatea temporală este O(n). Memoria suplimentară: o variabilă i și una pentru elementul curent, deci O(1) spațiu.
- Exemplul 2: Bubble Sort – două bucle imbricate, numărul total de comparații este aproximativ n*(n-1)/2, adică O(n²). În varianta optimizată, dacă vectorul este deja sortat, complexitatea poate fi O(n). Spațiul suplimentar: o variabilă temporară, deci O(1).
- Exemplul 3: Merge Sort – relația de recurență T(n) = 2T(n/2) + n, rezolvând obținem O(n log n). Memoria suplimentară: un vector auxiliar de dimensiune n, deci O(n).
Concepte cheie
- Notația asimptotică O mare (Big O) – limita superioară a complexității
- Complexitatea temporală – numărul de operații elementare în funcție de n
- Complexitatea spațială – memoria suplimentară utilizată de algoritm
- Analiza buclelor simple și imbricate
- Relații de recurență pentru algoritmi recursivi (ex. Merge Sort)
- Compararea algoritmilor: O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ)
Observații importante:
- Nu întotdeauna cel mai rapid algoritm în teorie este cel mai bun în practică, deoarece factorii constanți și dimensiunea mică a datelor pot influența
- Logaritmii sunt în baza 2, dar baza nu contează în notația asimptotică (log n = O(log n))
- Pentru examenele de Bacalaureat, accentul cade pe identificarea corectă a clasei de complexitate, folosind notația O, și pe compararea algoritmilor
Verifică-te!
- Care este complexitatea temporală a căutării binare și de ce este mai rapidă decât căutarea liniară pentru valori mari ale lui n?
- Ce înseamnă un algoritm „in-place” din perspectiva complexității spațiale?
- Cum se calculează complexitatea temporală pentru un algoritm cu două bucle imbricate care parcurg o matrice n x n?