📊 Eficiența și Complexitatea Algoritmilor

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.

Analizăm două tipuri:

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

Reguli de simplificare

Clasă	n = 10	n = 100	n = 1000	n = 10⁶
O(1)	1	1	1	1
O(log n)	~3	~7	~10	~20
O(n)	10	100	1 000	1 000 000
O(n log n)	~33	~664	~10 000	~2×10⁷
O(n²)	100	10 000	10⁶	10¹²
O(2ⁿ)	1 024	10³⁰	10³⁰⁰	∞

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)
}

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;

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

// 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

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)	✅

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
}

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.