[HELP] Ricorrenza
Clicca QUI per vedere il messaggio nel forum |
| The external |
Qualcuno saprebbe dirmi come risolvere questa ricorrenza?
T(n) = 2T(n/3) + T(n/4) + n
Più che altro che teorema si usa? |
| ideafix |
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 |
| 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 |
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 |
se noti 1 11/12 121/144
assomiglia alla cosi detta serie geometrica .
;)
(11/12)^0 + (11/12)^1 + (11/12)^2.... |
| The external |
| 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. :-o Ora vedo se riesco a tirarne fuori qualcosa. |
| antares85 |
| scusate ma all'orale torelli potrebbe chiedere di risolvere un problema del genere? |
| The external |
| Dovrebbe essere in teta(n) |
|
|
|
