AlgoMOOC 05.01. La complessità computazionale
9
http://codemooc.org/algoritmi/ Algo 05.01 La complessità computazionale alessandro bogliolo
-
Upload
alessandro-bogliolo -
Category
Education
-
view
117 -
download
2
Transcript of AlgoMOOC 05.01. La complessità computazionale
http://codemooc.org/algoritmi/
Algo 05.01
La complessità computazionale
alessandro bogliolo
Algo 05.01
dic
e e
trac
cia
di e
secu
zio
ne
La traccia di esecuzione è la sequenza delle istruzioni effettivamente eseguite.Di solito non coincide con il codice poiché le ripetizioni, le condizioni e le chiamate aprocedure o funzioni lo rendono non lineare.
Algo 05.01
cien
za e
co
mp
less
ità
Co
nti
amo
i p
assi
ele
men
tari
4*(controlloCiclo + 2*(controlloCiclo + moveForward) + turnRight)4*controlloCiclo + 8*controlloCiclo + 8*moveForward + 4*turnRight
Algo 05.01
i p
assi
d
ipen
do
no
dai
dat
i?Assegnamento+B(For+A(For+Incremento))Assegnamento+B*For + B*A(For+Incremento)1+B*1+B*A*2
Il computo dei passi eseguiti è dominato dal termineA*B
Algo 05.01
i p
assi
d
ipen
do
no
dai
dat
i?Assegnamento+A(For+Incremento)+B(For+Incremento)Assegnamento+(A+B)(For+Incremento)1+(A+B)*2
Il computo dei passi eseguiti è dominato dal termineA+B
Algo 05.01
i p
assi
d
ipen
do
no
dai
dat
i?Calcolo di N!, che si legge N fattoriale. Prodotto dei primi N numeri interi
Il ciclo invoca N volte la funzione moltiplica per calcolare:• La prima volta: 1*1• La seconda volta: 1*2• La terza volta: 2*3• La quarta volta: 6*4• …• L’ultima volta: (N-1)!*NPer il generico valore di i, si moltiplica i per il valore di fact già calcolato, che vale (i-1)!
Se l’unica istruzione elementare di cui disponiamo è l’incremento unitario, il numero di passi complessivi è pari a 1*1 + 1*2 + 2*3 + 6*4 + … + (N-1)!*NCome dire:1! + 2! + 3! + 4! + 5! + … + N!Dominato da (N+1)!
Algo 05.01
ole
per
il c
alco
lo
del
la c
om
ple
ssit
à1. Il numero di ripetizioni di
cicli nidificati si moltiplica 3. Procedure e funzioni incapsulano il codice, ma non ne nascondono la complessità
2. Il numero di ripetizioni di cicli consecutivi si somma
Algo 05.01
ali p
assi
so
no
dav
vero
ele
men
tari
?Addizione e moltiplicazione possono essere considerate istruzioni elementari solo se:1. il loro tempo di esecuzione
può essere ritenuto costante indipendentemente dal valore degli operandi
2. l’esecutore le conosce senza bisogno di descriverle in termini di passi più semplici
Nei calcolatori questo è vero finché i numeri non superano le dimensioni della rappresentazione adottata da chi li ha progettati
