Pages: [1]   Go Down
Print
Author Topic: Eq. di ricorrenza T(n)=3T(n/2)+n  (Read 1314 times)
0 Members e 1 Utente non registrato stanno visualizzando questa discussione.
KiLLing Spree
Matricola
*
Offline Offline

Posts: 81



« 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?
« Last Edit: 02-02-2010, 11:30:53 by KiLLing Spree » Logged

Ciao!
cock86
Forumista Eroico
*****
Offline Offline

Posts: 2.014


OM


« Reply #1 on: 02-02-2010, 13:55:43 »

beh con il terzo caso di maser la soluzione è giusta!
Logged

Un "buon informatico" trova una soluzione ad ogni tipo di problema. Un "ottimo informatico" trova la soluzione più efficiente ad ogni tipo di problema! Non stancatevi di migliorare la vostra soluzione!
KiLLing Spree
Matricola
*
Offline Offline

Posts: 81



« Reply #2 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?
Logged

Ciao!
Psycho
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 497



« Reply #3 on: 02-02-2010, 17:00:13 »

si, credo sia il primo caso del teorema master Wink
Logged

Segnate le date, cancellate gli altri impegni, chiudete i libri e i quaderni e per un attimo accorgetevi che la vita non è piatta ma può essere... 3d!
cock86
Forumista Eroico
*****
Offline Offline

Posts: 2.014


OM


« Reply #4 on: 02-02-2010, 17:33:11 »

si scusami proprio il primo!!
Logged

Un "buon informatico" trova una soluzione ad ogni tipo di problema. Un "ottimo informatico" trova la soluzione più efficiente ad ogni tipo di problema! Non stancatevi di migliorare la vostra soluzione!
Pages: [1]   Go Up
Print
Jump to: