📊 Eficiența și Complexitatea Algoritmilor

Capitolul 2 — Notații asimptotice, clase de complexitate, analiza algoritmilor de sortare

Big-OBubble SortCăutare binarăSortareComplexitate spațiu
📖 12 min
0
📏

Ce înseamnă eficiența unui algoritm?

📚 Analogie: De ce contează eficiența?

Imaginează-ți că vrei să găsești un cuvânt într-un dicționar cu 1.000.000 de cuvinte:

  • 🐢 Verifici pagină cu pagină de la început → maxim 1.000.000 pași → O(n)
  • 🚀 Cauți la mijloc, elimini jumătate (căutare binară) → maxim 20 pași → O(log n)

Pe 1 miliard de elemente: O(n) = 1 miliard de operații, O(log n) = doar 30. Eficiența contează enorm!

Un algoritm este o secvență finită, bine definită de pași care rezolvă o problemă. Două algoritme diferite pot rezolva același lucru, dar cu costuri diferite de timp și memorie.
Definiție: Complexitatea unui algoritm este o funcție care descrie creșterea resurselor necesare (timp sau spațiu) în funcție de dimensiunea datelor de intrare n.

Analizăm două tipuri:

Complexitate timp

Numărul de operații elementare executate

Complexitate spațiu

Memoria suplimentară utilizată de algoritm

De reținut: La BAC se analizează de obicei cazul cel mai defavorabil (worst case) și complexitatea timp.
Ο

Notații asimptotice: O, Ω, Θ

Notațiile asimptotice descriu comportamentul unui algoritm pentru n → ∞, ignorând constantele și termenii de ordin inferior.

O(g(n)) — Big-O
Limita superioară (worst case)
f(n) ≤ c · g(n) pentru n ≥ n₀
Ω(g(n)) — Omega
Limita inferioară (best case)
f(n) ≥ c · g(n) pentru n ≥ n₀
Θ(g(n)) — Theta
Limita exactă (tight bound)
c₁·g(n) ≤ f(n) ≤ c₂·g(n)
Exemplu concret: Dacă avem T(n) = 5n² + 3n + 12, atunci: T(n) = O(n²) — T(n) = Ω(n²) — T(n) = Θ(n²)

Reguli de simplificare

Elimină constantele multiplicative: O(5n) = O(n)
Elimină termenii de ordin inferior: O(n² + n) = O(n²)
Suma: max(O(f), O(g)) = O(max(f, g))
Produs: O(f) · O(g) = O(f · g)
📊

Clase de complexitate

O(1)
Ideal
O(log n)
Excelent
O(n)
Bun
O(n log n)
Acceptabil
O(n²)
Slab
O(n³)
Rău
O(2ⁿ)
Impracticabil
Ierarhie: O(1) < O(log n) < O(√n) < O(n) < O(n log n) < O(n²) < O(n³) < O(2ⁿ) < O(n!)
Clasăn = 10n = 100n = 1000n = 10⁶
O(1)1111
O(log n)~3~7~10~20
O(n)101001 0001 000 000
O(n log n)~33~664~10 000~2×10⁷
O(n²)10010 00010⁶10¹²
O(2ⁿ)1 02410³⁰10³⁰⁰∞

📈 Grafic interactiv Big-O

🔁

Complexitate timp — exemple practice

O(1) — Acces la element în tablou

int x = v[5];   // O(1) — acces direct, indiferent de n
int suma = a + b;  // O(1) — operație aritmetică

O(n) — Parcurgere simplă

for (int i = 0; i < n; i++) {
    cout << v[i];  // executat de n ori → O(n)
}

O(n²) — Bucle imbricate

for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++)
        suma += v[i] * v[j];  // n × n = n² operații

O(log n) — Căutare binară

int cautareBinara(int v[], int n, int x) {
    int st = 0, dr = n - 1;
    while (st <= dr) {
        int mij = (st + dr) / 2;
        if (v[mij] == x) return mij;
        else if (v[mij] < x) st = mij + 1;
        else dr = mij - 1;
    }
    return -1;
    // la fiecare pas intervalul se înjumătățește → O(log n)
}
Regulă practică: Numărul de bucle imbricate de câte n ori determină gradul: 1 buclă → O(n), 2 bucle → O(n²), 3 bucle → O(n³).

