Quanto è veloce? La notazione O grande

A un miliardo di passi al secondo, un metodo n² su un milione di valori richiede circa 17 minuti; un metodo n log n richiede 0.02 secondi.

La crescita conta più del conteggio esatto

Finora abbiamo contato i passi esattamente: 45 confronti, 4 scambi, 20 controlli. I conteggi esatti sono utili per esempi piccoli, ma dipendono da dettagli come il fatto che il bubble sort si fermi prima o il modo in cui si sceglie un pivot. Quando l'input diventa grande, una cosa domina tutte le altre: come cresce il conteggio al crescere di n. Un algoritmo i cui passi crescono come n² finirà per perdere contro uno i cui passi crescono come n log n, per quanto il primo sia messo a punto con cura.

La notazione O grande è il modo abbreviato per indicare questa crescita. Scrivere che un algoritmo è O(n²), che si legge «O grande di n al quadrato», significa che per n grande il suo numero di passi è al massimo una costante per n². Due regole la rendono facile da usare. Togli i fattori costanti: 3n e n/2 sono entrambi O(n). Tieni solo il termine che cresce più in fretta: n²/2 − n/2, i confronti del selection sort, è O(n²), perché per n grande la parte n² è quasi tutto. Il corso 6.006 del MIT usa la stessa idea quando confronta strutture dati e ordinamenti in base al loro tempo di esecuzione asintotico.

Le velocità di crescita più comuni

• O(1), costante. Il lavoro non dipende da n: leggere il primo valore di una lista, o un valore in una posizione nota.
• O(log n), logaritmica. Ogni passo dimezza il problema: la ricerca binaria. Un milione di valori, circa 20 passi.
• O(n), lineare. Ogni valore si tratta una volta: la ricerca lineare, trovare il valore più grande, sommare una lista.
• O(n log n). Il merge sort, e il quicksort in media. Il meglio che possa fare un ordinamento per confronti.
• O(n²), quadratica. Si esamina ogni coppia: bubble sort, selection sort e insertion sort nel caso peggiore, oppure due cicli annidati uno dentro l'altro.
• O(2ⁿ), esponenziale. Il lavoro raddoppia a ogni valore in più: provare ogni sottoinsieme di n oggetti, o spostare n dischi nella torre di Hanoi.

Che cosa significano i numeri in secondi

Supponi che un computer faccia un miliardo (10⁹) di passi elementari al secondo, una cifra tonda ragionevole per un singolo core di un processore. Ecco che cosa significa ogni velocità di crescita per un milione di valori. O(log n) è circa 20 passi, molto meno di un microsecondo. O(n) è un milione di passi, un millisecondo. O(n log n) è circa 20 milioni di passi, 0.02 secondi. O(n²) è 10¹² passi, mille secondi, circa 17 minuti. O(2ⁿ) non si può portare a termine: 2 alla potenza di un milione è un numero con più di 300000 cifre. Per questo scegliere l'algoritmo giusto di solito conta molto più che comprare un computer più veloce. Una macchina dieci volte più veloce trasforma 17 minuti in 1.7 minuti; passare da O(n²) a O(n log n) li trasforma in un cinquantesimo di secondo.

Leggere la O grande dal codice

Spesso puoi leggere la velocità di crescita direttamente dalla forma del codice. Un solo ciclo sulla lista è O(n). Due cicli, uno dentro l'altro, entrambi sulla lista, sono O(n²): per ognuno degli n giri esterni il ciclo interno fa fino a n giri. Un ciclo che dimezza un numero ogni volta, come while (n > 1) n = Math.floor(n / 2), è O(log n): partendo da 1000 gira 9 volte, da un milione 19 volte. I passi che avvengono uno dopo l'altro si sommano, e vince il termine più grande: un ciclo O(n) seguito da un ciclo O(n²) è O(n²) nel complesso.

// O(n): una passata
let total = 0;
for (const x of list) total += x;

// O(n²): ogni coppia
for (let i = 0; i < list.length; i++)
  for (let j = i + 1; j < list.length; j++)
    if (list[i] === list[j]) console.log("duplicate", list[i]);

// O(log n): dimezzamenti
let k = list.length, rounds = 0;
while (k > 1) { k = Math.floor(k / 2); rounds++; }

Caso migliore, medio e peggiore

Uno stesso algoritmo può comportarsi in modo molto diverso su input diversi. L'insertion sort è O(n) su una lista già ordinata e O(n²) su una invertita. Il quicksort è O(n log n) in media e O(n²) con pivot sempre sbagliati. Quando si cita una sola O grande senza dire di quale caso si tratta, di solito si intende il caso peggiore, perché è una garanzia: l'algoritmo non farà mai di peggio. La O grande trascura anche alcune cose. Ignora i fattori costanti, quindi per input piccoli un metodo O(n²) con passi molto semplici può battere uno O(n log n). Per questo molte routine di ordinamento reali passano all'insertion sort per i pezzi corti della lista.