Analisi della complessità

L'analisi della complessità studia la complessità dei problemi. Si distingue da quella degli algoritmi in quanto non analizza la procedura utilizzata per la risoluzione di un problema (algoritmo) bensì la complessità stessa del problema. I problemi sono classificati in classi di complessità P e NP indipendentemente dall'algoritmo utilizzato. L'analisi della complessità ha lo scopo di stabilire se un problema può essere affrontato da un algoritmo, ossia se l'algoritmo può formulare una soluzione al problema e verificare l'ipotesi in un tempo polinomiale accettabile. La complessità dell'algoritmo è misurata sia nella quantità di tempo di elaborazione necessaria per giungere ad una soluzione ( complessità temporale ) sia nella quantità di risorse hardware necessarie per l'esecuzione dell'algoritmo e l'elaborazione dei dati ( complessità spaziale ).