complessità temporale

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 5n3 + 3n, 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.