Cos’è logn?

La versione breve è che è un termine informatico da smanettoni che è anche abbastanza corto da piacermi come nome di dominio. Nonostante ciò che altri possono dirvi, non è un errore di ortografia di “login”. Inoltre, si tende a pronunciarlo come “log” seguito dalla lettera “n”.

La versione lunga è che è il termine usato per descrivere una classe di algoritmi altamente efficienti.Se mi concedete una breve lezione…

Complessità temporale

In informatica, gli algoritmi sono spesso confrontati dalla quantità di tempo o memoria che consumano per eseguire un compito. Al fine di rendere questi confronti equi e facili da capire, li analizziamo basandoci sulla relazione tra la dimensione del compito e il numero di passi richiesti per completare il compito.

Per esempio, supponiamo di voler fare la media di una lista di valori numerici. Per farlo, avreste bisogno di sommare tutti i numeri e poi dividere per il numero di valori che avete. Il numero di passi è direttamente correlato al numero di valori: se raddoppiate il numero di valori da calcolare, vi aspettate che ci voglia il doppio del tempo. Questo è un esempio di complessità lineare: al crescere del numero di elementi (abbreviato in n), il tempo per completare il compito cresce allo stesso ritmo.

Si può certamente fare molto peggio del tempo lineare; molti compiti richiedono un tempo polinomiale o addirittura esponenziale per essere completati! L’ordinamento delle liste di numeri è un buon esempio; è necessario fare più passaggi sui dati per setacciare tutto in un ordine finale.

Tuttavia, ci sono anche alcuni algoritmi che sono migliori del tempo lineare. Consideriamo un gioco di indovinelli in cui un umano pensa a un numero compreso tra uno e 100, e il computer deve indovinare quale sia. Se il computer indovina in modo errato, l’umano dice al computer se la risposta è “più alta” o “più bassa” di quella indovinata. Scegliendo accuratamente i numeri indovinati, questa informazione permette al computer di eliminare la metà dei numeri rimanenti ad ogni tentativo (scegliendo sempre un numero nel mezzo del possibile insieme di numeri).

Perché ogni tentativo divide il numero rimanente a metà, i ripetuti dimezzamenti si compongono e creano un esponente inverso: un algoritmo. In effetti, il numero di passi per risolvere il problema cresce linearmente mentre lo spazio del problema cresce esponenzialmente. Pensato in un altro modo, raddoppiando la dimensione del problema si ottiene solo un singolo passo aggiuntivo (confronta questo con un algoritmo lineare, dove raddoppiando la dimensione del problema raddoppia anche il numero di passi). Abbreviamo questa relazione come logn, mostrando che come n (la dimensione del problema) diventa più grande, il numero di passi è solo il logaritmo di quel numero.

Quindi, gli algoritmi logaritmici sono altamente efficienti e ben considerati.Ho pensato che sarebbe stato divertente chiamare il mio dominio come loro.

Lascia un commento

Il tuo indirizzo email non sarà pubblicato.