Complessità computazionale

Idea

Si misura il numero di operazioni elementari (assegnamenti, confronti, operazioni aritmetiche, accessi per indice) in funzione della dimensione dell'input $n$ (lunghezza della lista, numero di cifre...). Il tempo in secondi dipende dalla macchina; la crescita al crescere di $n$ no.

• Caso peggiore: massimo numero di operazioni tra gli input di dimensione $n$ (è quello che si dà di solito: è una garanzia).
• Caso migliore: minimo.
• Caso medio: media su una distribuzione degli input.

Esempio, ricerca lineare di x in una lista di $n$ elementi: caso migliore 1 confronto (primo elemento), caso peggiore $n$ (assente o ultimo).

Notazione O-grande

$f(n) = O(g(n))$ se esistono $c > 0$ e $n_0$ tali che $f(n) \le c \cdot g(n)$ per ogni $n \ge n_0$: $f$ cresce al più come $g$, a meno di costanti.

Regole pratiche:

• si tiene solo il termine dominante e si tolgono le costanti: $3n^2 + 10n + 7 = O(n^2)$;
• passi in sequenza: si sommano (vince il maggiore);
• cicli annidati: si moltiplicano.

Esistono anche $\Omega$ (limite inferiore: cresce almeno come) e $\Theta$ (stessa crescita: sia $O$ sia $\Omega$).

Classi di crescita

Con $n = 10^6$ e $10^9$ operazioni al secondo: $n \log n$ richiede circa 0,02 s, $n^2$ circa 17 minuti, $2^n$ è impossibile.

Contare i passi

for i in range(n):            # n volte
    s += v[i]                 # O(1)
# totale O(n)

for i in range(n):
    for j in range(i + 1, n): # n-1, n-2, ..., 0 volte
        ...                   # totale n(n-1)/2 = O(n^2)

i = n
while i > 1:
    i //= 2                   # i si dimezza: log2(n) iterazioni -> O(log n)

Ricorsione: si scrive l'equazione di ricorrenza del costo $T(n)$.

• fattoriale: $T(n) = T(n-1) + c$ → $O(n)$.
• ricerca binaria: $T(n) = T(n/2) + c$ → $O(\log n)$.
• merge sort: $T(n) = 2T(n/2) + cn$ → $O(n \log n)$.
• fib ingenuo: $T(n) = T(n-1) + T(n-2) + c$ → esponenziale.

Costi nascosti in Python

Una riga di Python non è sempre $O(1)$:

# O(n^2): "in" su una lista dentro un ciclo
dup = any(v[i] in v[i+1:] for i in range(len(v)))
# O(n): insieme
dup = len(set(v)) != len(v)

Misurare i tempi

import time
t0 = time.perf_counter()
risultato = funzione(dati)
print(f"{time.perf_counter() - t0:.4f} s")

Raddoppiando $n$: un algoritmo lineare raddoppia il tempo, uno quadratico lo quadruplica.

Spazio

Analogamente si misura la memoria aggiuntiva: $O(1)$ se si usano poche variabili, $O(n)$ se si crea una copia della lista; la ricorsione usa spazio di stack proporzionale alla profondità.

Errori tipici

• Considerare $O(1)$ un in su lista o uno slicing.
• Confondere caso migliore e caso peggiore.
• Pensare che le costanti non contino mai: a parità di classe contano, ma per $n$ grande la classe vince.