Complexitate Computațională și Notația Asimptotică¶

De ce ne interesează complexitatea?¶

Imaginează-ți că ai doi algoritmi care rezolvă aceeași problemă. Pe un input de 100 de elemente, ambii rulează instant. Pe 10.000 de elemente, primul termină în 0.1 secunde, al doilea în 10 minute. Pe 1.000.000 de elemente, primul termină în 1 secundă, al doilea ar dura 11 zile.

Complexitatea nu este despre cât de rapid rulează un program pe un anumit computer — ci despre cum crește timpul de execuție pe măsură ce inputul devine mai mare. Este diferența dintre un algoritm care scalează și unul care nu.

Analiza Asimptotică¶

Analiza asimptotică ignoră constantele și termenii mici, concentrându-se pe comportamentul dominant pentru inputuri mari.

De ce ignorăm constantele? Pentru că:
- Un computer de 2x mai rapid reduce orice algoritm cu un factor constant
- Optimizările de compilator schimbă constantele fără a schimba algoritmul
- Ceea ce contează este rata de creștere, nu valoarea exactă

Notația Big-O (marginea superioară)¶

$f(n) = O(g(n))$ înseamnă că $f$ crește cel mult la fel de repede ca $g$:

$$\exists \; c > 0, \; n_0 \geq 0 \;\text{ a.î. } \; f(n) \leq c \cdot g(n), \quad \forall \; n \geq n_0$$

Exemplu concret: Fie $f(n) = 3n^2 + 7n + 15$. Afirmăm că $f(n) = O(n^2)$.

Demonstrație: Alegem $c = 25$ și $n_0 = 1$. Atunci $3n^2 + 7n + 15 \leq 3n^2 + 7n^2 + 15n^2 = 25n^2$ pentru $n \geq 1$. ✓

Notația Omega (marginea inferioară)¶

$f(n) = \Omega(g(n))$ înseamnă că $f$ crește cel puțin la fel de repede ca $g$:

$$\exists \; c > 0, \; n_0 \geq 0 \;\text{ a.î. } \; f(n) \geq c \cdot g(n), \quad \forall \; n \geq n_0$$

Notația Theta (margine strânsă)¶

$f(n) = \Theta(g(n))$ înseamnă că $f$ crește exact la fel de repede ca $g$:

$$f(n) = O(g(n)) \;\text{ și }\; f(n) = \Omega(g(n))$$

Big-O spune „cel mult atât", Omega spune „cel puțin atât", Theta spune „exact atât". În practică, când cineva zice „algoritmul e $O(n \log n)$", de obicei înseamnă $\Theta(n \log n)$.

Clase de Complexitate¶

Regulă practică: Un computer modern execută ~$10^8$ operații/secundă. Dacă $n = 10^6$, un algoritm $O(n^2)$ ar lua ~$10^{12} / 10^8 = 10.000$ secunde ≈ 2.7 ore. Un algoritm $O(n \log n)$ ar lua ~$0.2$ secunde.

Cum calculăm complexitatea¶

Regula 1: Bucle simple¶

Numărul de iterații determină complexitatea:

# O(n) — o singură buclă
for i in range(n):
    print(i)

# O(n²) — două bucle imbricate, fiecare O(n)
for i in range(n):
    for j in range(n):
        print(i, j)

# O(n³) — trei bucle imbricate
for i in range(n):
    for j in range(n):
        for k in range(n):
            print(i, j, k)

Regula 2: Bucle consecutive se adună¶

# O(n) + O(n²) = O(n²)
for i in range(n):       # O(n)
    print(i)

for i in range(n):       # O(n²)
    for j in range(n):
        print(i, j)

Se păstrează doar termenul dominant: $O(n) + O(n^2) = O(n^2)$.

Regula 3: Bucle imbricate se înmulțesc¶

# O(n) × O(m) = O(n·m)
for i in range(n):
    for j in range(m):
        print(i, j)

Regula 4: Înjumătățirea → logaritm¶

Când la fiecare pas înjumătățim inputul, complexitatea este $O(\log n)$:

# O(log n)
i = n
while i > 0:
    print(i)
    i = i // 2

De câte ori putem înjumătăți $n$ până ajungem la 1? De exact $\log_2 n$ ori.

Regula 5: Recursivitate¶

Pentru funcții recursive, scriem o relație de recurență și o rezolvăm.

def factorial(n):
    if n <= 1:
        return 1
    return n * factorial(n - 1)

$T(n) = T(n-1) + O(1) \implies T(n) = O(n)$

def fibonacci_naive(n):
    if n <= 1:
        return n
    return fibonacci_naive(n-1) + fibonacci_naive(n-2)

