De ce contează?
Cauți un cuvânt într-un dicționar. Îl iei pagină cu pagină de la început? Sau deschizi la mijloc, vezi că ești prea departe și înjumătățești zona de căutat? A doua metodă e mult mai rapidă — și exact această diferență de „cât de repede crește efortul" o măsoară complexitatea.
Ce măsoară complexitatea
Complexitatea nu măsoară secunde — depind de calculator. Măsoară cum crește numărul
de operații când crește n (mărimea datelor). O scriem cu notația „O mare": păstrezi
doar termenul care domină și ignori constantele.
Patru clase pe care le întâlnești mereu:
| Notație | Nume | Efort când n se dublează |
|---|---|---|
| O(1) | constant | neschimbat |
| O(log n) | logaritmic | crește cu un pas |
| O(n) | liniar | se dublează |
| O(n²) | pătratic | se face de 4 ori mai mare |
Intuiția cheie: nu contează cât durează un pas, ci câți pași faci în funcție de
n. Un algoritm O(n) cu pași lenți bate, pentru n mare, un O(n²) cu pași rapizi.
Cum recunoști fiecare clasă în cod
- O(1) — un număr fix de operații, fără bucle peste date:
int x = a + b;. - O(n) — o singură buclă peste cele
nelemente: parcurgi vectorul o dată. - O(n²) — o buclă în altă buclă, fiecare peste
n: compari fiecare element cu fiecare. - O(log n) — la fiecare pas înjumătățești problema: căutare binară,
n /= 2.
// O(1): cost constant
int prim = v[0];
// O(n): o trecere
for (int i = 0; i < n; i++) suma += v[i];
// O(n^2): bucla in bucla
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
if (v[i] + v[j] == tinta) ...
// O(log n): injumatatim de fiecare data
while (n > 0) n /= 2;De ce contează: ordinul de mărime
La concurs, un procesor face aproximativ 10⁸ operații simple pe secundă. Cu o limită
tipică de 1 secundă, asta înseamnă cam 10⁸ operații „permise". Iată câte operații cer
clasele pentru diferite n:
n | O(n) | O(n²) | O(log n) |
|---|---|---|---|
| 1.000 | 1.000 | 1.000.000 | ~10 |
| 100.000 | 100.000 | 10¹⁰ ❌ | ~17 |
| 1.000.000 | 1.000.000 | 10¹² ❌ | ~20 |
Pentru n = 100.000, un O(n²) cere 10¹⁰ operații → ~100 de secunde, mult peste limită.
Același n cu O(n) cere doar 100.000 operații → instantaneu. Aceeași problemă, două verdicte
diferite, doar din cauza complexității.
Cum alegi în practică
Citește limita lui n din enunț — îți spune ce complexitate îți permiți:
n până la | Complexitatea de care ai nevoie |
|---|---|
| ~500 | O(n³) e ok |
| ~5.000 | O(n²) |
| ~10⁶ | O(n) sau O(n log n) |
| ~10⁹ | O(log n) sau O(1) |
Așa, încă dinainte să scrii cod, știi dacă soluția pătratică „naivă" trece sau dacă ai nevoie de o tehnică mai isteață (căutare binară, sume parțiale, two pointers).
Greșeli reale legate de complexitate:
- Soluție pătratică pentru
nmare: scrii două bucle imbricate pentrun = 10⁵→ 10¹⁰ operații, depășești timpul (Time Limit Exceeded), deși rezultatul ar fi corect. - Ignori constanta când
ne mic: pentrun = 100, O(n²) e doar 10.000 operații — perfect. Nu complica degeaba o soluție simplă. - Confuzi „merge pe exemplu" cu „intră în timp": codul dă rezultatul corect pe
testul mic din enunț, dar pică pe testele mari. Verifică mereu complexitatea față de
limita lui
n. - Uiți costul ascuns: o operație în buclă care e ea însăși O(n) (ex. o căutare liniară) transformă un O(n) aparent într-un O(n²) real.
De reținut
- Complexitatea măsoară cum crește numărul de pași cu
n, nu secunde. - O(1) < O(log n) < O(n) < O(n²); recunoști clasa după numărul și imbricarea buclelor.
- Limita lui
ndin enunț îți dictează complexitatea necesară — verific-o înainte să scrii cod.