9 : Analisi degli Algoritmi Vers . 2.0 – Aprile 2022
ALGORITMO Alg _ A i , n , som : INT
FUNZIONE somma ( VAL x : INT ; VAL y : INT ): INT s : INT
Supponendo che sia N = 10 allora
Test Incr Ass chiamata corpo num . cicli Ult . Test costo Alg _ A = 4 + ( 1 + 1 + 1 + costo chiamata somma ( ) + costo somma ( )) * 10 + 1 + 2
costo Alg _ A = 4 + ( 3 + 1 + 2 ) * 10 + 1 + 2 = 67 N . B . Il costo della funzione somma ( ) è pari a 2 , poiché l ’ istruzione RITORNA ha costo pari ad 1
in generale per un N generico
Test Incr |
Ass |
chiamata |
corpo |
num . cicli |
Ult . Test |
costo Alg _ A = 4 + ( 1 + 1 + 1 + costo chiamata somma ( ) + costo somma ( )) * N |
+ 1 |
+ 2 |
costo Alg _ A = 6 N + 7 |
|
|
N . B . Si osservi che dalla relazione 6N + 7 per N = 10 si ottiene esattamente il valore 67 calcolato prima
ALGORITMO Alg _ B x , y , r , s , z : INT
ALLORA SE ( y < 0 )
ALLORA r � 1
ALTRIMENTI r � 2 s � 1 FINE SE z � 1 FINE SE
Test costo Alg _ B = 3 + 1 + costo del SE esterno ( ALLORA )
Test costo del SE esterno ( ALLORA ) = 1 + costo del SE interno ( ALTRIMENTI ) + 1 = 1 + 2 + 1 = 4
costo Alg _ B = 3 + 1 + 4 = 8
Ass
Autore : Rio Chierego ( email : riochierego @ libero . it - sito web : www . riochierego . it ) Pag . 4