9 : Analisi degli Algoritmi Vers . 2.0 – Aprile 2022
IL MODO ADATTO PER VALUTARE IL TEMPO DI ESECUZIONE DI UN ALGORITMO
Un metodo più idoneo di valutazione del tempo di esecuzione di un algoritmo è quello di esprimerlo in funzione del numero di operazioni ( assegnazioni , confronti , operazioni , di I / O , operazioni aritmetiche , scambi , etc .) che l ’ algoritmo deve compiere per fornire i risultati .
Definiremo costo di un algoritmo il numero di operazioni necessarie a realizzare il suo processo risolutivo
Introduciamo le seguenti regole di valutazione per potere effettuare il calcolo del costo di un algoritmo dettagliato in un linguaggio di progettazione strutturato ( esempio PSEUDOCODIFICA ):
1 ) Vanno considerate solo le istruzioni comprese tra INIZIO e FINE senza includere queste due istruzioni nel calcolo relativo ;
2 ) Le istruzioni semplici quali lettura , scrittura , assegnazione , test ,… si ipotizza abbiano SEMPRE un costo pari ad 1 ;
3 ) Le istruzioni iterative ( quali MENTRE … FINE MENTRE , RIPETI .. FINCHE ’, PER … FINE PER ) hanno TUTTE un costo pari alla somma dei costi del test ( ossia 1 ) e del costo delle istruzioni contenute nel corpo del ciclo , moltiplicato il numero di volte per il quale esso viene eseguito . Si ribadesce che : - il test del ciclo , viene SEMPRE considerata un ’ istruzione semplice e quindi si ipotizza abbia costo uguale ad 1 ; - il corpo del ciclo avrà costo pari alla somma dei costi delle singole istruzioni calcolati in accordo con le regole qui proposte . N . B . per i cicli post-condizionali va tenuta in considerazione una verifica di test aggiuntiva .
4 ) L ’ istruzione di selezione unaria SE … ALLORA ha costo pari alla somma del costo del test ( ossia 1 ) più quello delle singole istruzioni contenute nel ramo ALLORA calcolate in accordo alle regole qui proposte .
L ’ istruzione di selezione binaria SE … ALLORA … ALTRIMENTI ha costo pari alla somma del costo del test ( ossia 1 ) più , per convenzione , quello massimo tra i costi delle singole istruzioni contenute nel ramo ALLORA e del ramo ALTRIMENTI calcolato in accordo alle regole qui proposte .
L ’ istruzione di selezione ennaria NEL CASO CHE …. FINE CASO ha costo pari alla somma del costo del test ( ossia 1 ) più , per convenzione , quello massimo tra i costi dei vari blocchi relativi alla lista dei valori oppure al ramo ALTRIMENTI calcolato in accordo alle regole qui proposte .
5 ) L ’ istruzione di chiamata di un sottoprogramma ( funzione o procedura ) ha costo pari alla somma del costo dell ’ istruzione di chiamata ( che per convenzione è pari ad 1 ) più il costo dell ’ intero sottoprogramma calcolato in accordo alle regole qui proposte ; N . B L ’ istruzione RITORNA si ipotizza abbia costo pari ad 1
6 ) L ’ istruzione composta ( ad esempio strutture di controllo annidate e blocchi di istruzioni ) ha una complessità pari alla somma dei costi delle singole istruzioni semplici che la compongono calcolati in accordo alle regole qui proposte .
I risultati ottenuti in accordo alle seguenti regole sono più affidabili rispetto ai precedenti benché risultino anch ’ essi approssimati per difetto in quanto è consuetudine occuparsi esclusivamente delle operazioni dal costo dominante ( confronti e moltiplicazioni ) trascurando le istruzioni meno onerose dal punto di vista esecutivo quali addizioni , sottrazioni , incrementi , decrementi .
Possiamo finalmente dire che , utilizzando questa tecnica di valutazione , il tempo di esecuzione di un qualsiasi algoritmo è proporzionale al suo costo . Appare evidente che , conoscendo il tempo di esecuzione di una istruzione di costo unitario ( tempo unitario ) espresso in secondi , basterà moltiplicare il costo complessivo dell ’ algoritmo per il tempo unitario per ottenere una stima attendibile riguardo al tempo totale di esecuzione dell ’ algoritmo .
Autore : Rio Chierego ( email : riochierego @ libero . it - sito web : www . riochierego . it ) Pag . 3