Articolo originale: Big O Notation Explained with Examples
La notazione O-grande è un modo di descrivere la velocità o la complessità di un dato algoritmo. Se il tuo progetto attuale richiede un algoritmo predefinito, è importante capire quanto questo sia veloce o lento rispetto ad altre opzioni.
Cos'è la notazione O-grande e come funziona?
La notazione O-grande esprime il numero di operazioni compiute da un algoritmo. Prende il nome dalla "O" maiuscola posta davanti al numero stimato di operazioni.
Quello che la notazione O-grande non ti dice è la velocità di un algoritmo in secondi. Ci sono troppi fattori che influenzano il tempo necessario all'esecuzione di un algoritmo. Invece, utilizzerai la notazione O-grande per confrontare algoritmi diversi tramite il numero di operazioni che svolgono.
La O-grande definisce il tempo di esecuzione per il caso peggiore
Immagina di essere un insegnante e di avere uno studente di nome Gianni. Vuoi trovare i suoi dati usando un algoritmo di ricerca semplice cercando nel database della tua scuola.
La ricerca semplice viene eseguita in O(n) volte. Ciò vuol dire che, nel caso peggiore, dovrai cercare tra tutti i singoli dati (rappresentati da n) per trovare quelli di Gianni.
Ma quando esegui la ricerca semplice, trovi che i dati di Gianni sono la prima voce del database. Non devi analizzare ogni voce perché hai trovato i dati che cercavi al primo tentativo.
Questo algoritmo impiega un tempo O(n)? Oppure O(1), visto che hai trovato i dati al primo colpo?
In questo caso, o(1) rappresenta il caso più favorevole - sei stato fortunato e hai trovato i dati di Gianni in cima al database. La notazione O-grande si riferisce al caso peggiore, che è o(n) per una ricerca semplice. La certezza è che la ricerca semplice non sarà mai più lunga di un tempo O(n).
I tempi di esecuzione degli algoritmi crescono a velocità diverse
Considera di impiegare 1 millisecondo per controllare ciascun elemento del database della scuola.
Con una ricerca semplice, se devi controllare 10 voci, impiegherai 10 ms, ma con un algoritmo di ricerca binaria devi controllare soltanto 3 elementi, impiegando 3 ms.
Nella maggior parte dei casi, la lista o il database in cui effettui la ricerca avranno centinaia o migliaia di elementi.
Se c'è 1 miliardo di elementi, usando la ricerca semplice il tempo massimo necessario è 1 miliardo di ms, o 11 giorni. D'altro canto, usando la ricerca binaria ci vorranno soltanto 32 ms nel caso più sfavorevole:
Chiaramente i tempi di esecuzione per una ricerca semplice e per una ricerca binaria non crescono alla stessa velocità. Man mano che le voce in elenco aumentano, la ricerca binaria impiega un po' più di tempo. Il tempo di esecuzione della ricerca semplice cresce esponenzialmente man mano che le voci in elenco aumentano.
Ecco perché è importante sapere come cresce il tempo di esecuzione in relazione alla dimensione di un elenco ed è esattamente ciò per cui la notazione O-grande risulta utile.
La notazione O-grande mostra il numero di operazioni
Come detto precedentemente, la notazione O-grande non mostra il tempo che un algoritmo impiega per essere eseguito, ma indica il numero di operazioni che svolge e quanto velocemente cresce in confronto ad altri.
Ecco alcuni algoritmi comuni con i relativi tempi di esecuzione in notazione O-grande:
| Notazione O-grande | Algoritmo di esempio |
|---|---|
| O(log n) | Ricerca binaria |
| O(n) | Ricerca semplice |
| O(n * log n) | Quicksort |
| O(n2) | Ordinamento per selezione |
| O(n!) | Commesso viaggiatore |
Adesso ne sai abbastanza sulla notazione O-grande per iniziare a confrontare algoritmi!