OKPEDIA ALGORITMO

Complessità esponenziale

La complessità esponenziale è un tipo di complessità computazionale degli algoritmi. Si parla di complessità esponenziale quando il numero delle operazioni di un algoritmo O ( nk ) cresce in modo esponenziale rispetto alla dimensione dei dati da elaborare ( n ). In un algoritmo a complessità esponenziale la funzione di complessità è indicata con O ( nk ) con k≥n. Ad esempio, un algoritmo con funzione di complessità O ( 2n+n ) è un algoritmo con complessità esponenziale. Gli algoritmi con complessità esponenziale sono caratterizzati da una complessità spaziale e/o temporale proibitiva. Il tempo di esecuzione può durare anche anni o secoli e il consumo di risorse del computer ( memoria ) può estendersi ben oltre le capacità massime degli attuali computer. Quando un problema è risolvibile computazionalmente soltanto con algoritmi a complessità esponenziale viene detto problema intrattabile. La complessità esponenziale è oggetto di studio dell'informatica nella teoria della complessità computazionale.

https://www.okpedia.it/complessita_esponenziale


Segnala un errore o invia un suggerimento per migliorare la pagina



FacebookTwitterLinkedinLinkedin