Informaticăliceumediu
Complexitatea Algoritmilor C++ — Notație Big O pentru BAC
Înțelege complexitatea timpului și spațiului în C++: notația Big O, O(1), O(log n), O(n), O(n²). Esențial pentru BAC informatică și titularizare.
6 zile în urmă
0 vizualizări
45 minute
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)
| Complexitate | Denumire | Exemplu |
|---|---|---|
| O(1) | Constantă | Accesarea unui element din vector |
| O(log n) | Logaritmică | Căutare binară |
| O(n) | Liniară | Parcurgerea unui vector |
| O(n log n) | Liniară-logaritmică | MergeSort, QuickSort |
| O(n²) | Pătratică | BubbleSort, parcurgere matrice |
| O(n³) | Cubică | Floyd-Warshall |
| O(2ⁿ) | Exponențială | Backtracking naiv |
Exemple Practice de Complexitate
O(1) — Timp Constant
1int primaElement(int arr[]) { return arr[0]; } // O(1) 2int suma(int a, int b) { return a + b; } // O(1)
O(log n) — Logaritmică
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ă
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ă
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ă
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:
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
- •Elimini constantele: O(2n) = O(n)
- •Păstrezi termenul dominant: O(n² + n) = O(n²)
- •Secvențe: O(n) + O(n) = O(n)
- •Bucle imbricate: O(n) × O(n) = O(n²)
Tutorialul te-a ajutat?
Dacă ai nevoie de ajutor personalizat, găsește un profesor calificat pentru meditații