$T(n) = T(n-1) + T(n-2) + O(1) \implies T(n) = O(2^n)$ — exponențial! Extrem de ineficient.

Exemplu Detaliat: Căutarea Binară¶

Căutarea binară este unul dintre cei mai fundamentali algoritmi. Funcționează pe un array sortat și la fiecare pas elimină jumătate din candidați.

def binary_search(arr, target):
    left, right = 0, len(arr) - 1

    while left <= right:
        mid = left + (right - left) // 2  # evităm overflow

        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1   # target e în jumătatea dreaptă
        else:
            right = mid - 1  # target e în jumătatea stângă

    return -1  # nu a fost găsit

De ce left + (right - left) // 2 și nu (left + right) // 2? Pentru a evita overflow-ul în limbaje cu întregi de dimensiune fixă. Dacă left și right sunt ambele aproape de valoarea maximă a tipului int, suma lor ar depăși limita.

Analiză: La fiecare iterație, intervalul de căutare se înjumătățește:
- Start: $n$ elemente
- După 1 pas: $n/2$
- După 2 pași: $n/4$
- După $k$ pași: $n/2^k$
- Se oprește când $n/2^k = 1$, deci $k = \log_2 n$

Complexitate: $O(\log n)$ timp, $O(1)$ spațiu.

Variante utile ale căutării binare¶

def lower_bound(arr, target):
    """Primul index i cu arr[i] >= target (sau len(arr) dacă nu există)"""
    left, right = 0, len(arr)
    while left < right:
        mid = left + (right - left) // 2
        if arr[mid] < target:
            left = mid + 1
        else:
            right = mid
    return left

def upper_bound(arr, target):
    """Primul index i cu arr[i] > target"""
    left, right = 0, len(arr)
    while left < right:
        mid = left + (right - left) // 2
        if arr[mid] <= target:
            left = mid + 1
        else:
            right = mid
    return left

Aceste variante sunt esențiale: lower_bound și upper_bound permit numărarea aparițiilor unui element într-un array sortat în $O(\log n)$:

def count_occurrences(arr, target):
    return upper_bound(arr, target) - lower_bound(arr, target)

Complexitatea Spațiu¶

Până acum am discutat despre timp. Dar și memoria contează.

# O(1) spațiu — doar variabile simple
def sum_array(arr):
    total = 0
    for x in arr:
        total += x
    return total

# O(n) spațiu — creăm o copie
def reverse_copy(arr):
    return arr[::-1]

# O(n) spațiu din cauza stivei de recursivitate
def sum_recursive(arr, i=0):
    if i == len(arr):
        return 0
    return arr[i] + sum_recursive(arr, i + 1)

Atenție la recursivitate! Chiar dacă nu alocăm structuri noi, fiecare apel recursiv ocupă spațiu pe stivă. O recursivitate de adâncime $n$ consumă $O(n)$ memorie.

Teorema Master¶

Pentru recurențe de forma $T(n) = a \cdot T(n/b) + O(n^c)$:

1. Dacă $c < \log_b a$: $T(n) = O(n^{\log_b a})$
2. Dacă $c = \log_b a$: $T(n) = O(n^c \log n)$
3. Dacă $c > \log_b a$: $T(n) = O(n^c)$

Merge Sort: $T(n) = 2T(n/2) + O(n)$ → $a=2, b=2, c=1$ → $\log_2 2 = 1 = c$ → Cazul 2: $O(n \log n)$

Căutare Binară: $T(n) = T(n/2) + O(1)$ → $a=1, b=2, c=0$ → $\log_2 1 = 0 = c$ → Cazul 2: $O(\log n)$

Complexitate Best, Average, Worst Case¶

Un algoritm poate avea complexități diferite în funcție de input:

• Best case — cel mai favorabil input (rar relevant)
• Average case — media peste toate inputurile posibile
• Worst case — cel mai defavorabil input (cel mai des analizat)

def linear_search(arr, target):
    for i in range(len(arr)):
        if arr[i] == target:
            return i
    return -1

• Best case: $O(1)$ — elementul e primul
• Average case: $O(n/2) = O(n)$
• Worst case: $O(n)$ — elementul nu există

De obicei analizăm worst case pentru că oferă garanții.

Exerciții¶

1. Determinați complexitatea timp și spațiu:
   python def mystery(n): if n <= 1: return 1 return mystery(n // 2) + mystery(n // 2)

2. Un algoritm are complexitatea $T(n) = 2T(n/2) + n^2$. Ce complexitate are conform Teoremei Master?

3. Implementați căutarea binară recursiv și analizați diferența de spațiu față de varianta iterativă

4. Dat un array sortat de $n$ elemente, găsiți prima poziție unde arr[i] == i în $O(\log n)$