Analiza corectă — cazuri speciale

// Două bucle SEPARATE (nu imbricate) → O(n) + O(n) = O(n)
for (int i = 0; i < n; i++) suma1 += v[i];
for (int i = 0; i < n; i++) suma2 += v[i];
// Total: O(n), nu O(n²)
// Jumătate din n la fiecare pas → log₂n pași → O(log n)
while (n > 1) n /= 2;
💾

Complexitate spațiu

Complexitatea spațiu se referă la memoria suplimentară folosită de algoritm (nu se numără inputul în sine).

O(1) — spațiu constant

Algoritmul folosește doar câteva variabile auxiliare, indiferent de n

Exemplu: bubble sort in-place
O(n) — spațiu liniar

Se alocă un tablou auxiliar de dimensiune n

Exemplu: merge sort (tablou temp) 
// O(1) spațiu — sortare prin selecție, in-place
for (int i = 0; i < n-1; i++) {
    int minIdx = i;
    for (int j = i+1; j < n; j++)
        if (v[j] < v[minIdx]) minIdx = j;
    swap(v[i], v[minIdx]);  // O(1) memorie extra
}
// O(n) spațiu — copiere tablou
int copie[100001];
for (int i = 0; i < n; i++) copie[i] = v[i];  // n elemente suplimentare
Recursivitatea consumă spațiu pe stivă: O(adâncimea recursiei). Factorial(n) → O(n) spațiu pe stivă.
🔀

Algoritmi de sortare — comparație

Algoritm Best Average Worst Spațiu Stabil
Bubble Sort O(n) O(n²) O(n²) O(1) ✅
Selection Sort O(n²) O(n²) O(n²) O(1) ❌
Insertion Sort O(n) O(n²) O(n²) O(1) ✅
Merge Sort O(n log n) O(n log n) O(n log n) O(n) ✅
Quick Sort O(n log n) O(n log n) O(n²) O(log n) ❌
Heap Sort O(n log n) O(n log n) O(n log n) O(1) ❌
Counting Sort O(n+k) O(n+k) O(n+k) O(k) ✅
La BAC se cer de obicei Bubble Sort și Selection Sort. Cunoaște codul și complexitatea O(n²) pentru ambele.

📊 Comparație algoritmi de sortare

Bubble Sort — implementare C++

void bubbleSort(int v[], int n) {
    for (int i = 0; i < n-1; i++) {
        bool swap_facut = false;
        for (int j = 0; j < n-i-1; j++) {
            if (v[j] > v[j+1]) {
                swap(v[j], v[j+1]);
                swap_facut = true;
            }
        }
        if (!swap_facut) break;  // optimizare: șirul deja sortat
    }
    // Complexitate: O(n²) worst/average, O(n) best
}

Selection Sort — implementare C++

void selectionSort(int v[], int n) {
    for (int i = 0; i < n-1; i++) {
        int minIdx = i;
        for (int j = i+1; j < n; j++)
            if (v[j] < v[minIdx]) minIdx = j;
        if (minIdx != i) swap(v[i], v[minIdx]);
    }
    // Complexitate: O(n²) în toate cazurile
}
🎬

Animație — Bubble Sort

Apasă Start pentru a vedea cum funcționează Bubble Sort pas cu pas. Barele de culoare portocalie sunt comparate, cele verzi sunt la locul final.

🧩

Probleme rezolvate — analiza complexității

5 exerciții cu analiza pas cu pas a complexității timp și spațiu.

1 Două bucle imbricate independente Ușor
Calculează complexitatea timp a fragmentului:
Cod:
for (i = 1; i <= n; i++)
  for (j = 1; j <= m; j++)
    s++;
Răspuns:
O(n · m)
💡 Explicație

Bucla externă rulează exact n iterații. Pentru fiecare, bucla internă rulează m iterații. Total = n × m operații elementare. Dacă n = m, e O(n²).

2 Bucla pe i, internă pe i Ușor
Care este complexitatea?
Cod:
for (i = 1; i <= n; i++)
  for (j = 1; j <= i; j++)
    op();
