Pages: [1]   Go Down
Print
Author Topic: ricorrenza  (Read 4051 times)
0 Members e 1 Utente non registrato stanno visualizzando questa discussione.
bakks87
Apprendista Forumista
**
Offline Offline

Posts: 162


« on: 04-09-2009, 14:37:17 »

salve potreste darmi la soluzione con relativa spiegazione della ricorrenza

T(n)=T(n-1)+T(n-2)+n  l'esercizio dice di scegliere il bound più stretto, ovvero?

grazie.
Logged
K1a
Apprendista Forumista
**
Offline Offline

Posts: 210



« Reply #1 on: 04-09-2009, 16:59:11 »

ciao, ricorrenza interessante.. non ho la soluzione ma ho tentato di farla con l'albero di ricorsione ..
al primo livello ho una somma di n al secondo di n-3 al terzo di n-12 al quarto di n-40 e così via.. (se i calcoli sono giusti)
Arrivata a questo punto però mi sono bloccata..
speriamo che qulcuno ci dia una mano Smiley
Logged
James
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 209



« Reply #2 on: 04-09-2009, 18:10:53 »

Primo livello = n
Secondo livello = 2n-3
Terzo livello = 4n-12
Quarto livello = 8n-36
e così via...
« Last Edit: 04-09-2009, 18:15:57 by James » Logged

Whatever people say i am, that's what i'm not
shiny
Forumista
***
Offline Offline

Posts: 810



WWW
« Reply #3 on: 08-09-2009, 12:52:52 »

è una esponenziale ovvero Theta(2^n)...

io non l'ho risolta però se la guardate bene è molto simile a qsta T(n)= T(n-1)+T(n-2)+1 che non è altro che la ricorrenza di ricerca dei numeri di fibonacci che come tutti sanno ha una complessità esponenziale...

se ad ogni passaggio dovete aggiungere un fattore n anziché una costante converrete che anche questa è sicuramente esponenziale.

Cmq visto che ho un po di tempo vedo di risolverla  univ
« Last Edit: 14-12-2010, 11:07:16 by shiny » Logged
shiny
Forumista
***
Offline Offline

Posts: 810



WWW
« Reply #4 on: 08-09-2009, 15:42:22 »

eccovi la soluzione...

come detto da james l'albero di ricorsione si sviluppa secondo qsti passi:
0: n
1: 2n - 3
2: 4n - 12
3: 8n - 36
4: 16n - 96
...

da cui la sommatoria

\sum_{i=0}^n {n2^i\ - 3i 2^{i-1}}

spezzando le sommatorie e portando i termini costanti fuori otteniamo le 2 seguenti sommatorie

n\sum_{i=0}^n{2^i}\ - 3\sum_{i=0}^n{i 2^{i-1}}

La 1 sommatoria è la serie geometrica di ragione 2 il cui risultato è

n2^{n+1}\ -\ n

mentre la seconda, essendo i2(i-1) una funzione monotona crescente, la si può approssimare con gli integrali con il seguente risultato

3\ \left( 2^n\ \left(\frac{n+1}{\ln 2}\ -\ \frac{1}{\ln^2 2}\right)\ -\ \frac{1}{\ln 2}\ +\ \frac{1}{\ln^2 2}\right)


Se sottraiamo al primo risultato il secondo possiamo vedere che il termine di ordine maggiore è
Quote
n2(n+1)
e quindi la nostra equazione di ricorrenza ha complessità O(n2(n+1))
« Last Edit: 21-05-2011, 13:28:40 by shiny » Logged
Fra83
Apprendista Forumista
**
Offline Offline

Posts: 213



« Reply #5 on: 22-03-2011, 12:29:46 »

Code:
0: n
1: 2n - 3
2: 4n - 12
3: 8n - 36
4: 16n - 96

Scusa potresti cortesemente dirmi perchè al livello 3 il costo è 8n-36? A me viene 8n-48...

                                                               livello 0------------------  n
                                                               livello 1------------ (n-1)+(n-2)
                                                               livello 2-----------(n-2)+(n-2)+(n-4)+(n-4)
                                                               livello 3-------(n-4)+(n-4)+(n-4)+(n-4)+(n-8)+(n-8)+(n-8)+(n-8)

Dove sbaglio?
Logged
shiny
Forumista
***
Offline Offline

Posts: 810



WWW
« Reply #6 on: 22-03-2011, 18:33:33 »

Code:
0: n
1: 2n - 3
2: 4n - 12
3: 8n - 36
4: 16n - 96

Scusa potresti cortesemente dirmi perchè al livello 3 il costo è 8n-36? A me viene 8n-48...

                                                               livello 0------------------  n
                                                               livello 1------------ (n-1)+(n-2)
                                                               livello 2-----------(n-2)+(n-2)+(n-4)+(n-4)
                                                               livello 3-------(n-4)+(n-4)+(n-4)+(n-4)+(n-8)+(n-8)+(n-8)+(n-8)

Dove sbaglio?


Dal livello 2 in poi e' tutto sbagliato 
Logged
Fra83
Apprendista Forumista
**
Offline Offline

Posts: 213



« Reply #7 on: 22-03-2011, 21:23:55 »

Ti sarei grato se magari scrivessi l'albero corretto....Grazie mille
Logged
shiny
Forumista
***
Offline Offline

Posts: 810



WWW
« Reply #8 on: 23-03-2011, 01:22:40 »

Eccolo
                                                               livello 0------------------ n
                                                               livello 1------------ (n-1)+(n-2)
                                                               livello 2-------- (n-2)+(n-3)+(n-3)+(n-4)
                                                               livello 3---- (n-3)+(n-4)+(n-4)+(n-5)+(n-4)+(n-5)+(n-5)+(n-6)
« Last Edit: 24-03-2011, 01:24:30 by shiny » Logged
Fra83
Apprendista Forumista
**
Offline Offline

Posts: 213



« Reply #9 on: 23-03-2011, 09:40:36 »

Grazie ancora, gentilissimo!
Logged
Fra83
Apprendista Forumista
**
Offline Offline

Posts: 213



« Reply #10 on: 21-05-2011, 09:55:30 »

Code:
come detto da james l'albero di ricorsione si sviluppa secondo qsti passi:
0: n
1: 2n - 3
2: 4n - 12
3: 8n - 36
4: 16n - 96
...

da cui la sommatoria da 1 ad n di



Come la ricavi questa sommatoria?
Logged
shiny
Forumista
***
Offline Offline

Posts: 810



WWW
« Reply #11 on: 21-05-2011, 13:31:00 »

Code:
come detto da james l'albero di ricorsione si sviluppa secondo qsti passi:
0: n
1: 2n - 3
2: 4n - 12
3: 8n - 36
4: 16n - 96
...

da cui la sommatoria da 1 ad n di



Come la ricavi questa sommatoria?
sommando i termini che ho scritto prima ^^
Logged
Pages: [1]   Go Up
Print
Jump to: