The external

User info:

Registered: Feb 2007
Posts: 6 (0.00 al dì)
Location:
Corso:
Anno:
Time Online: 0:43:48 [...]
Status: Offline

Post actions:

Qualcuno saprebbe dirmi come risolvere questa ricorrenza?

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

Più che altro che teorema si usa?

ideafix

.grande:maestro.

User info:

Registered: Oct 2004
Posts: 953 (0.13 al dì)
Location: Melegnano (MI)
Corso: Informatica
Anno: Dottore!
Time Online: 27 Days, 3:05:20 [...]
Status: Offline

Post actions:

Io userei l'albero di ricorrenza.

Al limite poi per provare quello che l'albero di ricorrenza suggerisce, userei il metodo di sostituzione

The external

User info:

Registered: Feb 2007
Posts: 6 (0.00 al dì)
Location:
Corso:
Anno:
Time Online: 0:43:48 [...]
Status: Offline

Post actions:

Però i livelli sommati hanno, ad esempio il secondo, 11/12n, mentre il primo n e quindi non so che ipotesi fare sull'albero di ricorsione. Il terzo è più o meno nella stessa proporzione 121/144

poi_1969

User info:

Registered: Aug 2005
Posts: 507 (0.07 al dì)
Location: milano
Corso: informatica
Anno: 2°
Time Online: 10 Days, 22:40:57 [...]
Status: Offline

Post actions:

Non puoi usare il teorema dell'esperto, perche mancano le condizioni.
Devi usare l'albero di ricorsione per fare un'ipotesi che poi devi dimostrare con il metodo della sostituzione.
Dei due rami devi vedere quello che si esaurisce per ultimo e calcolarne l'altezza.
Dovresti provare con il metodo di sostituzione (n log in base 3 di n)
Ma devi stabilire quale sono le condizioni iniziali: cioè qual'è il caso base.

ciao

ideafix

.grande:maestro.

User info:

Registered: Oct 2004
Posts: 953 (0.13 al dì)
Location: Melegnano (MI)
Corso: Informatica
Anno: Dottore!
Time Online: 27 Days, 3:05:20 [...]
Status: Offline

Post actions:

se noti 1 11/12 121/144

assomiglia alla cosi detta serie geometrica .




(11/12)^0 + (11/12)^1 + (11/12)^2....

Last edited by ideafix on 02-03-2007 at 10:30

The external

User info:

Registered: Feb 2007
Posts: 6 (0.00 al dì)
Location:
Corso:
Anno:
Time Online: 0:43:48 [...]
Status: Offline

Post actions:

Si effettivamente non differisce molto dagli es che ho fatto finora... forse non avevo capito una piccola sfumatura sull'albero di ricorsione. Scusate, stress da studio. Ora vedo se riesco a tirarne fuori qualcosa.

antares85

User info:

Registered: Oct 2005
Posts: 197 (0.03 al dì)
Location: milano
Corso: informatica
Anno: 2
Time Online: 1 Day, 6:16:58 [...]
Status: Offline

Post actions:

scusate ma all'orale torelli potrebbe chiedere di risolvere un problema del genere?

The external

User info:

Registered: Feb 2007
Posts: 6 (0.00 al dì)
Location:
Corso:
Anno:
Time Online: 0:43:48 [...]
Status: Offline

Post actions:

Dovrebbe essere in teta(n)