AlgoMOOC 05.01. La complessità computazionale

9
http://codemooc.org/algoritmi/ Algo 05.01 La complessità computazionale alessandro bogliolo

Transcript of AlgoMOOC 05.01. La complessità computazionale

Page 1: AlgoMOOC 05.01. La complessità computazionale

http://codemooc.org/algoritmi/

Algo 05.01

La complessità computazionale

alessandro bogliolo

Page 2: AlgoMOOC 05.01. La complessità computazionale

Algo 05.01

[email protected] q

uad

rato

Page 3: AlgoMOOC 05.01. La complessità computazionale

Algo 05.01

[email protected]

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.

Page 4: AlgoMOOC 05.01. La complessità computazionale

Algo 05.01

[email protected]

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

Page 5: AlgoMOOC 05.01. La complessità computazionale

Algo 05.01

[email protected] se

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

Page 6: AlgoMOOC 05.01. La complessità computazionale

Algo 05.01

[email protected] se

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

Page 7: AlgoMOOC 05.01. La complessità computazionale

Algo 05.01

[email protected] se

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)!

Page 8: AlgoMOOC 05.01. La complessità computazionale

Algo 05.01

[email protected]

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

Page 9: AlgoMOOC 05.01. La complessità computazionale

Algo 05.01

[email protected]

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