Răspuns:
O(n²)
💡 Explicație

Numărul total de operații = 1 + 2 + 3 + ... + n = n(n+1)/2. În notație asimptotică ignoram constantele și termenii inferiori ⇒ O(n²).

3 Bucla cu înjumătățire Mediu
Care este complexitatea?
Cod:
i = n;
while (i > 0) {
  for (j = 1; j <= n; j++) op();
  i = i / 2;
}
Răspuns:
O(n log n)
💡 Explicație

Bucla while rulează log₂ n iterații (i se înjumătățește). Bucla for internă rulează n operații. Total = n · log n. Acesta este și complexitatea sortărilor optime (merge sort, heap sort, quicksort mediu).

4 Trei bucle imbricate Mediu
Calculează complexitatea pentru produsul a două matrici n × n:
Cod:
for (i = 1; i <= n; i++)
  for (j = 1; j <= n; j++) {
    c[i][j] = 0;
    for (k = 1; k <= n; k++)
      c[i][j] += a[i][k] * b[k][j];
  }
Răspuns:
O(n³)
💡 Explicație

Trei bucle imbricate, fiecare cu n iterații ⇒ n × n × n = n³ operații. Pentru n = 1000 ⇒ 10⁹ operații — la limita timpului obișnuit de 1 s. Există algoritmi sub-cubici (Strassen O(n^2.81)), dar la BAC algoritmul clasic e ok.

5 Recurența T(n) = T(n/2) + O(1) Dificil
Care este complexitatea unei funcții recursive cu recurența T(n) = T(n/2) + O(1)? Dă un exemplu.
Recurență:
T(n) = T(n/2) + O(1)
T(1) = O(1)
Răspuns:
O(log n)
💡 Explicație

Desfășurăm: T(n) = T(n/2) + c = T(n/4) + 2c = T(n/8) + 3c = ... = T(1) + c·log₂n = O(log n). Exemplu: cautareBinaraRec(v, st, dr, x) — la fiecare apel reduce intervalul la jumătate.

Comparație rapidă (Master Theorem): T(n) = 2T(n/2) + O(n) ⇒ O(n log n) (merge sort); T(n) = T(n−1) + O(1) ⇒ O(n) (factorial).

💡 Sfat: pentru BAC focusează-te pe O(1), O(log n), O(n), O(n log n), O(n²), O(n³), O(2ⁿ), O(n!).
📝

Probleme tip BAC — rezolvate

Problemă 1 (BAC 2023): Determina complexitatea timp a algoritmului următor: 
for(i=1; i<=n; i++)
  for(j=1; j<=i; j++)
    s = s + i*j;
Soluție: Bucla exterioară rulează n ori. Bucla interioară rulează 1, 2, 3, ... n ori. Total operații = 1 + 2 + ... + n = n(n+1)/2 ≈ n²/2. Deci complexitatea este O(n²).
Problemă 2: Care este complexitatea algoritmului următor? 
i = n;
while(i > 1) i = i / 2;
Soluție: La fiecare pas i se înjumătățește. Numărul de pași ≈ log₂(n). Complexitatea este O(log n).
Problemă 3: Se dă un vector cu n elemente. Scrie un algoritm O(n) care verifică dacă există duplicate.
Soluție (vector de frecvență): 
int freq[1001] = {0};
bool duplicat = false;
for(int i = 0; i < n; i++) {
    freq[v[i]]++;
    if(freq[v[i]] > 1) { duplicat = true; break; }
}
// O(n) timp, O(k) spațiu unde k = domeniu valori
📚

Referințe și resurse

Continuare după BAC

UPB — Facultatea de Automatică
UniBuc — Facultatea de Matematică-Informatică
UBB Cluj — Informatică
TUIASI Iași — Calculatoare

Practică & Probleme

pbinfo.ro — probleme BAC & olimpiadă
infoarena.ro — concursuri RO
LeetCode — pregătire interviuri IT
HackerRank — exerciții structurate

Resurse internaționale

VisuAlgo — animații algoritmi
bigocheatsheet.com
cppreference.com — referință C++
Khan Academy

💪

Exercitii interactive - testeaza cunostintele