Tempo di computazione (Running Time) di programmi
Misure del tempo: metodi principali
1. Benchmarking
2. 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 p
codici postali italiani
numeri telefonici di Roma
Tempo di computazione (Running Time) di programmi
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,….
Tempo di computazione (Running Time) di programmi
Worst case (caso peggiore): su diversi input di stessa
dimensione n si possono avere r.t. differenti
T(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
1.
2.
3.
4.
|
|
|
|
|
Numero operazioni
1
1 + n + (n-1) =2n
n-1
n-1 (worst case)
TOTALE: 1+2n+2(n-1)=4n-1  T(n)=4n-1
Tempo di computazione (Running Time) di programmi
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)
T’(n)
n
n<50,
T’’(n) < T’(n)
n>50,
T’’(n) > T’(n)
n=100,
T’’(n) = 2 T’(n)
n=1000,
T’’(n) = 20 T’(n)
Tempo di computazione (Running Time) di programmi
T’(n)=100n
T’’(n)=2n2
Unità di tempo= 1ms (millisec)  1000 operazioni/sec
sec (1000ms) | max n per A
| (100n=1000*sec)
1
10
100
1000
|
|
|
|
10
100
1000
10000
| max n per B
|
|
|
|
|
|
|
|
|
| ( 2n2=1000*sec)
22
70
223
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. 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)
Notazione O-grande e r.t. approssimato
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’’)
Notazione O-grande e r.t. approssimato
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)
Notazione O-grande e r.t. approssimato
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. approssimato
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)
Prova:
Siano n0  1,
k
a
c
i  0 , ai  0
i
k
Si ha
(nota ai  c per ogni 0  i  k )
T (n)   ai n i 
i 0

k
k
a
n
 i
k
i
a
n
 i
i  0 , ai  0
(essendo 1  n)
i  0 , ai  0
 nk
k
k
k
a

n
c

cn
.
 i
i  0 , ai  0
Notazione O-grande e r.t. approssimato
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)
Es. T(n)  10 n 5  3n 3 - 2n 2  1
n0  1,
c
k
a
i  0 , ai  0
i
 10  3  1  14
T(n)  10 n 5  3n 3 - 2n 2  1  10 n 5  3n 3  1
 10 n 5  3n 5  n 5  14n 5  cn 5
Notazione O-grande e r.t. approssimato
La funzione g(n) cresce più rapidament e di h(n) se
h( n)
lim
0
n  g ( n )
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))
Es. T(n)=2n+n3=O(2n), infatti
n3
lim n  0
n  2
Verificarlo in modo diretto esibendo le costanti n0 e c
Notazione O-grande e r.t. approssimato
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’ g(n)
per ogni n>n’
g(n)=O(h(n))
 Esistono c’’, n’’ tali che g(n) < c’’ h(n)
per ogni n>n’’
Quindi, prendiamo n0=max { n’,n’’ } e c=c’c’’
Per n>n0
f(n) < c’ g(n) < c’ (c’’ h(n)) = c h(n)
Notazione O-grande e r.t. approssimato
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.
Notazione O-grande e r.t. approssimato
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 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)
Running Time di programmi
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)
Running Time di programmi
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)
Running Time di programmi
Sequenze di istruzioni: si devono sommare i tempi
delle singole istruzioni. Si usa la regola della somma.
Date
{I1;
I2;
.
.
.
Im;}
con
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.
Running Time di programmi
Chiamate a funzioni: si deve sommare il tempo
della 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
Running Time di programmi
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)=t
T(n)=T(n-1)+c
Running Time di programmi
Es. int fact(int n)
{ if (n<=1) return 1;
else return n*fact(n-1)}
T(1)=t
T(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)
Running Time di programmi
Es. int fact(int n)
{ if (n<=1) return 1;
else return n*fact(n-1)}
T(1)=t
T(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)
Running Time di programmi
Es. int fact(int n)
{ if (n<=1) return 1;
else return n*fact(n-1)}
T(1)=t
T(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)
Running Time di programmi
Esercizio. Dimostrare per induzione su n che la
relazione di ricorrenza
T(1)=t
T(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
Running Time di programmi
Esercizio. Considerare la relazione di ricorrenza
T(0)=T(1)= 1
T(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.
4.
se
se
Determinare T(n) in termini di T(n-2i): T(n)=2i T(n-2i)
Determinare T(n):
n pari,
i=n/2, T(n-2i)=T(0) T(n)=2n/2T(0)=2n/2
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 ricorrenza
1. T(1)=a
T(n)= b+T(n-1), n>1
2. T(k)=a
T(n)=T(n-1)+g(n)
 T(n)=(n-1)b+a
 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
Soluzioni Relazioni di ricorrenza
4. T(1)=a
T(n)=2T(n/2)+g(n)

T ( n) 
log2 n 1
n )  an
2
g
(
2j

j
j 0
T (n)  g (n)  2T (n / 2) 
 g (n)  2 g (n / 2)  4T (n / 4)
...
i 1
i 1
 g (n)  2 g (n / 2)  ...  2 T (n / 2 )  2 T (n / 2 )
i
i
  2 g(
i
j 0

log2 n 1
n
i 1
2i
)  2 T (n / 2 ) [Per i  log n-1, 2
j
n )  an
2
g
(

2j
j 0
i 1
i
i 1
 n]
Soluzioni Relazioni di ricorrenza
4. T(1)=a
T(n)=2T(n/2)+g

T ( n) 
log2 n 1
j
2
 g  an
j 0
g
log2 n 1
2
j
 an
j 0
 g 2log2 n  an
 gn  an  (a  g )n
Soluzioni Relazioni di ricorrenza
4. T(1)=a
T(n)=2T(n/2)+n

T ( n) 
log2 n 1
 2 (n / 2 )  an
j
j 0

log2 n 1
 n  an
j 0
 n(log 2 n)  an
 O(n(log 2 n))
j