.dsy:it. (http://www.dsy.it/forum/)
- Algoritmi e strutture dati (http://www.dsy.it/forum/forumdisplay.php?forumid=207)
-- [HELP] Ricorrenza (http://www.dsy.it/forum/showthread.php?threadid=29779)

Ricorrenza

Qualcuno saprebbe dirmi come risolvere questa ricorrenza?

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

Più che altro che teorema si usa?

Io userei l'albero di ricorrenza.

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

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

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

se noti 1 11/12 121/144

assomiglia alla cosi detta serie geometrica .




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

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.

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

Dovrebbe essere in teta(n)