Forum Informatica Unict

LAUREA TRIENNALE (D.M. 270/04) => Algoritmi, 9 CFU => Topic started by: KiLLing Spree on 02-02-2010, 11:28:47



Title: Eq. di ricorrenza T(n)=3T(n/2)+n
Post by: KiLLing Spree on 02-02-2010, 11:28:47
Sto provando a risolvere l'equazione di ricorrenza T(n)=3T(n/2)+n tramite un albero di ricorsione.
La soluzione a cui sono arrivato è n^{\lg_2 3} ma quando provo a verificarla col metodo di sostituzione sembra non essere corretta..E' sbagliata la soluzione o il mio modo di verificarla?


Title: Re:Eq. di ricorrenza T(n)=3T(n/2)+n
Post by: cock86 on 02-02-2010, 13:55:43
beh con il terzo caso di maser la soluzione è giusta!


Title: Re:Eq. di ricorrenza T(n)=3T(n/2)+n
Post by: KiLLing Spree on 02-02-2010, 15:06:28
Forse mi sbaglio, ma credo che tu ti riferissi al primo caso del teorema master, cioè se f(n)=O(n^{log_b a - e}) per e>0 allora T(n)=teta(n^{log_b a})...giusto?


Title: Re:Eq. di ricorrenza T(n)=3T(n/2)+n
Post by: Psycho on 02-02-2010, 17:00:13
si, credo sia il primo caso del teorema master ;)


Title: Re:Eq. di ricorrenza T(n)=3T(n/2)+n
Post by: cock86 on 02-02-2010, 17:33:11
si scusami proprio il primo!! .wink .arrossisco