Tempo di computazione (Running Time) di programmi

Tempo di computazione (Running Time) di Tempo di computazione (Running Time) di programmiprogrammi

Misure del tempo: Misure del tempo: metodi principali1. Benchmarking2. Analisi Benchmarking: usato per confrontare

programmi. Si cerca una collezione di input che sia

rappresentativa dell’insieme dei possibili dati reali. Il giudizio di confronto viene espresso sugli input scelti.

Es. per algoritmi di sorting si può scegliere la collezione:

• prime 20 cifre • codici postali italiani• numeri telefonici di Roma


ANALISI: analizza il r.t. di un dato programma

Si raggruppano input per dimensione(es. ordinamento: dimensione= numero elementi da

ordinare, sisteme di n equazioni in n incognite: dimensione=n)

Running time: funzione T(n), con n=dimensione input,

che rappresenta il numero di “unità di tempo” usate

dall’algoritmo

Unità di tempo varia: es. numero di istruzioni semplici in

linguaggio usato (C).Tempo effettivo dipende da vari paramentri:

velocità del processore usato, compilatore,….


Worst case (caso peggiore): su diversi input di stessa dimensione n si possono avere r.t. differentiT(n)=worst case r.t. = max tempo su qualsiasi input di dimentsione n

Es. cerca min A[0..n-1] (dimensione=n)1. small=0;2. for(j=1; j<n; j++) 3. if(A[j]<A[small]) 4. small=j;

| Linea | Numero operazioni | 1. | 1 | 2. | 1 + n + (n-1) =2n | 3. | n-1 | 4. | n-1 (worst case)

TOTALE: 1+2n+2(n-1)=4n-1 T(n)=4n-1


Confronto di r.t. Dato un problema consideriamo 2 algoritmi A e B con r.t. T’(n) e T’’(n)

T’(n)=100n T’’(n)=2n2

T’’(n) n<50, T’’(n) < T’(n)

T’(n) n>50, T’’(n) > T’(n) n=100, T’’(n) = 2 T’(n)

n=1000, T’’(n) = 20 T’(n)

n


T’(n)=100n T’’(n)=2n2

Unità di tempo= 1ms (millisec) 1000 operazioni/sec

sec (1000ms) | max n per A | max n per B || (100n=1000*sec) | ( 2n2=1000*sec) |

1 | 10 | 22 |10 | 100 | 70 |100 | 1000 | 223 |1000 | 10000 | 707 |

Se calcolatori diventano 100 volte più veloci (unità di tempo =1/100 di ms 100.000

operazioni/sec)

In 10 sec A passa da n=100 ad n=10000 (*100)

B passa da n=70 ad n=707 (*10)

Notazione O-grande e r.t. approssimatoNotazione O-grande e r.t. approssimato

Dato un programma ed un input r.t. dipende ancora da

1. Calcolatore usato (velocità di esecuzione istruzioni)2. Compilatore (numero istruzioni macchina/istruzione

C)

Quindi non ha senso parlare di tempo in sec per analizzare un algoritmo.

Per nascondere effetti di 1. e 2. si usa la notazione O-grande (big-Oh) che ignora le costanti

Es. 4m-1=O(m) (ignorando la costante moltiplicativa 4 e quella additiva 1)


Un r.t. T(n) si assume essere definito solo per n>0 e

che T(n)>0 per ogni n.

Definizione Dati il r.t. T(n) ed una funzione f(n), definita per ogni intero n>0,

T(n)=O(f(n)) Esistono n0>0 e c>0 tali che per ogni n>n0 risulta T(n)<cf(n)

N.B. Notazione Asintotica (vale per n ‘’grande’’)


Definizione Dati il r.t. T(n) ed una funzione f(n), definita per ogni intero n>0,

T(n)=O(f(n)) Esistono n0>0 e c>0 tali che per ogni n>n0 risulta T(n)<cf(n)

Es. Dato T(0)=0 e T(n)=(n+1)*(n+2), n>0 mostriamo che T(n)= O(n2). (cioè f(n)=n2) Prendiamo n0=1, c=6:

T(n) =(n+1)(n+2)=n2+3n+2 <n2+3n2+2n2 (per n>1, n0=1<n<n2) =6n2=c n2= c f(n)


Costanti non hanno valore T(n)=O(d T(n)), per ogni costante d

Infatti: siano n0=0, c=1/d. Si ha

