Notazione Big O - Spiegata semplicemente con illustrazioni e video

La notazione Big O viene utilizzata per comunicare la velocità di un algoritmo. Questo può essere importante quando si valutano gli algoritmi di altre persone e quando si valutano i propri! In questo articolo, spiegherò cos'è la notazione Big O e ti fornirò un elenco dei tempi di esecuzione più comuni per gli algoritmi che la utilizzano.

I tempi di esecuzione degli algoritmi crescono a velocità diverse

Mio figlio Judah ha molti giocattoli. In effetti, ha acquistato un miliardo di giocattoli! Saresti sorpreso di quanto velocemente un bambino possa ottenere così tanti giocattoli se è il primo nipote di entrambi i lati della famiglia. ??

Comunque, Judah ha un problema. Quando i suoi amici visitano e vogliono giocare con un giocattolo specifico, può volerci SEMPRE per trovare il giocattolo. Quindi vuole creare un algoritmo di ricerca per aiutarlo a trovare un giocattolo specifico il più rapidamente possibile. Sta cercando di decidere tra due diversi algoritmi di ricerca: ricerca semplice e ricerca binaria. (Non preoccuparti se non hai familiarità con questi algoritmi.)

L'algoritmo scelto deve essere veloce e corretto. Da un lato, la ricerca binaria è più veloce. E spesso Judah ha solo 3 0 secondi prima che il suo amico si annoi a cercare un giocattolo. D'altra parte, un semplice algoritmo di ricerca è più facile da scrivere e ci sono meno possibilità che vengano introdotti bug. Sarebbe sicuramente imbarazzante se il suo amico avesse trovato dei bug nel suo codice! Per stare molto attenti, Judah decide di cronometrare entrambi gli algoritmi con un elenco di 100 giocattoli.

Supponiamo che sia necessario 1 millisecondo per controllare un giocattolo. Con la ricerca semplice, Judah deve controllare 100 giocattoli, quindi la ricerca impiega 100 ms per essere eseguita. D'altra parte, deve solo controllare 7 giocattoli con la ricerca binaria (log2 100 è circa 7, non preoccuparti se questa matematica è confusa poiché non è il punto principale di questo articolo), quindi la ricerca richiede 7 ms correre. Ma in realtà, l'elenco conterrà un miliardo di giocattoli. In caso affermativo, quanto tempo richiederà la ricerca semplice? Quanto tempo richiederà la ricerca binaria?

Tempo di esecuzione per la ricerca semplice rispetto alla ricerca binaria, con un elenco di 100 elementi

Judah esegue la ricerca binaria con 1 miliardo di giocattoli e impiega 30 ms (log2 1.000.000.000 corrisponde a circa 30). "32 ms!" lui pensa. "La ricerca binaria è circa 15 volte più veloce della ricerca semplice, perché la ricerca semplice ha richiesto 100 ms con 100 elementi e la ricerca binaria ha richiesto 7 ms. Quindi una ricerca semplice richiederà 30 × 15 = 450 ms, giusto? Ben al di sotto dei 30 secondi necessari al mio amico per annoiarsi. " Judah decide di andare con una semplice ricerca. È la scelta giusta?

No. Si scopre che Judah aveva torto e ha perso un amico per la vita. ? Il tempo di esecuzione per la ricerca semplice con 1 miliardo di elementi sarà di 1 miliardo di ms, ovvero 11 giorni! Il problema è che i tempi di esecuzione per la ricerca binaria e la ricerca semplice non crescono allo stesso ritmo.

I tempi di esecuzione crescono a velocità molto diverse! Man mano che il numero di elementi aumenta, la ricerca binaria richiede un po 'più di tempo per essere eseguita, ma la ricerca semplice richiede molto più tempo per essere eseguita. Quindi, man mano che l'elenco dei numeri diventa più grande, la ricerca binaria diventa improvvisamente molto più veloce della ricerca semplice.

Quindi Judah si sbagliava sul fatto che la ricerca binaria fosse sempre 15 volte più veloce della ricerca semplice. Se ci sono 1 miliardo di giocattoli, è più simile a 33 milioni di volte più veloce.

È molto importante sapere come il tempo di esecuzione aumenta all'aumentare della dimensione dell'elenco. È qui che entra in gioco la notazione Big O.

La notazione Big O ti dice quanto è veloce un algoritmo. Ad esempio, supponiamo di avere un elenco di dimensioni n . La ricerca semplice deve controllare ogni elemento, quindi saranno necessarie n operazioni. Il tempo di esecuzione nella notazione Big O è O ( n ).

Dove sono i secondi? Non ce ne sono: Big O non ti dice la velocità in pochi secondi. La notazione O grande ti consente di confrontare il numero di operazioni. Ti dice quanto velocemente cresce l'algoritmo.

