Forum Informatica Unict » LAUREA TRIENNALE (D.M. 270/04) » II anno » Algoritmi, 9 CFU (Moderator: Domenico Cantone) » Equazione di ricorrenza con metodo di sostituzione
Pages: [1]   Go Down
« precedente successivo »
Print
Author Topic: Equazione di ricorrenza con metodo di sostituzione  (Read 1593 times)
0 Members e 1 Utente non registrato stanno visualizzando questa discussione.
AnGeL88
Matricola
*
Offline Offline

Gender: Female
Posts: 96
« on: 02-11-2010, 12:44:57 »
Salve ragazzi, mi sto sbattendo la testa con questa ricorrenza:  testate

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

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

Come come la risolvereste? Grazie 
Logged
I computer sono incredibilmente veloci, accurati e stupidi. Gli uomini sono incredibilmente lenti, inaccurati e intelligenti. Insieme sono una potenza che supera l'immaginazione.
AnGeL88
Matricola
*
Offline Offline

Gender: Female
Posts: 96
« Reply #1 on: 02-11-2010, 17:28:32 »
raga ho risolto da sola  ok
Logged
I computer sono incredibilmente veloci, accurati e stupidi. Gli uomini sono incredibilmente lenti, inaccurati e intelligenti. Insieme sono una potenza che supera l'immaginazione.
invochevirtual
Matricola
*
Offline Offline

Posts: 46
« Reply #2 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?Huh? ti ringrazio
Logged
Crasher
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 417
« Reply #3 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 univ

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? 
Logged
Diventa ciò che sei nato per essere
shiny
Forumista
***
Offline Offline

Posts: 810



WWW
« Reply #4 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
« Last Edit: 09-11-2010, 16:20:33 by shiny » Logged
invochevirtual
Matricola
*
Offline Offline

Posts: 46
« Reply #5 on: 09-11-2010, 16:35:29 »
grazie mille!
Logged
esteta84
Apprendista Forumista
**
Offline Offline

Posts: 284
« Reply #6 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??
« Last Edit: 10-11-2010, 10:49:20 by esteta84 » Logged
esteta84
Apprendista Forumista
**
Offline Offline

Posts: 284
« Reply #7 on: 10-11-2010, 10:37:55 »
ah ok capito. Lo ricavi da \int \frac{1}{m} dm
Logged
shiny
Forumista
***
Offline Offline

Posts: 810



WWW
« Reply #8 on: 10-11-2010, 21:22:30 »
Quote from: 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??
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)
« Last Edit: 10-11-2010, 21:26:04 by shiny » Logged
Pages: [1]   Go Up
Print
« precedente successivo »
Jump to: