In informatica, la complessità temporale di un algoritmo quantifica la quantità di tempo impiegata da un algoritmo a essere eseguito in funzione della lunghezza della stringa che rappresenta l'input:226. La complessità temporale di un algoritmo è espressa comunemente usando la notazione O-grande, che esclude i coefficienti e i termini di ordine inferiore. Quando è espressa in questo modo, si dice che la complessità temporale è descritta asintoticamente, ossia, quando la dimensione degli input va a infinito. Ad esempio, se il tempo richiesto da un algoritmo su tutti gli input di dimensione n è al massimo , la complessità temporale asintotica è O(n3).
La complessità temporale è stimata comunemente contando il numero di operazioni elementari eseguite dall'algoritmo, dove un'operazione elementare impiega una quantità di tempo fissa a essere eseguita. Così la quantità di tempo impiegata e il numero di operazioni elementari eseguite dall'algoritmo differiscono al massimo di un fattore costante.
Poiché il tempo di esecuzione di un algoritmo può variare con diversi input della stessa dimensione, si usa comunemente la complessità temporale del caso peggiore di un algoritmo, denotata come T(n), che è definita come la quantità di tempo massimo impiegata su qualsiasi input di dimensione n. Le complessità temporali sono classificate in base alla natura della funzione T(n). Ad esempio, un algoritmo con T(n) = O(n) è chiamato algoritmo in tempo lineare, e un algoritmo con T(n) = O(2n) si dice che è un algoritmo in tempo esponenziale.
Tabella di complessità temporali comuni
La tabella seguente sintetizza alcune classi di complessità temporali che si incontrano comunemente. Nella tabella, poly(x) = xO(1), cioè, polinomiale in x.
Nome Classe di complessità Tempo di esecuzione (T(n)) Esempi di tempi di esecuzione Algoritmi di esempio tempo costante O(1) 10 Determinare se un intero (rappresentato in binario) è pari o dispari tempo inverso di Ackermann O(α(n)) Tempo ammortizzato per un'operazione che usa un insieme disgiunto tempo logaritmico iterato O(log* n) Colorazione distribuita di cicli log-logaritmico O(log log n) Tempo ammortizzato per un'operazione che usa una coda di priorità vincolata tempo logaritmico DLOGTIME O(log n) log n, log(n2) ricerca binaria tempo polilogaritmico poly(log n) (log n)2 potenza frazionaria O(nc) dove 0 < c < 1 n1/2, n2/3 Ricerca in un albero kd tempo lineare O(n) n Trovare l'elemento più piccolo in un vettore non ordinato tempo "n log asterisco n" O(n log* n) Algoritmo di triangolazione di un poligono di Seidel tempo linearitmico O(n log n) n log n, log n! Il più veloce ordinamento comparativo tempo quadratico O(n2) n2 Ordinamento a bolle; ordinamento a inserimento; convoluzione diretta tempo cubico O(n3) n3 Moltiplicazione ingenua di due matrici n×n. Calcolare la correlazione parziale tempo polinomiale P 2O(log n) = poly(n) n, n log n, n10 Algoritmo di Karmarkar per la programmazione lineare; algoritmo AKS tempo quasi-polinomiale QP 2poly(log n) nlog log n, nlog n Il più noto algoritmo di approssimazione O(log2 n) per il problema dell'albero di Steiner diretto tempo subesponenziale(prima definizione) SUBEXP O(2nε) per tutti gli ε > 0 O(2log nlog log n) Assumendo le congetture della teoria della complessità, BPP è contenuta in SUBEXP tempo subesponenziale(seconda definizione) 2o(n) 2n1/3 Il più noto algoritmo per la scomposizione in fattori primi e per l'isomorfismo dei grafi tempo esponenziale E 2O(n) 1,1n, 10n Risolvere il problema del commesso viaggiatore usando la programmazione dinamica tempo fattoriale O(n!) n! Risolvere il problema del commesso viaggiatore attraverso il metodo forza bruta tempo esponenziale EXPTIME 2poly(n) 2n, 2n2 tempo doppio esponenziale 2-EXPTIME 22poly(n) 22n Decidere la verità di un'affermazione data nell'aritmetica di Presburger
Tempo costante Si dice che un algoritmo è in tempo costante (scritto anche come tempo O(1)) se il valore di T(n) è vincolato da un valore che non dipende dalla dimensione dell'input. Ad esempio, accedere a qualsiasi elemento singolo in un vettore richiede tempo costante in quanto deve essere eseguita solo un'operazione per localizzarlo. Tuttavia, trovare il valore minimale in un vettore non ordinato non è un'operazione in tempo costante, in quanto è necessaria una scansione su ciascun elemento del vettore al fine di determinare il valore minimale. Quindi è un'operazione in tempo lineare, che impiega il tempo O(n). Se il numero di elementi è conosciuto in anticipo e non cambia, tuttavia, si può ancora dire che tale algoritmo si esegue in tempo costante.
Malgrado il nome "tempo costante", il tempo di esecuzione non deve essere indipendente dalla dimensione del problema, ma deve essere posto un vincolo superiore per il tempo di esecuzione indipendentemente dalla dimensione del problema. Ad esempio, il compito "scambiare i valori di a e b se necessario affinché a ≤ b" è chiamato tempo costante anche se il tempo può dipendere se sia o no già vero che a ≤ b. Tuttavia, c'è una qualche costante t tale che il tempo richiesto sia sempre al massimo t.
Ecco alcuni frammenti di codice che si eseguono in tempo costante:
int indice = 5; int elemento = lista[indice]; if (condizione vera) then svolgere qualche operazione che si esegue in tempo costante other svolgere qualche altra operazione che si esegue in tempo costante per i = 1 a 100 per j = 1 a 200 svolgere qualche operazione che si esegue in tempo costante
Se T(n) è O(qualsiasi valore costante), questo è equivalente a ed enunciato in notazione normale come T(n) essendo O(1).
Tempo logaritmico Si dice che un algoritmo impiega tempo logaritmico se T(n) = O(log n). A causa dell'uso del sistema numerico binario da parte dei computer, il logaritmo è frequentemente a base 2 (cioè, log2 n, talvolta scritto lg n). Tuttavia, con il cambiamento della base per i logaritmi, loga n e logb n differiscono soltanto per un moltiplicatore costante, che nella notazione O grande è scartato; così O(log n) è la notazione standard per gli algoritmi in tempo logaritmico indipendentemente dalla base del logaritmo.
Gli algoritmi che impiegano tempo logaritmico si trovano comunemente nelle operazioni sugli alberi binari o quando si usa la ricerca binaria.
Un algoritmo O(log n) è considerato altamente efficiente, in quanto le operazioni da completare richieste per istanza diminuiscono con ogni istanza.
Un esempio molto semplice di questo tipo di f(n) è un algoritmo che taglia a metà una stringa. Impiegherà O(log n) (n essendo la lunghezza della stringa) dal momento che sminuzziamo la stringa a metà prima di ogni stampa (facciamo l'assunzione che console.log e str.substring si eseguano in tempo costante). Questo significa che, al fine di aumentare il numero di stampe, dobbiamo raddoppiare la lunghezza della stringa.
// Funzione per stampare ricorsivamente la metà destra di una stringa var destra = function(str){ var lunghezza = str.length;
// Funzione di aiuto var aiuto = function(indice){
// Caso Ricorsivo: Stampare la metà destra if(indice < lunghezza){
// Stampa i caratteri dall'indice fino alla fine dell'array console.log(str.substring(indice, lunghezza));
// Chiamata Ricorsiva: chiamare aiuto sulla metà destra aiuto(Math.ceil((lunghezza + indice)/2));
// Caso Base: Non fare niente
aiuto(0); }
Tempo polilogaritmico Si dice che un algoritmo è eseguito in tempo polilogaritmico se T(n) = O((log n)k), per una qualche costante k. Ad esempio, l'ordinamento di una catena di matrici può essere risolto in tempo polilogaritmico su una macchina ad accesso casuale parallelo.
Tempo sublineare Si dice che un algoritmo si esegue in tempo sublineare (spesso scritto tempo sub-lineare) se T(n) = o(n). In particolare questo include algoritmi con le complessità temporali definite sopra, nonché altri come l'algoritmo di ricerca di Grover O(n½).
Gli algoritmi tipici che sono esatti e tuttavia si eseguono in tempo sub-lineare usano l'elaborazione parallela (come fa il calcolo del determinante della matrice NC1), l'elaborazione non classica (come fa la ricerca di Grover), o alternativamente hanno assunzioni garantite sulla struttura degli input (come fanno la ricerca binaria in tempo logaritmico e molti algoritmi di manutenzione ad albero). Tuttavia, i linguaggi come l'insieme di tutte le stringhe che hanno 1-bit indicizzato dai primi bit log(n) possono dipendere da ogni bit dell'input ed essere però computabili in tempo sub-lineare.
Il termine specifico algoritmo in tempo sublineare è riservato solitamente ad algoritmi diversi da quelli di sopra in quanto sono eseguiti su modelli classici di macchine seriali e non sono consentite loro assunzioni anteriori sull'input. Essi possono tuttavia essere randomizzati, e in verità devono esserlo per quasi tutti i compiti più banali.
Poiché tale algoritmo deve fornire una risposta senza leggere l'intero input, i particolari dipendono fortemente dall'accesso consentito all'input. Solitamente per un input che è rappresentato come una stringa binaria b1,...,bk si assume che l'algoritmo possa nel tempo O(1) richiedere e ottenere il valore di bi per qualsiasi i.
Gli algoritmi in tempo sub-lineare sono tipicamente randomizzati, e forniscono solo soluzioni approssimate. Infatti, si può facilmente dimostrare che la proprietà di una stringa binaria che ha solo zeri (e nessun uno) non è decidibile da un algoritmo in tempo sub-lineare (non approssimato). Gli algoritmi in tempo sub-lineare emergono naturalmente nelle indagini sul collaudo delle proprietà.
Tempo lineare Si dice che un algoritmo impiega un tempo lineare, o tempo O(n), se la sua complessità temporale è O(n). Informalmente, questo significa che per dimensioni dell'input abbastanza grandi il tempo di esecuzione aumenta linearmente con la dimensione dell'input. Per esempio, una procedura che addiziona tutti gli elementi di una lista richiede un tempo proporzionale alla lunghezza della lista. Questa descrizione è lievemente inaccurata, poiché il tempo di esecuzione può deviare significativamente da una precisa proporzionalità, specialmente per piccoli valori di n.
Il tempo lineare è spesso visto come un attributo desiderabile per un algoritmo. Sono state investite molte ricerche nella creazione di algoritmi che esibiscono un tempo (quasi) lineare o migliore. Queste ricerche includono sia metodi software che hardware. Nel caso dell'hardware, alcuni algoritmi che, matematicamente parlando, non possono mai raggiungere un tempo lineare con modelli di computazione ordinari sono in grado di essere eseguiti in tempo lineare. Ci sono parecchie tecnologie hardware che sfruttano il parallelismo per ottenere questo. Un esempio è la memoria indirizzabile ai contenuti. Questo concetto di tempo lineare è usato negli algoritmi di accoppiamento delle stringhe come l'algoritmo di Boyer-Moore e l'algoritmo di Ukkonen.
Tempo linearitmico Una funzione linearitmica (combinazione di lineare e logaritmica) è una funzione della forma n · log n (cioè un prodotto di un termine lineare e di uno logaritmico). Si dice che un algoritmo è eseguito in tempo linearitmico se T(n) = O(n log n). In confronto ad altre funzioni, una funzione linearitmica ω(n), o(n1+ε) per ogni ε > 0, e Θ(n · log n). Perciò, un termine linearitmico cresce più velocemente di un termine lineare ma più lentamente di un qualsiasi polinomio in n con esponente strettamente maggiore di 1.
In molti casi, il tempo di esecuzione n · log n è semplicemente il risultato di eseguire un'operazione Θ(log n) n volte. Ad esempio, l'ordinamento ad albero binario crea un albero binario inserendo ciascun elemento del vettore (array) di dimensione n uno alla volta. Poiché l'operazione di inserimento su un albero binario di ricerca bilanciato impiega il tempo O(log n), l'intero algoritmo impiega un tempo linearitmico.