Teoria della complessità algoritmica
Questo articolo è uno stub, il che vuol dire che necessita di essere ampliato e corretto, secondo i canoni di Wikipedia. Se puoi, rendi anche questo articolo serio e dettagliato come dev'essere un articolo di enciclopedia, grazie.
| Table of contents |
|
2 Problemi NP e NP# 3 Spin glass e K-solvibilità 4 Vedi anche: 5 Link Esterni |
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 che cresce il 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 da analizzare 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.Definizione
