Notazione Big O per calcolare la complessità di un algoritmo

Questo video accompagna la guida Notazione Big O per calcolare la complessità di un algoritmo e riprende i passaggi principali con una spiegazione più diretta e visuale.

Sintesi del video

La notazione Big O è fondamentale per capire la complessità di un algoritmo e confrontare l’efficienza di soluzioni diverse.

Punti trattati

• Complessità costante: O(1)
• Complessità lineare: O(n)
• Complessità quadratica: O(n²)
• Complessità logaritmica: O(log n)
• Comparazione delle prestazioni

Testo di supporto

Come fai a sapere se un algoritmo rappresenta la soluzione migliore ad un problema? Come fai a stabilire se un algoritmo è più veloce di un altro? Come fai a capire se una nuova implementazione migliora una implementazione precedente dell’algoritmo?

Per rispondere alle precedenti domande, la notazione Big O viene in tuo aiuto.

Quando si parla di efficienza degli algoritmi, si considera l’esecuzione degli stessi su un numero molto grande di dati in input. Prendendo come esempio dell’ordinamento dei numeri, non ha molto senso considerare l’efficienza degli algoritmi per un input di 10 numeri, poiché, in questo caso, le prestazioni saranno equivalenti ed impercettibili anche comparando algoritmi con diverse prestazioni. Tuttavia se aumentiamo il nostro input a un milione di elementi vedrai che un algoritmo efficiente può ordinare i numeri in un paio di secondi mentre un algoritmo mal progettato può metterci fino ad un paio d’ore!

La notazione Big O è utilizzata per quantificare le prestazioni degli algoritmi all’aumentare della dimensione dell’input. La notazione è una delle metodologie più utilizzate per condurre l’analisi del caso peggiore.

Un algoritmo che impiega la stessa quantità di tempo di esecuzione indipendentemente dalla dimensione dell’input, si dice che è eseguito a tempo costante. Un tale algoritmo è etichettato con la notazione O(1).

Prendiamo ad esempio l’accesso all’ennesimo elemento di una lista (o array). In questo caso, il tempo impiegato per accedere l’elemento è indipendente dalla dimensione della lista ed è costante. Se devo accedere il quinto elemento di una lista, non è importante il numero di elementi che compongono la lista stessa. Il tempo che impiego per prelevare l’elemento è lo stesso sia che la lista è composta da dieci elementi o da un milione di elementi.

Approfondimento scritto

Per comandi, esempi e passaggi completi puoi leggere l’articolo collegato: Notazione Big O per calcolare la complessità di un algoritmo .