Programmazione · concetti · algoritmi
Che cosa e la notazione Big O?
La notazione Big O e un modo per descrivere come cresce il tempo di esecuzione di un algoritmo (o il suo uso di memoria) al crescere dell'input. Risponde a una domanda: quando la quantita di dati raddoppia, o cresce di mille volte, il tuo codice resta veloce, rallenta un po' o si blocca del tutto? Ignora deliberatamente i secondi esatti e la velocita della macchina, e si concentra sulla forma della crescita, perche e questo che decide se un codice che funziona su 100 elementi funziona ancora su 100 milioni.
Perche non misurare semplicemente il tempo?
Perche i secondi dipendono dalla macchina, dal linguaggio, dal compilatore e da cosa altro e in esecuzione. Esegui lo stesso codice su un portatile e su un server e ottieni numeri diversi. Big O scarta tutto questo e misura qualcosa di piu duraturo: come il lavoro scala con la dimensione dell'input, di solito chiamata n. Due algoritmi possono entrambi impiegare "pochi millisecondi" su un input piccolo, eppure uno resta rapido su larga scala mentre l'altro diventa inutilizzabile. Big O e il modo in cui li distinguiamo prima di sbattere contro quel muro.
Le complessita piu comuni, dalla migliore alla peggiore
Questi sono i tassi di crescita che incontrerai piu spesso, dal piu rapido nel scalare al piu pericoloso:
| Notazione | Nome | Idea di massima |
|---|---|---|
| O(1) | Costante | Stesso lavoro indipendentemente dalla dimensione dell'input, ad esempio leggere array[5]. |
| O(log n) | Logaritmica | Dimezza il problema a ogni passo, ad esempio la ricerca binaria. |
| O(n) | Lineare | Il lavoro cresce di pari passo con l'input, ad esempio scorrere una lista una volta. |
| O(n log n) | Linearitmica | Il meglio che puoi fare per l'ordinamento generale, ad esempio mergesort. |
| O(n²) | Quadratica | Un ciclo dentro un ciclo: va bene per 100 elementi, doloroso per un milione. |
| O(2ⁿ) | Esponenziale | Raddoppia a ogni elemento aggiunto: utilizzabile solo per input minuscoli. |
| O(n!) | Fattoriale | Ogni ordinamento dell'input: pratico solo per n molto piccoli. |
Perche le costanti e i termini piccoli vengono ignorati
Big O si interessa alla crescita, non ai conteggi esatti, quindi semplifica. Se un algoritmo esegue 2n + 3 passi, si scrive O(n): il 2 e il 3 non cambiano la forma della curva quando n diventa grande. Allo stesso modo n² + n diventa O(n²), perche il termine quadratico domina quando n e grande. Ecco perche Big O riguarda il termine dominante, la parte che decide il comportamento su larga scala, e non una lettura precisa del cronometro.
Un esempio concreto
Supponiamo di voler verificare se una lista contiene un duplicato. Un approccio confronta ogni elemento con ogni altro elemento, due cicli annidati, all'incirca n × n confronti, quindi O(n²). Un altro approccio aggiunge ogni elemento a un hash set e verifica l'appartenenza man mano che procede, un solo passaggio, quindi O(n). Su 1.000 elementi la versione quadratica esegue circa un milione di confronti; su 100.000 elementi ne esegue dieci miliardi, mentre la versione lineare ne esegue 100.000. Stesso compito, destino radicalmente diverso su larga scala. Quel divario e esattamente cio che Big O e progettato per rivelare.
Caso peggiore, medio e migliore
In senso stretto, Big O descrive un limite superiore, di solito il caso peggiore, il massimo lavoro che l'algoritmo potrebbe fare. Vedrai anche due parenti: Big Omega (Ω) per il caso migliore, un limite inferiore, e Big Theta (Θ) quando il caso migliore e quello peggiore crescono allo stesso ritmo, dando un limite stretto. Nell'uso quotidiano si dice "Big O" in modo generico per intendere la crescita nel caso peggiore, perche e cio su cui si pianifica: vuoi sapere quanto brutta puo diventare la situazione, non quanto fortunato potresti essere ogni tanto.
Anche la complessita spaziale
La stessa notazione descrive la memoria, non solo il tempo. Un algoritmo che copia l'intero input in una nuova struttura usa O(n) di spazio extra; uno che riorganizza l'input sul posto usa O(1) di spazio extra. Su grandi quantita di dati, la memoria puo essere il vero limite, quindi vale la pena chiedersi sia "come cresce il tempo?" sia "come cresce la memoria?"
Come ragionare sul tuo codice
- Conta i cicli sull'input. Un singolo passaggio e di solito O(n); un ciclo dentro un ciclo sugli stessi dati e di solito O(n²).
- Dimezzare e un logaritmo. Se ogni passo scarta meta dei dati rimanenti (come la ricerca binaria), quello e O(log n).
- Le ricerche in un hash map/set sono ~O(1). Sostituire una scansione annidata con una ricerca hash e il modo classico per trasformare O(n²) in O(n).
- Ignora le costanti. Tre passaggi singoli separati sono comunque O(n), non O(3n): cio che conta e la forma.
FAQ
Una Big O piu bassa e sempre piu veloce? Su larga scala si, ma non sempre per input piccoli. Le costanti e l'overhead che Big O ignora possono far si che un metodo O(n²) batta uno O(n log n) su una manciata di elementi. Big O ti dice chi vince quando i dati crescono, che di solito e cio che conta.
Qual e la migliore complessita possibile? O(1), tempo costante: il lavoro non cresce affatto con l'input. La successiva migliore e O(log n). Per problemi che devono esaminare ogni elemento almeno una volta, O(n) e il minimo.
Perche O(n log n) e speciale per l'ordinamento? E il limite inferiore dimostrato per l'ordinamento generale basato su confronti, quindi mergesort, heapsort e le buone implementazioni di quicksort puntano tutte a esso. In generale non puoi ordinare dati arbitrari piu velocemente solo con i confronti.
Mi serve Big O per la programmazione di tutti i giorni? Non serve la matematica formale, ma l'intuizione e preziosissima: riconoscere quando un ciclo annidato esplodera su un input grande, o quando una ricerca hash ti salva, previene intere categorie di bug di prestazioni.