
Notația Big O îți spune cât de repede crește timpul (sau memoria) de care are nevoie un algoritm atunci când crește volumul de date. Nu măsoară secunde, ci ritmul de creștere: un algoritm O(n) face de zece ori mai mulți pași la de zece ori mai multe date, unul O(n²) face de o sută de ori mai mulți.
Toate tipurile de algoritmi, cu vizualizare pas cu pas: algoritmi explicați pe înțeles, căutarea binară în O(log n) și metoda bulelor în O(n²).
În acest ghid vezi clasele de complexitate pe care le întâlnești cel mai des, cum calculezi Big O pentru codul tău în patru reguli, două exemple Python care rulează și numără pașii, plus cum răspunzi la întrebarea „ce complexitate are soluția ta?” la interviu.
Ce este Big O, pe înțelesul tuturor
Big O este o notație care descrie cum se comportă un algoritm pe date din ce în ce mai mari, de obicei în cazul cel mai nefavorabil. Litera n înseamnă dimensiunea intrării: câte elemente are lista, câte rânduri are tabelul, câte caractere are textul.
Gândește-te la o bibliotecă de cartier cu 1.000 de cărți. Dacă sunt puse la întâmplare pe rafturi și cauți una anume, în cel mai rău caz te uiți la toate 1.000. Dacă sunt ordonate alfabetic, deschizi la mijloc, vezi dacă titlul tău e înainte sau după, și înjumătățești căutarea de fiecare dată. Ajungi la carte în cel mult 10 pași. Prima metodă este O(n), a doua O(log n).
Diferența nu se vede la 10 cărți. Se vede la un milion de înregistrări, când una dintre metode răspunde instant și cealaltă blochează aplicația.
Complexitatea algoritmilor: de ce contează Big O
Big O contează pentru că îți spune, înainte să rulezi codul pe date reale, dacă soluția ta va rezista când datele cresc. Un script care merge perfect pe un fișier Excel de 200 de rânduri poate deveni inutilizabil pe un export de 200.000 de rânduri de la contabilitate.
Al doilea motiv e interviul tehnic. Aproape orice problemă de algoritmi la interviu se termină cu aceeași întrebare: ce complexitate are soluția ta și o poți îmbunătăți? Recrutorul nu vrea doar un cod care merge, ci să vadă că știi cât costă. Lista de întrebări tehnice frecvente la interviurile IT include aproape mereu o variantă a acestei întrebări. În cursul de algoritmi pentru interviuri, Big O pentru timp și spațiu apare din primele lecții, înaintea oricărei structuri de date.
Clasele de complexitate pe care le întâlnești des
Majoritatea algoritmilor pe care îi scrii la început se încadrează în șase clase. Tabelul arată, orientativ, câți pași face fiecare pentru 1.000 și pentru 1.000.000 de elemente.
| Notație | Nume | Exemplu tipic | n = 1.000 | n = 1.000.000 |
|---|---|---|---|---|
| O(1) | constantă | accesezi lista[5] sau o cheie dintr-un dicționar | 1 | 1 |
| O(log n) | logaritmică | căutare binară într-o listă sortată | ~10 | ~20 |
| O(n) | liniară | parcurgi o listă o dată (suma, maximul) | 1.000 | 1.000.000 |
| O(n log n) | liniar-logaritmică | sortări eficiente (merge sort, sorted() în Python) | ~10.000 | ~20.000.000 |
| O(n²) | pătratică | două bucle imbricate pe aceeași listă | 1.000.000 | 1.000.000.000.000 |
| O(2ⁿ) | exponențială | toate submulțimile unei liste, Fibonacci recursiv naiv | imposibil | imposibil |
Uită-te la ultimele două rânduri. Un trilion de pași înseamnă ore sau zile chiar pe un calculator rapid. De aceea, când datele cresc, trecerea de la O(n²) la O(n log n) sau O(n) e cea mai valoroasă optimizare pe care o poți face.
Cum calculezi Big O pentru codul tău
Ca să afli complexitatea unei funcții, numeri de câte ori se repetă operațiile în raport cu n, apoi păstrezi doar termenul care crește cel mai repede. Patru reguli acoperă aproape toate cazurile de început:
- O buclă peste n elemente înseamnă O(n). Contează câte iterații face, nu câte linii are corpul buclei.
- Buclele imbricate se înmulțesc. O buclă în altă buclă, ambele peste n, dă O(n × n) = O(n²).
- Pașii succesivi se adună, apoi rămâne cel mai mare. O buclă O(n) urmată de una O(n²) dă O(n + n²), adică O(n²).
- Constantele dispar. Două parcurgeri ale listei înseamnă O(2n), dar se scrie O(n). Big O descrie forma creșterii, nu numărul exact de pași.
Mai e un tipar de reținut: dacă la fiecare pas înjumătățești problema (căutarea binară, un arbore echilibrat), ai O(log n). Logaritmul răspunde la întrebarea „de câte ori pot împărți n la 2 până ajung la 1?”.
Atenție și la funcțiile gata făcute. Operația x in lista pare un singur pas, dar Python parcurge lista element cu element, deci e O(n). Aceeași operație pe un set sau un dict e, în medie, O(1). Tabelul oficial cu complexitatea operațiilor din Python e o resursă bună de ținut la îndemână.
Exemplu în Python: căutare liniară vs căutare binară
Cel mai clar mod de a vedea Big O e să numeri pașii. Programul de mai jos caută ultimul număr dintr-o listă sortată, o dată element cu element și o dată prin înjumătățire, și afișează câți pași a făcut fiecare metodă.
def cautare_liniara(lista, x):
pasi = 0
for element in lista:
pasi += 1
if element == x:
break
return pasi
def cautare_binara(lista, x):
pasi = 0
st, dr = 0, len(lista) - 1
while st <= dr:
pasi += 1
mij = (st + dr) // 2
if lista[mij] == x:
break
if lista[mij] < x:
st = mij + 1
else:
dr = mij - 1
return pasi
for n in (1_000, 1_000_000):
numere = list(range(n))
cel_mai_rau = n - 1 # ultimul element: cazul cel mai nefavorabil
print(f"n = {n}: liniară {cautare_liniara(numere, cel_mai_rau)} pași, "
f"binară {cautare_binara(numere, cel_mai_rau)} pași") Rezultatul:
n = 1000: liniară 1000 pași, binară 10 pași
n = 1000000: liniară 1000000 pași, binară 20 pași Când lista crește de o mie de ori, căutarea liniară face de o mie de ori mai mulți pași. Căutarea binară face doar 10 pași în plus. Asta e diferența dintre O(n) și O(log n), văzută cu ochii tăi. Condiția e ca lista să fie sortată; în Python, modulul bisect îți oferă căutarea binară gata scrisă.
Exemplu de optimizare: de la O(n²) la O(n)
Cea mai frecventă îmbunătățire la interviu este înlocuirea a două bucle imbricate cu un set sau un dicționar. Problema: verifici dacă o listă conține valori duplicate, de exemplu CNP-uri introduse de două ori într-un formular de înscriere.
import time
def are_dubluri_lent(lista): # O(n²)
for i in range(len(lista)):
for j in range(i + 1, len(lista)):
if lista[i] == lista[j]:
return True
return False
def are_dubluri_rapid(lista): # O(n)
vazute = set()
for x in lista:
if x in vazute:
return True
vazute.add(x)
return False
date = list(range(10_000))
for f in (are_dubluri_lent, are_dubluri_rapid):
t = time.perf_counter()
rezultat = f(date)
print(f"{f.__name__}: {rezultat}, {time.perf_counter() - t:.4f} s") Pe un laptop obișnuit, pentru 10.000 de elemente fără dubluri, varianta lentă durează în jur de 1–3 secunde, iar cea rapidă sub o milisecundă. Valorile exacte diferă de la calculator la calculator, dar raportul rămâne uriaș.
Varianta lentă compară fiecare element cu toate cele de după el, aproximativ n²/2 comparații, adică O(n²). Varianta rapidă parcurge lista o singură dată și ține minte ce a văzut într-un set, unde verificarea e O(1) în medie. Ai plătit cu memorie (setul poate ajunge la n elemente, deci O(n) spațiu) ca să câștigi timp. Acest schimb timp contra memorie apare în foarte multe probleme de interviu.
Complexitatea de spațiu și cazurile best, average, worst
Complexitatea de spațiu măsoară câtă memorie suplimentară folosește algoritmul pe măsură ce crește n. Se scrie tot cu Big O. Funcția are_dubluri_rapid are O(n) spațiu din cauza setului, iar are_dubluri_lent are O(1), pentru că folosește doar câteva variabile.
Pe lângă spațiu, mai auzi de trei cazuri. Cazul cel mai bun (best case) e când ai noroc: elementul căutat e primul din listă. Cazul mediu (average case) descrie comportamentul obișnuit. Cazul cel mai nefavorabil (worst case) e situația cea mai proastă posibilă. Când cineva spune doar „căutarea liniară e O(n)”, se referă aproape mereu la worst case, pentru că acolo ai garanția că nu poate fi mai rău.
Cum răspunzi la interviu despre complexitate
La interviu, spune complexitatea de timp și pe cea de spațiu și explică de unde vin, într-o propoziție fiecare. De exemplu: „Soluția e O(n) ca timp, pentru că parcurg lista o singură dată, și O(n) ca spațiu, din cauza setului în care țin elementele văzute.”
Câteva obiceiuri care fac diferența:
- Pornește de la soluția directă, chiar dacă e O(n²), spune-i complexitatea, apoi propune îmbunătățirea.
- Numește structura care te ajută: set sau dicționar pentru căutări rapide, listă sortată pentru căutare binară, heap pentru „cele mai mari k elemente”.
- Nu uita de operațiile ascunse: un
sort()în interiorul unei bucle sau uninpe o listă schimbă complexitatea totală. - Dacă nu ești sigur, numără cu voce tare: „bucla exterioară merge de n ori, cea interioară tot de n ori, deci n pătrat”.
Greșeli frecvente când înveți Big O
Cea mai des întâlnită greșeală este să confunzi Big O cu viteza în secunde. Un algoritm O(n²) poate fi mai rapid decât unul O(n) pe 10 elemente, pentru că Big O ignoră constantele. Contează când datele cresc.
A doua greșeală e să crezi că o singură linie de cod înseamnă O(1). lista.index(x), x in lista sau lista.remove(x) parcurg lista în spate. A treia: să numeri buclele imbricate fără să te uiți pe ce iterează. Două bucle una în alta, una peste n elemente și una peste un număr fix de 26 de litere, înseamnă O(26n) = O(n), nu O(n²).
Exercițiu pentru tine
Ce complexitate are funcția de mai jos, care primește notele de la BAC ale unei clase și returnează câte note sunt peste media clasei?
def peste_medie(note):
media = sum(note) / len(note)
return len([n for n in note if n > media]) Răspuns: O(n) ca timp, pentru că sum parcurge lista o dată și list comprehension-ul încă o dată (O(2n) devine O(n)), și O(n) ca spațiu din cauza listei construite. Poți coborî spațiul la O(1) dacă înlocuiești lista cu un contor: sum(1 for n in note if n > media).
Întrebări frecvente
Ce înseamnă O(n) în programare?
O(n) înseamnă complexitate liniară: numărul de pași crește în același ritm cu numărul de elemente. Dacă lista se dublează, și timpul se dublează, aproximativ. Exemplul clasic este parcurgerea unei liste ca să găsești maximul.
Care este cea mai bună complexitate a unui algoritm?
O(1) este cea mai bună, pentru că timpul nu depinde de volumul datelor. În practică, „cea mai bună” depinde de problemă: o sortare bazată pe comparații nu poate coborî în general sub O(n log n), deci acolo O(n log n) e optimul.
Trebuie să știu matematică pentru Big O?
Nu mai mult decât înmulțirea și ideea de logaritm. La început îți ajunge să știi că log n crește foarte încet (log₂ dintr-un milion e aproximativ 20). Restul e numărat bucle și recunoscut tipare.
Big O se întreabă și la interviurile pentru junior?
Da, de cele mai multe ori. Chiar dacă problema e simplă, ți se poate cere să spui complexitatea soluției și cum ai îmbunătăți-o. Nu e nevoie de demonstrații formale, ci de o explicație clară.
Care e diferența dintre O(n log n) și O(n²)?
Pentru un milion de elemente, O(n log n) înseamnă în jur de 20 de milioane de pași, iar O(n²) un trilion. Prima rulează în fracțiuni de secundă, a doua poate dura ore. Diferența dintre o sortare eficientă și una naivă (bubble sort) e exact aceasta.
Primul pas: numără pașii în propriul tău cod
Ia ultima funcție pe care ai scris-o și notează lângă fiecare buclă de câte ori se execută. Apoi scrie complexitatea finală și verific-o cu un contor, ca în exemplele de mai sus. Dacă vrei să exersezi sistematic, cursul de algoritmi pentru interviuri are 150 de lecții în care fiecare problemă rezolvată în browser vine cu complexitatea soluției explicată și cu teste automate, inclusiv pe cazuri limită.
Dacă abia începi cu programarea, pornește cu cursul de Python, unde primele 15 lecții sunt gratuite: algoritmii devin mult mai ușori când listele, dicționarele și buclele îți sunt familiare. Iar dacă te atrag datele și modelele de machine learning, unde complexitatea contează la fiecare pas, uită-te pe traseul Data Scientist / ML Engineer. Pentru bazele teoretice, citește și explicația despre ce este un algoritm.
Curs Python
Programare Python pentru începători, cu exerciții practice în browser
Începe gratuit
