verde_acqua
27-10-2005, 16:49
Ciao ho un equazione di ricorrenza che mi sta dando dei problemi,
è questa:
T(n)<= 2T(inf(n/4))+T(inf(n/5))+cn
dove inf sta per parte intera inferiore.
ora non è possibile applicare il teorema fondamentale delle ricorrenze nè
l albero della ricorrenza.
Per applicare il metodo della sostituzione dovrei intuire la soluzione....per poi dimostrarla per induzione....
Per iterazione ho dei problemi perchè ciò che conduce al passo base T(1) = costante, la prima chiamata ricorsiva 2T(inf(n/4)) non porta al passo base la seconda.
Sto sbagliando qualcosa? Cos'altro posso tentare?
Grazie in anticipo per qualsiasi consiglio.
è questa:
T(n)<= 2T(inf(n/4))+T(inf(n/5))+cn
dove inf sta per parte intera inferiore.
ora non è possibile applicare il teorema fondamentale delle ricorrenze nè
l albero della ricorrenza.
Per applicare il metodo della sostituzione dovrei intuire la soluzione....per poi dimostrarla per induzione....
Per iterazione ho dei problemi perchè ciò che conduce al passo base T(1) = costante, la prima chiamata ricorsiva 2T(inf(n/4)) non porta al passo base la seconda.
Sto sbagliando qualcosa? Cos'altro posso tentare?
Grazie in anticipo per qualsiasi consiglio.