9 : Analisi degli Algoritmi Vers . 2.0 – Aprile 2022
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 ;
2 ) tempo di esecuzione : ossia il tempo di esecuzione legato al processo necessario alla sua esecuzione .
Tra le due risorse in mancanza di esplicita richiesta si considera prioritaria la risorsa “ tempo di esecuzione ” pertanto nel prosieguo della nostra analisi valuteremo esclusivamente il tempo di esecuzione di un processo legato ad un algoritmo . Per far ciò confronteremo tra loro due o più algoritmi equivalenti di una stessa classe di problemi sulla base degli stessi parametri in modo da potere effettuare un ’ analisi qualitativa degli stessi .
UN MODO NON ADATTO PER VALUTARE IL TEMPO DI ESECUZIONE DI UN ALGORITMO
Ipotizziamo di valutare il tempo di esecuzione di un algoritmo esprimendo il tempo nelle unità solari abituali ( cronometro con ore , minuti e secondi ). Per valutare quindi la bontà di un certo processo risolutivo relativo ad un determinato algoritmo è sufficiente cronometrarne il tempo impiegato per la sua esecuzione . Analogamente si fa per tutti i processi risolutivi equivalenti individuati . Secondo questo criterio confrontando semplicemente i tempi misurati sarà possibile individuare l ’ algoritmo più efficiente .
Questo metodo , apparentemente corretto , è assolutamente inaccettabile !!!
I risultati del test proposto sono inattendibili in quanto verranno a dipendere esclusivamente dalle condizioni in cui verrà eseguito il test e precisamente : - dalla velocità di esecuzione dell ’ elaboratore ; - dalla velocità d ’ interpretazione del programma traduttore ( compilatore o interprete ) utilizzato per la codifica ; - dalla dimensione e dalla disposizione dei dati di test forniti in input .
Appare evidente che un confronto può essere ritenuto valido solo se i diversi processi in esecuzione vengono testati nelle stesse condizioni ossia : - i diversi programmi sono tradotti utilizzando lo stesso traduttore ( compilatore o interprete ); - il test viene eseguito sullo stesso elaboratore dedicato ; - il test viene eseguito più volte con dati di input diversi per dimensione e disposizione .
Queste osservazioni ci portano ad affermare che in ogni caso non si può assolutamente valutare la complessità di un algoritmo servendosi dell ’ unità solari in quanto nonostante tutti gli accorgimenti più minuziosi che è possibile prendere , non può essere comunque effettuata un ’ analisi completa .
Per questo motivo si dice che per valutare correttamente la bontà di un algoritmo occorre considerare esclusivamente l ’ algoritmo in se ( i dati e le istruzioni utilizzate ) e non la sua implementazione .
Autore : Rio Chierego ( email : riochierego @ libero . it - sito web : www . riochierego . it ) Pag . 2