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