Due programmi possono risolvere lo stesso problema e dare lo stesso risultato, ma uno impiega un istante e l'altro diversi minuti. Con cento dati la differenza non si nota; con un milione diventa enorme. La notazione O-grande è lo strumento che gli informatici usano per descrivere questa differenza in modo preciso, indipendentemente dal computer, dal linguaggio o dall'abilità di chi ha scritto il codice.
Cosa misura
La notazione O-grande descrive come cresce il lavoro di un algoritmo al crescere della dimensione dell'input, indicata di solito con n. Non dice quanti secondi impiega un programma: dice come cambia il tempo quando i dati raddoppiano, decuplicano o diventano milioni.
Per questo si concentra sul comportamento per n grande e trascura due cose:
- le costanti: un algoritmo che fa 3n operazioni e uno che ne fa 100n sono entrambi O(n);
- i termini minori: n² + 50n + 7 è O(n²), perché per n grande il termine n² domina tutto il resto.
Sembra una semplificazione brutale, ed effettivamente lo è. Ma è proprio questa semplificazione a renderla utile: permette di confrontare idee, non dettagli.
Le classi più comuni
| Notazione | Nome | Esempio tipico | Con n = 1.000.000 |
|---|---|---|---|
| O(1) | Costante | Accesso a un elemento di un array per indice | 1 operazione |
| O(log n) | Logaritmica | Ricerca binaria in un elenco ordinato | circa 20 operazioni |
| O(n) | Lineare | Scorrere una lista per trovare il massimo | 1 milione |
| O(n log n) | Quasi lineare | Algoritmi di ordinamento efficienti | circa 20 milioni |
| O(n²) | Quadratica | Confrontare ogni elemento con ogni altro | mille miliardi |
| O(2ⁿ) | Esponenziale | Provare tutti i sottoinsiemi di un insieme | impraticabile |
L'ultima colonna è indicativa, ma rende l'idea: la differenza tra O(n log n) e O(n²) con un milione di elementi è la differenza tra un'operazione istantanea e una che può richiedere ore.
Esempi nel codice
Il modo più semplice per stimare la complessità è guardare i cicli.
def contiene(lista, valore):
for elemento in lista: # n iterazioni
if elemento == valore:
return True
return False
Un ciclo che scorre una volta l'input: O(n).
def ha_duplicati(lista):
for i in range(len(lista)):
for j in range(i + 1, len(lista)): # ciclo dentro un ciclo
if lista[i] == lista[j]:
return True
return False
Due cicli annidati sullo stesso input: O(n²). Lo stesso problema si può risolvere in O(n) usando un insieme, che offre ricerche in tempo medio costante:
def ha_duplicati(lista):
visti = set()
for elemento in lista:
if elemento in visti:
return True
visti.add(elemento)
return False
Questo è l'uso pratico più importante della notazione O-grande: riconoscere quando un algoritmo quadratico può diventare lineare con una struttura dati diversa.
Il logaritmo, senza paura
O(log n) spaventa chi non ama la matematica, ma l'idea è intuitiva: un algoritmo logaritmico dimezza il problema a ogni passo. Cercare un nome in un elenco ordinato aprendo a metà, poi a metà della metà giusta, e così via: con un milione di nomi bastano circa venti passaggi, perché 2 elevato alla 20 supera già il milione. Raddoppiare i dati aggiunge un solo passo.
Caso peggiore, medio e migliore
Quando si dice che un algoritmo è O(n), di solito ci si riferisce al caso peggiore. La funzione contiene può trovare il valore al primo elemento (caso migliore) o non trovarlo affatto dopo averli scorsi tutti (caso peggiore). Alcuni algoritmi hanno comportamenti molto diversi nei vari casi: il quicksort, per esempio, è O(n log n) in media ma O(n²) nel caso peggiore. Conoscere questa distinzione evita sorprese quando i dati non sono quelli che ci si aspettava.
Non solo tempo: lo spazio
La stessa notazione si usa per la memoria. La seconda versione di ha_duplicati è più veloce, ma usa O(n) memoria aggiuntiva per l'insieme, mentre la prima ne usa O(1). Spesso si scambia spazio per tempo, ed è una scelta consapevole da fare in base al contesto.
Quando la complessità non è tutto
La notazione O-grande è un ottimo strumento di ragionamento, ma non sostituisce la misura reale. Con input piccoli un algoritmo O(n²) semplice può essere più veloce di uno O(n log n) complesso, perché le costanti trascurate contano. E molti problemi di prestazioni reali dipendono da altro: accessi al disco, chiamate di rete, query al database ripetute in un ciclo. La regola pratica: usa la complessità per scegliere l'approccio, poi misura con un profiler prima di ottimizzare.
In sintesi
- La notazione O-grande descrive come cresce il costo di un algoritmo al crescere dell'input.
- Ignora costanti e termini minori, per confrontare le idee e non i dettagli.
- Cicli annidati sullo stesso input suggeriscono O(n²); spesso una struttura dati adatta riporta a O(n).
- O(log n) significa dimezzare il problema a ogni passo.
- Usa la complessità per ragionare, ma misura sempre prima di ottimizzare.
