Complexitatea Algoritmilor C++ — Notația Big O

De Ce Contează Complexitatea?

Complexitatea algoritmică măsoară eficiența unui algoritm în funcție de dimensiunea datelor de intrare (n). Un algoritm bun trebuie să fie corect și eficient.

La BAC informatică și titularizare, înțelegerea complexității te ajută să:

• •Alegi algoritmul potrivit pentru problema dată
• •Estimezi dacă soluția ta se încadrează în limitele de timp
• •Demonstrezi că știi teoria algoritmilor

Ordinele de Complexitate (de la cel mai rapid la cel mai lent)

Exemple Practice de Complexitate

O(1) — Timp Constant

Copiază
1int primaElement(int arr[]) { return arr[0]; }  // O(1)
2int suma(int a, int b) { return a + b; }         // O(1)

O(log n) — Logaritmică

Copiază
1// Căutare binară — O(log n)
2int binarySearch(int arr[], int n, int target) {
3    int st = 0, dr = n - 1;
4    while (st <= dr) {            // se execută log2(n) ori
5        int mij = (st + dr) / 2;
6        if (arr[mij] == target) return mij;
7        else if (arr[mij] < target) st = mij + 1;
8        else dr = mij - 1;
9    }
10    return -1;
11}

O(n) — Liniară

Copiază
1// Suma elementelor — O(n)
2int suma(int arr[], int n) {
3    int s = 0;
4    for (int i = 0; i < n; i++) s += arr[i];  // n iterații
5    return s;
6}

O(n log n) — Liniară-Logaritmică

Copiază
1// std::sort — O(n log n)
2sort(arr, arr + n);  // cel mai bun algoritm de sortare general
3
4// MergeSort — O(n log n) garantat

O(n²) — Pătratică

Copiază
1// Bubble Sort — O(n²)
2for (int i = 0; i < n; i++)
3    for (int j = 0; j < n-i-1; j++)  // n * n/2 = O(n²)
4        if (arr[j] > arr[j+1])
5            swap(arr[j], arr[j+1]);
6
7// Parcurgerea unei matrice — O(n²)
8for (int i = 0; i < n; i++)
9    for (int j = 0; j < n; j++)
10        cout << mat[i][j];

Limite de Timp la BAC Informatică

La BAC, limita de timp este în general 1 secundă. Regulă de bază:

• •10⁸ operații/secundă pe un calculator modern
• •Dacă n = 1000 → O(n²) = 10⁶ → ✅ OK
• •Dacă n = 100.000 → O(n²) = 10¹⁰ → ❌ TLE (Time Limit Exceeded)
• •Dacă n = 100.000 → O(n log n) ≈ 1.7 × 10⁶ → ✅ OK

Complexitatea Spațiului (Space Complexity)

Pe lângă timp, algoritmii folosesc și memorie:

Copiază
1int arr[1000];          // O(n) spațiu
2int mat[100][100];      // O(n²) spațiu
3// Recursivitate adâncă → O(adâncime) pe stivă

Reguli de Calcul Big O

1. •Elimini constantele: O(2n) = O(n)
2. •Păstrezi termenul dominant: O(n² + n) = O(n²)
3. •Secvențe: O(n) + O(n) = O(n)
4. •Bucle imbricate: O(n) × O(n) = O(n²)