Ce este analiza asimptotica?
Analiza asimptotica descrie comportamentul unui algoritm pe masura ce marimea inputului tinde la infinit. Cele trei notatii principale sunt:
- Big O (O) — limita superioara: algoritmul nu va fi mai prost decat atat
- Big Omega (Ω) — limita inferioara: algoritmul nu va fi mai bun decat atat
- Big Theta (Θ) — limita stransa: algoritmul e exact atat
Exemplu: Pentru cautarea binara intr-un array de n elemente:
- Cel mai bun caz: Ω(1) — elementul e la mijloc
- Cel mai rau caz: O(log n) — elementul nu exista
- Cazul mediu: Θ(log n)
Complexitati comune si exemple
| Notatie | Nume | Exemplu | Demonstrație |
|---|---|---|---|
| O(1) | Constanta | Acces array | a[i] |
| O(log n) | Logaritmic | Căutare binară | T(n) = T(n/2) + O(1) |
| O(n) | Liniar | Parcurgere | T(n) = n |
| O(n log n) | Lin-log | MergeSort | T(n) = 2T(n/2) + O(n) |
| O(n^2) | Patratic | BubbleSort | T(n) = n(n-1)/2 |
| O(2^n) | Exponențial | Subseturi | T(n) = 2T(n-1) |
Reguli de calcul
- Adunarea: f(n) + g(n) = O(max(f(n), g(n))) — pastreaza termenul dominant
- Inmultirea: O(f(n)) · O(g(n)) = O(f(n) · g(n))
- Compozitia: buclele imbricate se inmultesc
- Recursia: se rezolva prin teorema master sau arbore de recursie
Cazuri speciale in analiza
Cazul cel mai rau vs cazul mediu
QuickSort are cazul cel mai rau O(n^2), dar cazul mediu O(n log n). In practica, varianta randomizata face ca O(n^2) sa aiba probabilitate neglijabila.
Analiza amortizata
Pentru operatii care sunt scumpe ocazional, analiza amortizata da costul mediu per operatie. Exemplu: inserarea intr-un Dynamic Array (Vector) e O(1) amortizat, desi redimensionarea e O(n).
Notatia Little o
o(f(n)) — creste strict mai lent decat f(n). Diferenta fata de O: o(n^2) NU include n^2, doar n^1.99, n log n, etc.
Teorema Master
Pentru recurente de forma T(n) = a·T(n/b) + f(n):
Cazul 1: f(n) = O(n^(log_b a - ε)) → T(n) = Θ(n^(log_b a)) Cazul 2: f(n) = Θ(n^(log_b a) · log^k n) → T(n) = Θ(n^(log_b a) · log^(k+1) n) Cazul 3: f(n) = Ω(n^(log_b a + ε)) si a·f(n/b) ≤ c·f(n) → T(n) = Θ(f(n))
Limite fundamentale
Orice algoritm de sortare prin comparatii are limita inferioara Ω(n log n). Aceasta nu poate fi depasita — e o constrangere matematica, nu inginereasca.