Che trattano la complessità degli algoritmi - manichini

Parte di Algorithms For Dummies Cheat Sheet

Sai già che gli algoritmi sono complessi. Tuttavia, è necessario sapere quanto è complesso un algoritmo perché più è complesso, più tempo è necessario per l'esecuzione. La seguente tabella ti aiuta a capire i vari livelli di complessità presentati in ordine di tempo di esecuzione (dal più veloce al più lento).

Complessità	Descrizione
Complessità costante O (1)	Fornisce un tempo di esecuzione invariabile, indipendentemente dalla quantità di input fornita. Ogni input richiede una singola unità di tempo di esecuzione.
Complessità logaritmica O (log n)	Il numero di operazioni cresce a un ritmo più lento dell'input, rendendo l'algoritmo meno efficiente con piccoli input e più efficiente con quelli più grandi. Un algoritmo tipico di questa classe è la ricerca binaria.
Complessità lineare O (n)	Le operazioni crescono con l'input in un rapporto 1: 1. Un algoritmo tipico è l'iterazione, quando si esegue la scansione di input una volta e si applica un'operazione a ciascun elemento di esso.
Complessità Linearitmica O (n log n)	La complessità è un mix tra complessità logaritmica e lineare. È tipico di alcuni algoritmi intelligenti utilizzati per ordinare dati, come Mergesortsort, Heapsort e Quicksort.
Complessità quadratica O (n 2 )	Le operazioni crescono come un quadrato del numero di input. Quando si ha una iterazione all'interno di un'altra iterazione (chiamata iterazioni nidificate in informatica), si ha una complessità quadratica. Ad esempio, hai un elenco di nomi e, per trovare quelli più simili, confronti ogni nome con tutti gli altri nomi. Alcuni algoritmi di ordinamento meno efficienti presentano tale complessità: ordinamento di bolle, ordinamento di selezione e ordinamento di inserimento. Questo livello di complessità significa che i tuoi algoritmi possono essere eseguiti per ore o addirittura giorni prima di raggiungere una soluzione.
Complessità cubica O (n 3 )	Le operazioni crescono anche più rapidamente della complessità quadratica perché ora si hanno più iterazioni nidificate. Quando un algoritmo ha questo ordine di complessità ed è necessario elaborare una modesta quantità di dati (100.000 elementi), l'algoritmo potrebbe funzionare per anni. Quando si dispone di un numero di operazioni che è una potenza dell'input, è comune fare riferimento all'algoritmo come in esecuzione in tempo polinomiale.
Complessità esponenziale O (2 n )	L'algoritmo richiede il doppio del numero di operazioni precedenti per ogni nuovo elemento aggiunto. Quando un algoritmo ha questa complessità, anche piccoli problemi possono richiedere per sempre. Molti algoritmi che eseguono ricerche esaurienti hanno una complessità esponenziale. Tuttavia, l'esempio classico di questo livello di complessità è il calcolo dei numeri di Fibonacci.
Complessità fattoriale O (n!)	Questo algoritmo presenta un vero incubo di complessità a causa dell'elevato numero di combinazioni possibili tra gli elementi. Immagina: se il tuo input è di 100 oggetti e un'operazione sul tuo computer richiede 10 -6 secondi (una velocità ragionevole per ogni computer al giorno d'oggi), avrai bisogno di circa 10 140 anni per completare l'attività con successo (una quantità di tempo impossibile perché l'età dell'universo è stimata in 10 14 anni). Un famoso problema di complessità fattoriale è il problema del commesso viaggiatore, in cui un venditore deve trovare il percorso più breve per visitare molte città e tornare alla città di partenza.