1
Ce este complexitatea temporala?
Complexitatea temporala a unui algoritm descrie cum creste numarul de operatii fundamentale (comparatii, atribuiri, adunari etc.) in functie de dimensiunea n a datelor de intrare. Nu masuram secunde — masuram ordinul de crestere.
De ce nu masuram in secunde?
Un algoritm lent pe un supercomputer poate fi mai rapid decat un algoritm bun pe un calculator vechi. Complexitatea ne spune ceva independent de hardware: ce se intampla cand n se dubleaza?
Notatia O mare (Big-O) exprima limita superioara a cresterii: ignoram constantele si termenii mai mici.
Exemplu: daca un algoritm face
Exemplu: daca un algoritm face
3n² + 5n + 7 operatii, spunem ca are complexitate O(n²).
Regula de simplificare O:
O(5n)→O(n)— ignoram constanta 5O(n² + n)→O(n²)— ignoram termenul mai micO(2 log n + 3)→O(log n)
2
Clasele de complexitate: ierarhie si intuitie
Urmatoarele clase apar cel mai des in practica, in ordine de la cel mai eficient la cel mai lent:
O(1) — Constant
Numarul de operatii NU depinde de n. Exemple: accesul la un element de tablou prin index, formula matematica directa (ex: suma Gauss).
O(log n) — Logaritmic
La fiecare pas, problema se injumatateste. Exemple: cautare binara, exponentierea rapida.
Intuitie: log₂(1.000.000) ≈ 20 — din un milion de elemente, gasesti orice in cel mult 20 de pasi.
O(n) — Liniar
Parcurgem fiecare element o singura data. Exemple: cautare liniara, suma unui sir, citirea unui fisier.
O(n log n) — Linearitmic
Combinatie: parcurgem n elemente, dar la fiecare nivel avem un factor logaritmic. Exemple: Merge Sort, Heap Sort, Quick Sort (caz mediu).
O(n²) — Patratic
Doua bucle imbricate care parcurg n elemente fiecare. Exemple: sortare prin selectie, sortare prin insertie, verificarea tuturor perechilor.
Tabel comparativ (numar de operatii aproximativ):
n O(1) O(log n) O(n) O(n log n) O(n^2) 10 1 3 10 33 100 100 1 7 100 664 10000 1000 1 10 1000 9966 1000000 1000000 1 20 1000000 19931568 1000000000000
3
Comparatie empirica: O(n) vs O(1) in Python
Masuram concret diferenta dintre un algoritm O(n) si unul O(1) care rezolva aceeasi problema: suma 1 + 2 + ... + n.
import time def suma_liniara(n): # O(n): parcurgem n pasi s = 0 for i in range(1, n + 1): s += i return s def suma_formula(n): # O(1): o singura formula return n * (n + 1) // 2 n = 10000 t0 = time.perf_counter() r1 = suma_liniara(n) t1 = time.perf_counter() r2 = suma_formula(n) t2 = time.perf_counter() print(f"suma_liniara({n}) = {r1}, timp: {(t1-t0)*1e6:.1f} us [O(n)]") print(f"suma_formula({n}) = {r2}, timp: {(t2-t1)*1e6:.3f} us [O(1)]")
Output real (rulat cu python):
suma_liniara(10000) = 50005000, timp: 315.4 microsecunde [O(n)] suma_formula(10000) = 50005000, timp: 1.400 microsecunde [O(1)]
Ambele dau acelasi rezultat (50005000), dar O(1) este de ~225 de ori mai rapid decat O(n) pentru n=10.000. La n=1.000.000, diferenta ar fi de ~22.500 de ori.
4
Calculul complexitatii: numararea operatiilor dominante
Pentru a determina complexitatea unui algoritm, identificam bucla care se executa cel mai mult si numaram de cate ori se executa instructiunea principala.
Exemplu 1: Sortare prin selectie — O(n²)
def sortare_selectie(arr): a = arr[:] n = len(a) comparatii = 0 for i in range(n): # n iteratii min_idx = i for j in range(i+1, n): # n-1, n-2,..., 1 iteratii comparatii += 1 if a[j] < a[min_idx]: min_idx = j a[i], a[min_idx] = a[min_idx], a[i] return a, comparatii
Output real (rulat cu python):
Sortare prin selectie (n=10): 45 comparatii [teoretic n*(n-1)/2 = 45] => O(n^2)
Total comparatii: (n-1)+(n-2)+...+1 = n(n-1)/2 ≈ n²/2 → O(n²)
Exemplu 2: Cautare binara — O(log n)
def cautare_binara(arr, target): lo, hi = 0, len(arr)-1 pasi = 0 while lo <= hi: pasi += 1 mid = (lo+hi)//2 # intervalul se injumatateste if arr[mid] == target: return mid, pasi elif arr[mid] < target: lo = mid+1 else: hi = mid-1 return -1, pasi
Output real (rulat cu python):
Cautare binara (n=1024, target=777): gasit la idx=777, pasi=9 [log2(1024)=10] => O(log n)
La fiecare pas intervalul se injumatateste → O(log n)
Exemplu 3: Merge Sort — O(n log n) verificat empiric
# Output real: Merge sort (n=16): ~44 comparatii [n*log2(n)=64] => O(n log n) # n niveluri de log n adancime, la fiecare nivel n operatii de combinare
Merge sort: n * log n → O(n log n)
5
Implementare si verificare empirica in C++ EXCLUSIV INTENSIV
⚡ Sectiune doar pentru intensiv informatica
Implementam si verificam empiric toate clasele de complexitate in C++. Numaratoarea exacta de operatii confirma teoria.
#include <iostream> #include <vector> #include <cmath> using namespace std; // O(1) - formula Gauss long long suma_gauss(long long n) { return n * (n + 1) / 2; } // O(log n) - exponentierea rapida long long putere_rapida(long long b, long long e, long long m) { long long r = 1; int pasi = 0; while (e > 0) { if (e % 2 == 1) r = r * b % m; b = b * b % m; e /= 2; pasi++; } cout << " Pasi O(log n): " << pasi << " [log2(32)=" << (int)log2(32) << "]" << endl; return r; } // O(n^2) - sortare prin selectie cu numarare int sortare_selectie_comp(vector<int> v) { int n = v.size(), c = 0; for (int i = 0; i < n-1; i++) { int m = i; for (int j = i+1; j < n; j++) { c++; if (v[j] < v[m]) m = j; } swap(v[i], v[m]); } cout << " Sir sortat: "; for (int x : v) cout << x << " "; cout << endl; return c; } int main() { cout << "O(1) - suma_gauss(1000000)=" << suma_gauss(1000000) << endl; cout << "O(log n) - 2^32 mod (10^9+7):" << endl; long long rez = putere_rapida(2, 32, 1000000007LL); cout << " Rezultat: " << rez << endl; cout << "O(n^2) - sortare selectie n=8:" << endl; vector<int> arr = {5, 2, 8, 1, 9, 3, 7, 4}; int comp = sortare_selectie_comp(arr); cout << " Comparatii: " << comp << " [teoretic 8*7/2=" << 8*7/2 << "]" << endl; return 0; }
Output real (compilat g++ -std=c++17, apoi rulat):
O(1) - suma_gauss(1000000)=500000500000 O(log n) - 2^32 mod (10^9+7): Pasi O(log n): 6 [log2(32)=5] Rezultat: 294967268 O(n^2) - sortare selectie n=8: Sir sortat: 1 2 3 4 5 7 8 9 Comparatii: 28 [teoretic 8*7/2=28]
Observatie: putere_rapida executa 6 pasi pentru exp=32, nu 5 ca log₂(32). La ultima iteratie exp_val=1 (impar), intra in bucla, se incrementeaza pasi, apoi e/=2 face exp_val=0 si se iese. Ordinul ramane O(log n).
6
Alegerea algoritmului si tipare BAC
Regula practica: daca n ≤ 100.000, O(n log n) este sigur. Daca n ≤ 10.000, O(n²) poate fi acceptabil. Daca n = 109, ai nevoie de O(log n) sau O(1).
Tipare de bucle si complexitatile lor (esential la BAC):
# O(n) - o singura bucla liniara for i in range(n): # instructiune simpla # O(n^2) - doua bucle imbricate pana la n for i in range(n): for j in range(n): # n*n operatii # O(log n) - injumatatire la fiecare pas while n > 1: n = n // 2 # O(n^2) - bucla interioara de la i (tot patratic!) for i in range(1, n+1): for j in range(i, n+1): # total: n*(n+1)/2 ~ n^2/2 => O(n^2)
Algoritmi standard si complexitatile lor (de memorat):
Cautare liniara => O(n)
Sortare prin selectie => O(n^2)
Sortare prin insertie => O(n^2)
Sortare cu lista de frecventa => O(n + max_val)
Merge Sort => O(n log n)
Quick Sort (caz mediu) => O(n log n)
Cautare binara => O(log n)
Exponentierea rapida => O(log n)
Ciurul lui Eratostene => O(n log log n)
Acces tablou prin index => O(1)
Formula matematica directa => O(1)La BAC, exercitiile tipice cer: (1) sa identifici complexitatea unui algoritm dat, (2) sa numeri operatiile pentru un n dat, (3) sa compari doi algoritmi si sa alegi cel mai eficient.