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

9 : Analisi degli Algoritmi Vers . 2.0 – Aprile 2022

Esempio 3 : calcolare il costo dei seguenti algoritmi :

ALGORITMO Alg _ C1 i : INT

INIZIO i � 1 MENTRE ( i ≤ 10 ) ESEGUI Scrivi (" Ciao !") i � i + 1 FINE MENTRE

FINE
ALGORITMO Alg _ C2 i : INT

INIZIO

PER i � 1 A 10 ESEGUI Scrivi (" Ciao !") i � i + 1 FINE PER
FINE
ALGORITMO Alg _ C3 i : INT

INIZIO i � 1 RIPETI Scrivi (" Ciao !") i � i + 1 FINCHE ’ ( i > 10 )

FINE
Ass Ncicli Test Scrivi Ass Ult . test Costo Alg _ C1 = 1 + ( 10 * ( 1 + 1 + 1 ) + 1 ) = 1 + 31 = 32
Generalizzando :
Ass Ncicli Test Scrivi Ass Ult . test
Costo Alg _ C1 = 1 + ( N * ( 1 + 1 + 1 ) + 1 ) = 3N + 2
Ass Ncicli Test Scrivi Ass Ult . test Costo Alg _ C2 = 1 + ( 10 * ( 1 + 1 + 1 ) + 1 ) = 1 + 31 = 32
Generalizzando :
Ass Ncicli Test Scrivi Ass Ult . test
Costo Alg _ C2 = 1 + ( N * ( 1 + 1 + 1 ) + 1 ) = 3N + 2
Ass Ncicli Test Scrivi Ass Costo Alg _ C3 = 1 + ( 10 * ( 1 + 1 + 1 ) ) = 1 + 30 = 31
Generalizzando :
Ass Ncicli Test Scrivi Ass
Costo Alg _ C3 = 1 + ( N * ( 1 + 1 + 1 ) ) = 3N + 1
N . B . in questo caso seppur in presenza di un impercettibile vantaggio nell ’ utilizzo di una ciclo di tipo RIPETI esso è di fatto trascurabile al crescere dellla dimensione del problema N .

Esempio 4 : calcolare il costo del seguente algoritmo :

ALGORITMO Alg _ D i : INT

INIZIO i � 1 MENTRE ( i ≤ N ) ESEGUI

SE ( i % 2 = 0 )
ALLORA k � i * 3 j � j + k ALTRIMENTI k � k / 2 Scrivi ( k ) FINE SE SE ( k + i % 3 )
ALLORA k � 2 * i FINE SE Scrivi (" Uffa !") i � i + 1 FINE MENTRE
FINE
Svolgimento :
Ass Ncicli Test M Ass Incr Ult . test M
Costo Alg _ D = 1 + N * ( 1 + Costo SE Bin + Costo SE Un + 1 + 1 ) + 1
dove
Test Ass Ass
Costo SE Bin = 1 + 1 + 1 = 3
Test
Ass
Costo SE Un = 1 + 1 = 2
Quindi sostituendo
Ass Ncicli Test M Ass Incr Ult . test M
Costo Alg _ D = 1 + N * ( 1 + 3 + 2 + 1 + 1 ) + 1 = 8N + 2
Autore : Rio Chierego ( email : riochierego @ libero . it - sito web : www . riochierego . it ) Pag . 5