Facciamo un altro esempio. La ricerca binaria richiede operazioni di log n per controllare un elenco di dimensione n . Qual è il tempo di esecuzione nella notazione Big O? È O (log n ). In generale, la notazione Big O è scritta come segue.

Questo ti dice il numero di operazioni che un algoritmo farà. Si chiama notazione O grande perché si mette una "O grande" davanti al numero di operazioni.

Big O stabilisce un tempo di esecuzione nel caso peggiore

Supponi di utilizzare la ricerca semplice per cercare un utente nel tuo database utenti. Sai che la ricerca semplice richiede O ( n ) tempo per essere eseguita, il che significa che nel peggiore dei casi, il tuo algoritmo dovrà esaminare ogni utente nel database. In questo caso, stai cercando un utente con il nome "aardvark213". Questo è il primo utente nell'elenco. Quindi il tuo algoritmo non doveva esaminare ogni voce: l'ha trovata al primo tentativo. L'algoritmo ha impiegato O ( n ) tempo? O ci è voluto O (1) tempo perché ha trovato la persona al primo tentativo?

La ricerca semplice richiede ancora O ( n ) tempo. In questo caso, l'algoritmo ha trovato immediatamente quello che stava cercando. Questo è lo scenario migliore. Ma notazione O-grande è circa il caso peggiore scenario. Quindi puoi dire che, nel peggiore dei casi , l'algoritmo dovrà esaminare ogni utente nel database una volta. È O ( n ) tempo. È una rassicurazione: sai che la ricerca semplice non sarà mai più lenta del tempo O ( n ).

Alcuni tempi di esecuzione di Big O comuni

Ecco cinque tempi di esecuzione di Big O che incontrerai molto, ordinati dal più veloce al più lento:

  • O (log n ), noto anche come log time. Esempio: ricerca binaria.
  • O ( n ), noto anche come tempo lineare . Esempio: ricerca semplice.
  • O ( n * log n ). Esempio: un algoritmo di ordinamento veloce, come quicksort.
  • O ( n 2). Esempio: un algoritmo di ordinamento lento, come l'ordinamento per selezione.
  • O ( n !). Esempio: un algoritmo molto lento, come il venditore ambulante.

Visualizzazione di tempi di esecuzione di Big O diversi

Supponi di disegnare una griglia di 16 riquadri e puoi scegliere tra 5 diversi algoritmi per farlo. Se usi il primo algoritmo, ti ci vorrà O (log n ) tempo per disegnare la griglia. Puoi eseguire 10 operazioni al secondo. Con il tempo O (log n ), ci vorranno 4 operazioni per disegnare una griglia di 16 caselle (log 16 in base 2 è 4). Quindi ti ci vorranno 0,4 secondi per disegnare la griglia. E se dovessi disegnare 1.024 caselle? Ti occorrerà registrare 1.024 = 10 operazioni o 1 secondo per disegnare una griglia di 1.024 caselle. Questi numeri utilizzano il primo algoritmo.

Il secondo algoritmo è più lento: impiega O ( n ) tempo. Occorrono 16 operazioni per disegnare 16 riquadri e 1.024 operazioni per disegnare 1.024 riquadri. Quanto tempo è in secondi?

Ecco quanto tempo ci vorrebbe per disegnare una griglia per il resto degli algoritmi, dal più veloce al più lento:

Ci sono anche altri tempi di esecuzione, ma questi sono i cinque più comuni.

Questa è una semplificazione. In realtà non puoi convertire da un tempo di esecuzione di Big O a un numero di operazioni così ordinatamente, ma questa è una buona stima.

Conclusione

Ecco le principali conclusioni:

  • La velocità dell'algoritmo non viene misurata in secondi, ma in aumento del numero di operazioni.
  • Invece, parliamo di quanto velocemente il tempo di esecuzione di un algoritmo aumenta all'aumentare della dimensione dell'input.
  • Il tempo di esecuzione degli algoritmi è espresso in notazione Big O.
  • O (log n ) è più veloce di O ( n ), ma diventa molto più veloce man mano che l'elenco degli elementi che stai cercando cresce.

Ed ecco un video che copre molto di ciò che è in questo articolo e altro ancora.

Spero che questo articolo ti abbia portato più chiarezza sulla notazione Big O. Questo articolo si basa su una lezione nel mio corso video da Manning Publications chiamato Algorithms in Motion. Il corso è basato sul fantastico libro Grokking Algorithms di Adit Bhargava. È lui che ha disegnato tutte le illustrazioni divertenti in questo articolo.

Se impari meglio attraverso i libri, prendi il libro! Se impari meglio attraverso i video, considera l'acquisto del mio corso. Puoi ottenere uno sconto del 39% sul mio corso utilizzando il codice " 39carnes ".