Pages: [1]   Go Down
Print
Author Topic: Equazioni di ricorrenza, metodo risolutivo?  (Read 875 times)
0 Members e 1 Utente non registrato stanno visualizzando questa discussione.
jos90
Apprendista Forumista
**
Offline Offline

Posts: 171



« on: 14-12-2014, 12:39:57 »

Ciao a tutti! Nella seguente equazione di ricorrenza, quale metodo risolutivo utilizzereste voi?

T(n) = 3T(n/2) + n^2

Io sono ricorso al primo caso del Teorema Master, dove f(n) = n^2 e f(n) = O( n^(log_2 3-E) ) , ipotesi vera per  E=1 > 0 ;

Quindi T(n) = theta ( n^(log_2 3) )

Il procedimento è corretto? Voi quale avreste utilizzato e che soluzione avreste raggiunto?
Grazie per l'attenzione  ciao

P.S.: Essendo lo script di Latex non funzionante, mi sono dovuto arrangiare come ho potuto, appuntando come  _2  la base 2 del logaritmo e come  ^2  l'esponente!

Logged

Perchè non pensi di non capire, quando capisci di non pensare?
Domenico Cantone
Moderator
Apprendista Forumista
*****
Offline Offline

Gender: Male
Posts: 345



« Reply #1 on: 22-12-2014, 10:10:31 »

Ciao a tutti! Nella seguente equazione di ricorrenza, quale metodo risolutivo utilizzereste voi?

T(n) = 3T(n/2) + n^2

Io sono ricorso al primo caso del Teorema Master, dove f(n) = n^2 e f(n) = O( n^(log_2 3-E) ) , ipotesi vera per  E=1 > 0 ;

Quindi T(n) = theta ( n^(log_2 3) )

Il procedimento è corretto? Voi quale avreste utilizzato e che soluzione avreste raggiunto?
Grazie per l'attenzione  ciao

P.S.: Essendo lo script di Latex non funzionante, mi sono dovuto arrangiare come ho potuto, appuntando come  _2  la base 2 del logaritmo e come  ^2  l'esponente!



Si osservi che log_2 3 < 2. Dunque è errato scrivere f(n) = O( n^(log_2 3-E) ), per qualunque E > 0.
Piuttosto vale f(n) = Omega( n^(log_2 3+E) ), per ogni 0< E < 2 - log_2 3.
Inoltre vale anche 3(n/2)^2 <= c n^2, per ogni 3/4 < c < 1 (condizione di regolarità).
Pertanto ricorrono le ipotesi del terzo caso del Teorema Master e di conseguenza la soluzione all'equazione di ricorrenza proposta è   T(n) = Theta( n^2 ).
Logged
Pages: [1]   Go Up
Print
Jump to: