Pages: 1 [2]   Go Down
Print
Author Topic: Equazione di ricorrenza  (Read 2476 times)
0 Members e 1 Utente non registrato stanno visualizzando questa discussione.
Pandemia000
Forumista Eroico
*****
Offline Offline

Gender: Male
Posts: 1.714


Γνῶθι Σεαυτόν


« Reply #15 on: 15-12-2010, 12:45:43 »

l'albero dovrebbe darti una buona approssimazione e poi provi la soluzione con il metodo di sosituzione. Credo che la soluzione sia esponenziale.
« Last Edit: 15-12-2010, 12:49:43 by Pandemia000 » Logged

La disumanità del computer sta nel fatto che, una volta programmato e messo in funzione, si comporta in maniera perfettamente onesta. (Isaac Asimov)
shiny
Forumista
***
Offline Offline

Posts: 810



WWW
« Reply #16 on: 15-12-2010, 14:15:02 »

T(n)\ =\ 2T(n-1)\ +\ 2(n-1)\ \leq\ 2T(n-1)\ +\ 2n
Sfruttando l'albero abbiamo che

0:\ n

1:\ 2(2n - 2)

2:\ 2(4n - 4)

3:\ 2(8n - 8)

4:\ 2(16n - 16)
...

T(n)\ \leq\ 2\ \sum_{i=0}^n {n2^i\ - 2^{i}}

T(n)\ \leq\ 2 (n-1)\ \sum_{i=0}^n\ {2^i}

T(n)\ \leq\ 2 (n-1)\ (2^{n+1} - 1)\ =\ O(n2^n)
« Last Edit: 15-12-2010, 14:20:00 by shiny » Logged
atrix0ne
Forumista
***
Offline Offline

Posts: 607


homo faber fortunae suae


« Reply #17 on: 15-12-2010, 14:19:36 »

ok ho capito!grazie shiny!
Logged

atrix0ne
Forumista
***
Offline Offline

Posts: 607


homo faber fortunae suae


« Reply #18 on: 15-12-2010, 14:28:15 »

quindi applico il telescoping giusto?
Logged

cock86
Forumista Eroico
*****
Offline Offline

Posts: 2.014


OM


« Reply #19 on: 15-12-2010, 14:48:48 »

pare abbia applicato l'albero di ricorrenza! viene così anche a me! però va provata con la sostituzione.
Logged

Un "buon informatico" trova una soluzione ad ogni tipo di problema. Un "ottimo informatico" trova la soluzione più efficiente ad ogni tipo di problema! Non stancatevi di migliorare la vostra soluzione!
Vincenzo Cutello
Administrator
Forumista
*****
Offline Offline

Gender: Male
Posts: 600


« Reply #20 on: 17-12-2010, 13:15:24 »

sostituisci S(n)=T(n)/2 e viene

S(n)=S(n-1) + n -1

questa si risolve con il telescoping e viene n^2 (ignora il -1) quindi T(n)=2*S(n) e resta di ordine n^2

non ne sono sicuro al 100% spererei in una conferma del prof. ma credo che si risolva cosi'
Ma se dividi per 2, ti viene T(n)/2, ma dall'altra parte ti rimane T(n-1)!
Attenzione a queste cose. Non sono dettagli.

Logged
Pages: 1 [2]   Go Up
Print
Jump to: