9 : Analisi degli Algoritmi Vers . 2.0 – Aprile 2022

Esempio 1 : calcolare il costo del seguente algoritmo :

ALGORITMO Alg _ A i , n , som : INT

FUNZIONE somma ( VAL x : INT ; VAL y : INT ): INT s : INT

INIZIO Scrivi (“ Inserisci un numero ”) Leggi ( N ) i � 1 som � 0 MENTRE ( i ≤ N ) ESEGUI som � somma ( i , som ) i � i + 1 FINE MENTRE Scrivi (“ La somma richiesta è ”) Scrivi ( som ) FINE

INIZIO s � x + y RITORNA ( s ) FINE

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

N . B . Si osservi che dalla relazione 6N + 7 per N = 10 si ottiene esattamente il valore 67 calcolato prima

Esempio 2 : calcolare il costo del seguente algoritmo :

ALGORITMO Alg _ B x , y , r , s , z : INT

INIZIO Leggi ( x ) Leggi ( y ) s � 0 SE ( x < 0 )

ALLORA SE ( y < 0 )

ALLORA r � 1

ALTRIMENTI r � 2 s � 1 FINE SE z � 1 FINE SE

FINE

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