Teoria della complessità algoritmica
La Teoria della Complessità si occupa di determinare la complessità di un algoritmo. Per complessità si intende una funzione che associa il numero di dati da trattare al numero di operazioni da eseguire per trattare i suddetti dati. Il simbolo utilizzato è una o minuscola "o" seguito da una parentesi dove è indicata la complessità come una funzione che dipende da N, dove N è il numero che rappresenta i dati in ingresso. Quindi o(N) rappresenta un algoritmo la cui funzione complessità cresce in modo lineare (cresce come una retta). o(N²)rappresenta un algoritmo la cui funzione complessità cresce come un quadrato (quindi un raddoppio dei dati in ingresso provoca una quadruplicazione delle operazioni da eseguire).
La complessità di molti algoritmi è pesantemente influenzata dai dati in ingresso. In questo caso quando si calcola la complessita si considera il caso ottimo, il caso pessimo e il caso medio.
Il caso ottimo è il caso in cui i dati sono i migliori dati possibili per l'algoritmo, cioè quelli che richiedono meno elaborazioni per essere trattati.
Il caso pessimo invece prevede i dati più sfavorevoli per l'algoritmo.
Il caso medio è il caso più utile da analizzare perché fornisce un reale indicatore della complessità dell'algoritmo ma tendenzialmente è anche quello più complesso dato che spesso è difficile determinare quali sono i dati medi. A volte per risolvere il problema del caso medio si preferisce eseguire molte simulazioni dell'algoritmo e poi dai tempi ottenuti con le simulazione estrarre una formula che approssimi adeguatamente l'andamento medio.
| Indice |
Problemi P, NP, NP-hard, NP completi
I vari problemi possono essere suddivisi in classi a seconda del tempo occorrente all'algoritmo "più rapido" per la loro risoluzione. La rapidità o meno di un algoritmo è definita come il numero di operazioni necessarie nel caso peggiore nel caso asintotico in cui la dimensione del problema stesso tende a infinito, quindi viene solo considerato il suo ordine di grandezza. Le principali categorie sono:
Problemi P, per i quali è noto un algoritmo che termina in tempo polinomiale rispetto alla dimensione dei dati. Un esempio tipico è l'ordinamento di n valori, per cui esistono algoritmi che garantiscono la terminazione in O(nlogn) operazioni. La P sta per polinomiale.
Problemi NP, per i quali è noto un algoritmo che termina in tempo polinomiale rispetto alla dimensione dei dati nel caso si possa utilizzare un numero indeterminato di macchine in parallelo. Due formulazioni equivalenti sono affermare che l'algoritmo termina in tempo polinomiale con l'"algoritmo di Gastone" (ogni volta che si deve fare una scelta, si imbrocca sempre quella corretta), oppure che la verifica di una soluzione può essere effettuata in tempo polinomiale. La sigla NP sta per polinomiale nondeterministico: pensarlo come "non polinomiale" è sbagliato, anche se è vero che tutti gli algoritmi noti risolvono il problema in tempo esponenziale rispetto a n.
Problemi NP-hard, che sono tali che un algoritmo per risolvere uno di questi problemi può essere convertito in un algoritmo per risolvere un qualunque problema NP. In pratica, questi problemi sono almeno complicati quanto un qualunque problema NP, anche se potrebbero esserlo di più.
Problemi NP completi, che sono sia NP che NP-hard. Esempi di questa classe di problemi sono il problema del commesso viaggiatore (calcolare il percorso più breve che tocchi N città e ritorni al punto iniziale) o del riempimento dello zaino (dato uno zaino che può portare al massimo un peso P, e un insieme di N pesi differenti, trovare il massimo valore che può essere messo nello zaino).
È immediato vedere che i problemi P sono anche NP. Il viceversa non è noto: ad esempio la programmazione lineare è stata creduta per lungo tempo essere NP fino a che L. Khachiyan ha trovato nel 1979 un algoritmo polinomiale per la sua risoluzione. La questione P=NP, se cioè per ogni problema NP esiste un algoritmo polinomiale, è una delle maggiori questioni aperte dell'informatica, anche se non è detto che abbia una ricaduta pratica: ai fini del calcolo, infatti, un problema risolubile in O(n10) operazioni non è molto più trattabile al crescere di n di un problema risolubile in O(2n) operazioni. L'importanza di tale congettura ne ha fatto uno dei problemi per il millennio.