4° Anno TEORIA 1. Complessità computazionale di un algoritmo

9: Analisi degli Algoritmi Vers.1.1 – Giugno 2009 9. ANALISI DEGLI ALGORITMI Abbiamo visto che in informatica esistono molte strade per risolvere uno stesso problema ossia esistono in genere più processi risolutivi equivalenti in grado a partire dagli stessi dati di input di ricavare gli stessi dati di output. Quindi in informatica ci si occupa spesso durante la fase di analisi, per quanto possibile, di trovare “buone soluzioni” di un problema ossia ci si sforza di trovare soluzioni quanto più “economiche” possibile in termini di “efficienza” in grado di risparmiare per quanto possibile “tempo di esecuzione” e “spazio di memoria”. Domanda chiave: Quali sono i criteri da seguire per valutare la bontà di un algoritmo? Rispetto ad un qualsiasi algoritmo dobbiamo considerare i seguenti due aspetti: a) la sua organizzazione interna: ossia l’organizzazione delle sue strutture di controllo e delle strutture dati utilizzate; b) le risorse necessarie per eseguirlo: (in particolare la memoria ed il processore) strettamente legate allo spazio occupato ed al tempo di esecuzione. Ricordiamo che ogni algoritmo che risolve un determinato problema può essere tradotto in un programma scritto in un qualsiasi linguaggio di programmazione e che tale programma verrà trasformato in un processo a tempo di esecuzione. PROGRAMMA 1 ALGORITMO 1 PROBLEMA ……………… ……………… PROCESSO 1 PROGRAMMA M ……………… ……………… PROCESSO K ALGORITMO N Per valutare oggettivamente la bontà di un algoritmo non ci riferiremo direttamente all’algoritmo in quanto tale, bensì alle risorse (tempo di esecuzione e spazio di allocazione) che utilizzerà quando verrà trasformato in processo ossia in entità dinamica a tempo di esecuzione. La parte dell’informatica che si occupa dello studio e dell’individuazione della complessità di calcolo o computazionale di un algoritmo si chiama analisi computazionale. La conoscenza dei principi di tale disciplina ci permette di ampliare il nostro obbiettivo di programmazione passando dall’iniziale: “dato un problema trovare un algoritmo corretto e funzionante che ne descriva il relativo procedimento risolutivo e codificarlo in un determinato linguaggio di programmazione (per noi il C)” al più completo: “dato un problema trovare tra gli algoritmi risolutivi possibili quello migliore confrontandoli dal punto di vista dell’efficienza sulla base di un analisi qualitativa delle sue istruzioni” Siamo quindi interessati costruire algoritmi che abbiano una organizzazione interna tale da minimizzare le risorse utilizzate ossia: 1) spazio di memoria: ossia l’area di memoria (di lavoro) occupata da un processo durante la sua esecuzione riferendoci sia a quella necessaria per memorizzare le strutture dati utilizzate sia a quella necessaria per memorizzare il codice stesso, i suoi dati di input e di output ed i risultati intermedi; Autore: Rio Chierego (email: riochierego@libero.it - sito web: www.riochierego.it) Pag. 1