Risolvere le equazioni di ricorrenza
Salve a tutti,
fra poco tempo avrò l'esame di algoritmi e strutture dati, e non ho capito bene come si risolvono le equazioni di ricorrenza:
$T(n) = aT(n/b) + cn$
Allora quelle di questa forma so che si possono risolvere applicando la sostituzione $b^k = n$, poi moltiplico ambo i membri per $1/a^k$, e poi applico un'altra sostituzione tipo $G(k) = T(b^k)/a^k$. Ora, fatto tutto questo posso risolvere l'equazione mediante telescoping...
Il problema è che a volte mi capita di trovare equazioni tipo:
$T(n) = T(n/a) + T(n/b) + cn$
quindi una come questa non so svilupparla:
$T(n) = T(n/3) + T(2n/3) + cn$
$T(n) = T(n/9) + T(2n/3) + cn$
Qualcuno mi può aiutare?
fra poco tempo avrò l'esame di algoritmi e strutture dati, e non ho capito bene come si risolvono le equazioni di ricorrenza:
$T(n) = aT(n/b) + cn$
Allora quelle di questa forma so che si possono risolvere applicando la sostituzione $b^k = n$, poi moltiplico ambo i membri per $1/a^k$, e poi applico un'altra sostituzione tipo $G(k) = T(b^k)/a^k$. Ora, fatto tutto questo posso risolvere l'equazione mediante telescoping...
Il problema è che a volte mi capita di trovare equazioni tipo:
$T(n) = T(n/a) + T(n/b) + cn$
quindi una come questa non so svilupparla:
$T(n) = T(n/3) + T(2n/3) + cn$
$T(n) = T(n/9) + T(2n/3) + cn$
Qualcuno mi può aiutare?
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo