Forum Informatica Unict

LAUREA TRIENNALE (D.M. 270/04) => Algoritmi, 9 CFU => Topic started by: AnGeL88 on 02-11-2010, 12:44:57



Title: Equazione di ricorrenza con metodo di sostituzione
Post by: AnGeL88 on 02-11-2010, 12:44:57
Salve ragazzi, mi sto sbattendo la testa con questa ricorrenza:  :-)|

T(n) = 5*T(n/5)+n/lgn

il prof da come risultato T(n) = O(nlglgn)

Come come la risolvereste? Grazie  .smile


Title: Re:Equazione di ricorrenza con metodo di sostituzione
Post by: AnGeL88 on 02-11-2010, 17:28:32
raga ho risolto da sola  :-OK


Title: Re:Equazione di ricorrenza con metodo di sostituzione
Post by: invochevirtual on 08-11-2010, 16:53:28
io sono arrivato a questo risultato
loglogn

praticamente mi manca la n iniziale

potresti postare il procedimento di come l'hai svolta???? ti ringrazio


Title: Re:Equazione di ricorrenza con metodo di sostituzione
Post by: Crasher on 09-11-2010, 12:12:45
mmh... voglio capirci qualcosa anch'io...

Inizio a postare la mia soluzione così abbiamo un punto di partenza |-O

T(n) = 5 T(\frac{n}{5})+ \frac{n}{lg n}

T(2^m) = 5 T(\frac{2^m}{5})+ \frac{2^m}{m}

\frac{T(2^m)}{2^m} = \frac{5 T(\frac{2^m}{5})}{2^m} + \frac{1}{m}

S(m) = \frac{T(2^m)}{2^m}

S(m) = 5 S(\frac{m}{5}) + \frac{1}{m}

Se imposto \epsilon = 2 ci troviamo nel 1° caso del Master:

S(m) = \theta(m^lg_5 ^5) = \theta(m)

Quindi:
T(n) = 2^m \theta(m) = \theta(n logn)

Possiamo confrontare le nostre soluzioni?  .smile


Title: Re:Equazione di ricorrenza con metodo di sostituzione
Post by: shiny on 09-11-2010, 16:15:32
Eccovi lo svolgimento col metodo di sostituzione

T(n) = 5 T(\frac{n}{5})+ \frac{n}{\log n}

T(5^m) = 5 T(\frac{5^m}{5})+ \frac{5^m}{m}

\frac{T(5^m)}{5^m} = \frac{T(5^{m-1})}{5^{m-1}} + \frac{1}{m}

S(m) = \frac{T(5^m)}{5^m}

S(m) = S(m-1) + \frac{1}{m}

S(m) = \log m

T(5^m) = 5^m \log m

T(n) = n \log\log n


Title: Re:Equazione di ricorrenza con metodo di sostituzione
Post by: invochevirtual on 09-11-2010, 16:35:29
grazie mille!


Title: Re:Equazione di ricorrenza con metodo di sostituzione
Post by: esteta84 on 10-11-2010, 10:18:00
Scusa shiny, dopo questo passaggio  S(m) = S(m-1) + \frac{1}{m}  cos'hai fatto per capire che
S(m) = \log m.

Io ho proseguito così: S(m) - S(m-1) = \frac{1}{m}
S(m) = \sum_{i=0}^m\frac{1}{i}

che è una serie armonica semplice quindi diverge a +\infty

e poi cosa bisogna fare??


Title: Re:Equazione di ricorrenza con metodo di sostituzione
Post by: esteta84 on 10-11-2010, 10:37:55
ah ok capito. Lo ricavi da \int \frac{1}{m} dm


Title: Re:Equazione di ricorrenza con metodo di sostituzione
Post by: shiny on 10-11-2010, 21:22:30
Scusa shiny, dopo questo passaggio  S(m) = S(m-1) + \frac{1}{m}  cos'hai fatto per capire che
S(m) = \log m.

Io ho proseguito così: S(m) - S(m-1) = \frac{1}{m}
S(m) = \sum_{i=0}^m\frac{1}{i}

che è una serie armonica semplice quindi diverge a +\infty

e poi cosa bisogna fare??
guarda che la serie armonica diverge solo quando abbiamo un numero infinito di termini... qui i termini vanno da 1 a m e non da 0 a m perche' per i = 0 avremmo \frac{1}{0} che non ha senso... per ricavarla la maggioro con un'altra sommatoria
\sum_{i=1}^m\ \frac{1}{i}\ \leq\ \sum_{i=0}^{\lfloor\log m \rfloor} \sum_{j=0}^{2^i -1}\ \frac{1}{2^i}\ =\ \sum_{i=0}^{\lfloor\log m \rfloor}\ 1\ \leq\ \log m\ +\ 1\ =\ \theta(\log m)