Complessità computazionale

Idea

Definizione (caso peggiore, migliore e medio). 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. Nella ricerca lineare su una lista di $n=100$ elementi il caso migliore costa $1$ confronto e il caso peggiore $100$.

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

Definizione (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.

Esempio. $3n^2+10n+7\le20n^2$ per $n\ge1$, quindi $3n^2+10n+7=O(n^2)$ con $c=20$ e $n_0=1$.

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

Classi di crescita

Definizione (classi di crescita)

Classe	Nome	Esempio
$O(1)$	costante	accesso v[i], append
$O(\log n)$	logaritmica	ricerca binaria
$O(n)$	lineare	ricerca lineare, somma, massimo
$O(n \log n)$	quasi lineare	merge sort, sorted
$O(n^2)$	quadratica	selection sort, insertion sort, tutte le coppie
$O(2^n)$	esponenziale	fib ricorsivo ingenuo, tutti i sottoinsiemi

Esempio. Con $n=10^6$ e $10^9$ operazioni al secondo, $n\log_2n\approx2\cdot10^7$ operazioni richiedono circa $0{,}02$ s e $n^2=10^{12}$ circa $17$ minuti.

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)

Proprietà (equazioni di ricorrenza del costo). 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.

Esempio. fattoriale(5) fa $6$ chiamate ($n=5,4,3,2,1,0$), coerente con $T(n)=T(n-1)+c\in O(n)$.

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")

Proprietà (effetto del raddoppio di n sul tempo). Raddoppiando $n$: un algoritmo lineare raddoppia il tempo, uno quadratico lo quadruplica.

Esempio. Se con $n=1000$ un algoritmo quadratico impiega $2$ s, con $n=2000$ ne servono circa $2\cdot4=8$.

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.