Tempo di computazione (Running Time) di programmi Misure del tempo: Misure del tempo: metodi...
-
Upload
domenica-masini -
Category
Documents
-
view
215 -
download
1
Transcript of Tempo di computazione (Running Time) di programmi Misure del tempo: Misure del tempo: metodi...
Tempo di computazione (Running Time) di Tempo di computazione (Running Time) di programmiprogrammi
Misure del tempo: Misure del tempo: metodi principali1. Benchmarking2. Analisi
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.
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
Tempo di computazione (Running Time) di Tempo di computazione (Running Time) di programmiprogrammi
ANALISI: analizza il r.t. di un dato programma
Si raggruppano input per dimensione(es. ordinamento: dimensione = numero elementi da
ordinare, sistema di n equazioni in n incognite: dimensione = n)
Tempo di computazione (Running Time) di Tempo di computazione (Running Time) di programmiprogrammi
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
Tempo di computazione (Running Time) di Tempo di computazione (Running Time) di programmiprogrammi
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 Tempo di computazione (Running Time) di programmiprogrammi
Worst case (caso peggiore): su diversi input di stessa
dimensione n si possono avere r.t. differenti
Tempo di computazione (Running Time) di Tempo di computazione (Running Time) di programmiprogrammi
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
Tempo di computazione (Running Time) di Tempo di computazione (Running Time) di programmiprogrammi
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;
Tempo di computazione (Running Time) di Tempo di computazione (Running Time) di programmiprogrammi
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
Tempo di computazione (Running Time) di Tempo di computazione (Running Time) di programmiprogrammi
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
Tempo di computazione (Running Time) di Tempo di computazione (Running Time) di programmiprogrammi
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 |
Tempo di computazione (Running Time) di Tempo di computazione (Running Time) di programmiprogrammi
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.
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)
Notazione O-grande e r.t. approssimatoNotazione O-grande e r.t. approssimato
Un r.t. T(n) si assume essre 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)< c f(n)
Notazione O-grande e r.t. approssimatoNotazione O-grande e r.t. approssimato
Un r.t. T(n) si assume essre 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)
Es. Dato T(0)=0 e T(n)=(n+1)*(n+2), n>0 mostriamo che T(n)= O(n2). (cioè f(n)=n2)
Notazione O-grande e r.t. approssimatoNotazione O-grande e r.t. approssimato
Un r.t. T(n) si assume essre 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)
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. approssimatoNotazione 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. approssimatoNotazione 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)
Notazione O-grande e r.t. approssimatoNotazione 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)
)0 ogniper (nota ,1 Siano0,0
0 kicaacn i
k
aii
i
Notazione O-grande e r.t. approssimatoNotazione 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)
)0 ogniper (nota ,1 Siano0,0
0 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
Notazione O-grande e r.t. approssimatoNotazione 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)
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
Notazione O-grande e r.t. approssimatoNotazione O-grande e r.t. approssimato
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
Notazione O-grande e r.t. approssimatoNotazione O-grande e r.t. approssimato
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
Notazione O-grande e r.t. approssimatoNotazione O-grande e r.t. approssimato
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
Notazione O-grande e r.t. approssimatoNotazione 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))
Notazione O-grande e r.t. approssimatoNotazione 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’ 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’’
Notazione O-grande e r.t. approssimatoNotazione 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’ 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)
Notazione O-grande e r.t. approssimatoNotazione 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. approssimatoNotazione 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 programmiRunning Time di programmi
Trova f(n) tale che T(n)=O(f(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)
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)
Running Time di programmiRunning 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))
Running Time di programmiRunning 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 programmiRunning 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 programmiRunning Time di programmi
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.
Running Time di programmiRunning Time di programmi
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)
Running Time di programmiRunning Time di programmi
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
Running Time di programmiRunning 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
Running Time di programmiRunning 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)=tT(n)=T(n-1)+c
Running Time di programmiRunning Time di programmi
Es. int fact(int n){ if (n<=1) return 1;
else return n*fact(n-1)}
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)
Running Time di programmiRunning Time di programmi
Es. int fact(int n){ if (n<=1) return 1;
else return n*fact(n-1)}
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)
Running Time di programmiRunning Time di programmi
Es. int fact(int n){ if (n<=1) return 1;
else return n*fact(n-1)}
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)
Running Time di programmiRunning Time di programmi
Es. int fact(int n){ if (n<=1) return 1;
else return n*fact(n-1)}
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)
Running Time di programmiRunning Time di programmi
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
Running Time di programmiRunning Time di programmi
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.
Running Time di programmiRunning Time di programmi
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)
Running Time di programmiRunning Time di programmi
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
Running Time di programmiRunning Time di programmi
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):
2. Determinare T(n) in termini di T(n-4):
3. Determinare T(n) in termini di T(n-6):
4. Determinare T(n) in termini di T(n-2i):
5. Determinare T(n):
Running Time di programmiRunning Time di programmi
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):
2. Determinare T(n) in termini di T(n-6):
3. Determinare T(n) in termini di T(n-2i):
4. Determinare T(n):
Running Time di programmiRunning Time di programmi
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)=2T(n-2)=4 T(n-4)
1. Determinare T(n) in termini di T(n-6):
2. Determinare T(n) in termini di T(n-2i):
3. Determinare T(n):
Running Time di programmiRunning Time di programmi
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)=4 T(n-4)= 8 T(n-6)
1. Determinare T(n) in termini di T(n-2i):
2. Determinare T(n):
Running Time di programmiRunning Time di programmi
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):
Running Time di programmiRunning Time di programmi
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=O(n)
Soluzioni Relazioni di ricorrenzaSoluzioni Relazioni di ricorrenza
1. T(1)=aT(n)= b+T(n-1), n>1 T(n)=O(n)
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)=…
Soluzioni Relazioni di ricorrenzaSoluzioni Relazioni di ricorrenza
1. T(1)=aT(n)= b+T(n-1), n>1 T(n)=O(n)
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)
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
Soluzioni Relazioni di ricorrenzaSoluzioni Relazioni di ricorrenza
4. T(1)=a T(n)=2T(n/2)+g(n)
angnT jn
n
j
j
)(2)( 2
log
0
2
Soluzioni Relazioni di ricorrenzaSoluzioni Relazioni di ricorrenza
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
Soluzioni Relazioni di ricorrenzaSoluzioni Relazioni di ricorrenza
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
Soluzioni Relazioni di ricorrenzaSoluzioni Relazioni di ricorrenza
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