Teoria della complessità

La teoria della complessità si occupa di analizzare la complessità computazionale di un algoritmo ( analisi della complessità ). La teoria della complessità consente di individuare l'algoritmo più efficiente per risolvere un problema. Qualsiasi problema trattabile può essere risolto in modo computazionale seguendo varie strade ( algoritmi ). La teoria della complessità consente di comparare gli algoritmi al fine di scegliere quello migliore ossia quello più efficiente a parità di risultato ( efficacia ). Per ogni algoritmo viene individuata una funzione di complessità tale da associare il numero dei dati N da elaborare ( dimensione dei dati ) al numero di operazioni computazionali necessari per completare l'elaborazione.La funzione di complessità è indicata con il simbolo O seguito, tra parentesi, dalla funzione stessa. Ad esempio, la complessità O ( n^k ) indica una complessità computazionale in cui sono necessarie n^k operazioni o n^k unità di tempo, ipotizzando che ciascuna operazione richieda un tempo di esecuzione pari a un'unità di tempo ( es. nanosecondo ), per elaborare n dati in input.

• Complessità costante. La complessità costante caratterizza gli algoritmi che eseguono sempre un medesimo numero di operazioni indipendentemente dalla dimensione dei dati. Un esempio di algoritmo a complessità costante è l'algoritmo di inserimento di un record in un file. La complessità costante è indicata O ( 1 ).
• Complessità sottolineare. La complessità sottolineare si verifica quando in un algoritmo il numero delle operazioni da eseguire cresce in modo meno che proporzionale rispetto alla dimensione dei dati n. La complessità sottolineare è indicata O ( n^k ) con 0<k<1.
• Complessità lineare. La complessità lineare caratterizza gli algoritmi che eseguono un numero di operazioni proporzionale alla dimensione dei dati da analizzare ( algoritmi lineari ). La complessità lineare è indicata O ( n ) ossia O ( n^k ) con k=1.
• Complessità sovralineare. La complessità polinomiale si verifica quando il numero delle operazioni dell'algoritmo cresce in modo più che proporzionale rispetto alla dimensione dei dati. La complessità sottolineare è indicata O ( n^k ) con k>1 e k<n.
• Complessità polinomiale. La complessità polinomiale è un insieme che comprende diversi tipi di complessità. Sono indicate come complessità polinomiali la complessità costante, la complessità sottolineare, la complessità lineare e la complessità sovralineare.
• Complessità esponenziale. La complessità esponenziale si verifica quando il numero delle operazioni cresce in modo esponenziale alla dimensione n dei dati. Nella complessità esponenziale la dimensione dati n compare come esponente della funzione di complessità. La complessità esponenziale è indicata con O ( n^k ) con k≥n. Gli algoritmi con complessità esponenziale sono caratterizzati da tempi di esecuzioni proibitivi indipendentemente dalla velocità computazionale del computer utilizzato.