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

9 : Analisi degli Algoritmi Vers . 2.0 – Aprile 2022
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 ……………… PROCESSO 1

………………
………………
………………
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 EQUIVALENTI quello migliore confrontandoli dal punto di vista dell ’ efficienza sulla base di un analisi qualitativa delle loro istruzioni ”
Autore : Rio Chierego ( email : riochierego @ libero . it - sito web : www . riochierego . it ) Pag . 1