T(n)=(1/d) d T(n)= c (d T(n))

Notazione O-grande e r.t. approssimatoNotazione O-grande e r.t. approssimatoLow-order terms non hanno valore Dato il

polinomio T(n)=aknk+ak-1nk-1+…+a1n+a0, con ak>0

risulta T(n)=O(nk)Prova: )0 ogniper (nota ,1 Siano

0,00 kicaacn i

k

aii

i

.

)1 (essendo

(n) ha Si

0,0

0,0

0,00

kkk

aii

k

kk

aii

ik

aii

ik

ii

cncnan

nna

nanaT

i

i

i


Low-order terms non hanno valore Dato il polinomio T(n)=aknk+ak-1nk-1+…+a1n+a0, con ak>0

risulta T(n)=O(nk)

55555

35235

0,00

235

nn14n3n n 10

13n n 1012n-3n n 10T(n)

141310 ,1

12n-3n n 10T(n) Es.

c

acnk

aii

i


Tasso di crescita Ha valore solo il termine che cresce più rapidamente. Se g(n) cresce più rap. di h(n)

g(n)+h(n)=O(g(n))

0)(

)(lim

se h(n) di erapidamentpiù cresce g(n) funzione La

n

ng

nh

Es. T(n)=2n+n3=O(2n), infatti

02

lim3

n

n

n

Verificarlo in modo diretto esibendo le costanti n0 e c


Transitività Se f(n)=O(g(n)) e g(n)=O(h(n)) allora

f(n)=O(h(n))

f(n)=O(g(n)) Esistono c’, n’ tali che f(n) << c’ c’ g(n) g(n)

per ogni nper ogni n>>n’n’

g(n)=O(h(n)) Esistono c’’, n’’ tali che g(n) << c’’ h(n)c’’ h(n)

per ogni nper ogni n>>n’’n’’

Quindi, prendiamo nQuindi, prendiamo n00=max { n’,n’’ } e c=c’c’’=max { n’,n’’ } e c=c’c’’

Per nPer n>n0 f(n) < c’ g(n)c’ g(n) < c’ (c’’ h(n)) = c h(n)


Si vuole come O-grande la funzione con il minimo tasso

di crescita!!!

Es. f(n)=12n +3, si ha f(n)=O(n)

risulta anche f(n)=O(n2), f(n)=O(n3), f(n)=O(2n), ….

ma non è quello che vogliamo.


Esercizio.Mostrare che g(n)+f(n)=O(max{f(n),g(n)})

Esercizio.Mostrare che se T(n)=O(f(n)) e S(n)=O(g(n))

allora T(n)S(n)=O(f(n)g(n))

Running Time di programmiRunning Time di programmi

Trova f(n) tale che T(n)=O(f(n))

Istruzioni semplici (assegnamento, confronto,…) tempo costante O(1)

Cicli for: for (i=1,i<=n,i++) I 1. se I=operazione semplice risulta O(n) 2. Se I ha r.t. O(f(n)) risulta O(nf(n)) es. for(i=1,i<=n,i++) A[i]=1 T(n)=O(n)

for(i=1,i<=n,i++)

for(j=1,j<=n,i++) A[i]=A[i]+A[j] T(n)=O(n*n) =O(n2)


If (C) I else I’: (normalmente C è O(1))

1. se I,I’ sono istruzioni semplici O(1) 2. se I ha r.t. O(f(n)) e I’ ha r.t. O(g(n))

O(max (f(n), g(n)) es. if (A[0]=0) for(i=1,i<=n,i++) A[i]=1; else for(i=1,i<=n,i++)

for(j=1,j<=n,i++) A[i]=A[i]+A[j]

T(n)=O(max (n, n2)) =O(n2)


Cicli while e do while: simili al ciclo for (non conosciamo esplicitamente il numero di

iterazioni)

es. Dato un array A di n elementi

i=0; while (x<>A[i] && i<n) i=i+1;

(caso peggiore: n iterazioni) T(n)=nO(1)=O(n)


Sequenze di istruzioni: si devono sommare i tempi

delle singole istruzioni. Si usa la regola della somma.

Date con

{I1;

I2;...Im;}

O(f1)

O(f2)...O(fm)

Risulta O(f1(n)) + O(f2(n))+…+ O(fm(n))= O(fi(n))

fj(n)=O(fi(n)) per ogni j diverso da i.


Chiamate a funzioni: si deve sommare il tempodella funzione chiamata.(se A chiama B: si calcola il r.t. di B e si somma

al r.t. delle altre istruzioni di A)

Chiamate ricorsive: determiniamo T(n) in modo induttivo

1. Tempo di una chiamata che non usa ricorsione = t (=O(1))

2. Si esprime T(n) in termini del tempo T(n’) della chiamata ricorsiva


Chiamate ricorsive: determiniamo T(n) in modo induttivo

1. Tempo di una chiamata che non usa ricorsione=t (=O(1))

2. Si esprime T(n) in termini del tempo T(n’) della chiamata ricorsiva

Es. int fact(int n){ if (n<=1) return 1;

else return n*fact(n-1)}

T(1)=tT(n)=T(n-1)+c




T(1)=tT(n)=c+ T(n-1)

Vogliamo il valore di T(n) (non dipendente da T(n’))

Abbiamo T(n)=c+ T(n-1) =c+ c+ T(n-2)= 2c +T(n-2)




T(1)=tT(n)=c+ T(n-1)

Abbiamo T(n)=c+T(n-1) =c+ c+ T(n-2)= 2c +T(n-2) =2c +c +T(n-3)=3c +T(n-3)




T(1)=tT(n)=c+ T(n-1)

Abbiamo T(n)=c+T(n-1) =c+ c+ T(n-2)= 2c +T(n-2) =2c +c +T(n-3)=3c +T(n-3) … =ic +T(n-i) (per i=n-1) =(n-1)c+T(1) =(n-1)c+t= O(n)


Esercizio. Dimostrare per induzione su n che la relazione di ricorrenza

T(1)=tT(n)=c+ T(n-1)

ha come soluzione T(n)=(n-1)c + t

Base n=1. T(1)=t=(1-1)c+t. OK.

Passo. Sia n> 1. Assumiamo T(n)=(n-1)c + t. Consideriamo T(n+1)

T(n+1)=c + T(n) (per definizione) =c + (n-1)c + t (per i.i.)

= nc +t


Esercizio. Considerare la relazione di ricorrenza T(0)=T(1)= 1T(n)=2 T(n-2)

1. Determinare T(2), T(3), T(4), T(5): T(2)=2, T(3)=2, T(4)=4, T(5)=4

1. Determinare T(n) in termini di T(n-4): T(n)=4 T(n-4)

2. Determinare T(n) in termini di T(n-6): T(n)=8 T(n-6)

3. Determinare T(n) in termini di T(n-2i): T(n)=2i T(n-2i)

4. Determinare T(n): se n pari, i=n/2, T(n-2i)=T(0) T(n)=2n/2T(0)=2n/2

se n disp., i=(n-1)/2, T(n-2i)=T(1) T(n)=2(n-1)/2T(1) =2(n-1)/2

Soluzioni Relazioni di ricorrenzaSoluzioni Relazioni di ricorrenza

1. T(1)=aT(n)= b+T(n-1), n>1 T(n)=(n-1)b+a

2. T(k)=a T(n)=T(n-1)+g(n) T(n)=a + g(k+1)+…+g(n)

T(n) = g(n)+T(n-1) = g(n)+g(n-1)+T(n-2)=… … = g(n)+g(n-1)+…+g(k+1)+T(k)

3. T(1)=1 T(n)=T(n-1)+n (g(i)=i) T(n)=1 + 2+…

+n=n(n+1)/2


4. T(1)=a T(n)=2T(n/2)+g(n)

angnT jn

n

j

j

)(2)( 2

1log

0

2

ang

n n-inTg

nTnTngng

nTngng

nTngnT

j

i

n

n

j

j

iiini

j

i

iiii

)(2

]2 ,1log[Per )2/(2)(2

)2/(2)2/(2...)2/(2)(

...

)4/(4)2/(2)(

)2/(2)()(

2

1log

0

1112

0

11

2


4. T(1)=a T(n)=2T(n/2)+g

ngaangn

ang

ang

angnT

n

n

j

j

n

j

j

)(

2

2

2)(

2

2

2

log

1log

0

1log

0


4. T(1)=a T(n)=2T(n/2)+n

))(log(

)(log

)2/(2)(

2

2

1log

0

1log

0

2

2

nnO

annn

ann

annnT

n

j

jn

j

j

Tempo di computazione (Running Time) di programmi

Documents

Transcript of Tempo di computazione (Running Time) di programmi