Pages: [1]   Go Down
Print
Author Topic: Aiuto su metodo di sostituzione pls!  (Read 1410 times)
0 Members e 1 Utente non registrato stanno visualizzando questa discussione.
KiLLing Spree
Matricola
*
Offline Offline

Posts: 81



« on: 05-02-2010, 13:07:44 »

Ho svolto l'albero di ricorsione della funzione T(n)=2T(n-1)+n che mi ha portato ad una complessità di 2^{n}, ho provato a verificare la soluzione col metodo di sostituzione ed ecco cosa viene fuori:

T(n)=2T(n-1)+n
dimostro che
T(n)<=c2^{n}

suppongo che sia vero per n-1, quindi
T(n-1)<=c2^{n-1}

Sostituisco e ottengo
T(n)<=2c2^{n-1}+n
T(n)<=c2^{n}+n
e quel "+n" fa fallire la dimostrazione...su diversi esercizi ho avuto questo problema, e sono certo della soluzione perchè la verifico anche col teorema Master...sapreste aiutarmi?
Logged

Ciao!
Vincenzo Cutello
Administrator
Forumista
*****
Offline Offline

Gender: Male
Posts: 603


« Reply #1 on: 08-02-2010, 18:34:51 »

Mi pare che così dovrebbe funzionare.

Assumiamo che T(1)=1
Quindi
T(2)=2T(1)+2=4 e
T(3)=2T(2)+3=11
T(4)=2T(3)+4=26
T(5)=2T(4)+5=57

Dimostriamo che T(n) \leq 3(2^n -n) per n > 3.

T(n)=2T(n-1)+n \leq 2(3\cdot2^{n-1}-3(n-1))+n=3\cdot2^n-6(n-1)+n=3\cdot2^n-5n+6
e dal momento che
5n-6\geq 3n perché si è supposto che n > 3
si ha
T(n) \leq 3\cdot2^n-5n+6 \leq 3(2^n -n)
Logged
vincenzo86
Forumista
***
Offline Offline

Gender: Male
Posts: 505



« Reply #2 on: 19-02-2012, 17:00:34 »

Potete spiegarmi questa ricorrenza? Grazie
Logged
shiny
Forumista
***
Offline Offline

Posts: 810



WWW
« Reply #3 on: 20-02-2012, 11:50:21 »

Mi sembra facile da capire la ricorrenza se hai studiato il metodo induttivo... sii più specifico sul cosa non ti e' chiaro (per esempio non mi e' chiaro il passaggio n). 
Logged
Pages: [1]   Go Up
Print
Jump to: