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

Gender: Male
Posts: 422


« on: 18-10-2010, 07:19:59 »


T(n)= radice(n) T(rad(n)) +n

io ci ho provato cosi..
n=2^m  m=log n
T(2^m) = S(m) = 2^(2/m)  S(m/2) + 2^m      pongo m=2^k  k=log m

S(2^k)= 4^(k-1) S(2^(k-1)) + 4^k                  pongo  R(k)=S(2^k)

R(k)=  4^(k-1) R(k-1) + 4^k                     
........ adesso dovrei dividere per "qualcosa" in modo che viene al numeratore R(k-1) e al denominatore 4^(k-1) in modo da poter poi fare la sostituzione Q(k)= R(k)/4^k ed ottenere  Q(k)=Q(k-1) + f(k) ma non so cosa :S
Logged

Codice etico e di pratica professionale dello sviluppo software:
..
..
7. Colleghi. Gli sviluppatori software devono essere leali e di supporto nei confronti dei loro colleghi.
...
Yngwie
Forumista
***
Offline Offline

Gender: Male
Posts: 849


Maestro! mi dia un MI in chiave di SOL!


« Reply #1 on: 18-10-2010, 16:04:54 »

Ma il latex che ci sta a fare in questo forum? ti consiglio di riscrivere il tutto sennò nessuno ti ... calcola  I
Logged

shiny
Forumista
***
Offline Offline

Posts: 810



WWW
« Reply #2 on: 19-10-2010, 00:27:01 »

L' equazione dovrebbe essere questa giusto?
T(n)\ =\ \sqrt{n}\ T(\sqrt{n})\ +\ n

Io l'ho risolta cosi':

\frac{T(n)}{\sqrt{n}}\ =\ T(\sqrt{n})\ +\ \sqrt{n}

B(n)\ =\ B(\sqrt{n})\ +\ \sqrt{n}

B(2^k)\ =\ B(2^{\frac{k}{2}})\ +\ \sqrt{2^k}

S(k)\ =\ S(\frac{k}{2})\ +\ \sqrt{2^k}

Per il 3 caso del teorema master
S(k)\ =\ \Theta(\sqrt{2^k})
B(n)\ =\ \Theta(\sqrt{n})
T(n)\ =\ \Theta(\sqrt{n}\ \sqrt{n})\ = \ \Theta(n)

Credo che cosi' dovrebbe andare anche se non ne sono sicuro 
« Last Edit: 19-10-2010, 00:28:53 by shiny » Logged
alex180788
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 422


« Reply #3 on: 19-10-2010, 10:05:49 »

Grazie shiny l'ho risolto da solo:

T(n)=\sqrt{n}T(\sqrt{n}) + n \qquad pongo\quad n=2^m m=\log n\\T{2^m}=2^{m/2}T(2^{m/2}) + 2^m\\S(m)=T(2^m)\\S(m)=2^{m/2}S(m/2)+2/m \qquad \qquad pongo\quad m=2^k k=\log m\\S(2^k)=2^{2^{k-1}}S(2^{k-1})+2^2^k\\R(k)=S(2^k)\\R(k)=2^{2^{k-1}}R(k-1)+2^2^k

divido per 2^2^k
poiché...

{2^{2^{k-1}}}/{2^k}= \\ = 2^2^{k-1} \quad \times \quad 2^{-2^k} = \\ = 2^{2^{k-1}-2^k}= \\ = 2^{2^{k-1} \quad \times \quad (1-2)} = \\ = 2^{-2^{k-1}} = \\ = 1 / 4^{k-1}


Q(k)=R(k)/4^k = R(k-1)/4^{k-1} + 2^{2k}/4^k
quindi
Q(k)=Q(k-1) + 1

che si risolve con telescopic... facendo tutte le sostituzioni viene T(n)=O(logn log log n) se la base del log è 4 e T(n)=O( log^2 log log n) se la base è 2



Ma il latex che ci sta a fare in questo forum? ti consiglio di riscrivere il tutto sennò nessuno ti ... calcola  I

hai ragione è davvero incomprensibile!..... cambiare marca di yogurt la mattina no?!
Logged

Codice etico e di pratica professionale dello sviluppo software:
..
..
7. Colleghi. Gli sviluppatori software devono essere leali e di supporto nei confronti dei loro colleghi.
...
shiny
Forumista
***
Offline Offline

Posts: 810



WWW
« Reply #4 on: 19-10-2010, 15:08:25 »


divido per 2^2^k

...

Q(k)=R(k)/4^k = R(k-1)/4^{k-1} + 2^{2k}/4^k

Io non vorrei buttarti giu' ma vedi che  2^{2^k}\ \neq\ 4^k
quindi la tua ricorrenza sarebbe

Q(k)=R(k)/2^{2^k} = R(k-1)/4^{k-1} + 2^{2^k}/2^{2^k}

e non

Q(k)=R(k)/4^k = R(k-1)/4^{k-1} + 2^{2k}/4^k

inoltre non ho capito da dove spunta  2^{2k} se fino alla R(k) era  2^{2^k} che, come gia' detto, sono 2 cose molto ma molto diverse...
Logged
alex180788
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 422


« Reply #5 on: 19-10-2010, 17:42:06 »

Io non vorrei buttarti giu' ma vedi che  2^{2^k}\ \neq\ 4^k
quindi la tua ricorrenza sarebbe

Q(k)=R(k)/2^{2^k} = R(k-1)/4^{k-1} + 2^{2^k}/2^{2^k}

....ops! quindi viene Q(k)=Q(k-1) + 1  ??

Quote
inoltre non ho capito da dove spunta  2^{2k} se fino alla R(k) era  2^{2^k} che, come gia' detto, sono 2 cose molto ma molto diverse...

si hai ragione ho sbagliato a scrivere (in latex)  quel   2^{2k}  era  2^{2^k}
Logged

Codice etico e di pratica professionale dello sviluppo software:
..
..
7. Colleghi. Gli sviluppatori software devono essere leali e di supporto nei confronti dei loro colleghi.
...
shiny
Forumista
***
Offline Offline

Posts: 810



WWW
« Reply #6 on: 19-10-2010, 20:16:56 »

Allora spero che cosi' ti sia chiaro (e spero di non dire una cavolata visto che ho dato questa materia anni fa ^^).
Quando hai

R(k)/2^{2^k} = R(k-1)/4^{k-1} + 2^{2^k}/2^{2^k}

poi non puoi dire che per Q(k)=R(k)/2^{2^k}
valga Q(k)=Q(k-1)+1 in quanto Q(k-1)\ =\ R(k-1)/2^{2^{k-1}}\ \neq \ R(k-1)/4^{k-1}
e R(k-1)/4^{k-1} era quello che avevi te prima quindi devi trovare un altro modo per risolverla. (ecco perche' io quando l'ho risolta ho usato il teorema master) 
« Last Edit: 19-10-2010, 20:19:40 by shiny » Logged
shiny
Forumista
***
Offline Offline

Posts: 810



WWW
« Reply #7 on: 19-10-2010, 20:24:17 »

io avevo assunto che questo sotto fosse giusto
{2^{2^{k-1}}}/{2^k}= \\ = 2^2^{k-1} \quad \times \quad 2^{-2^k} = \\ = 2^{2^{k-1}-2^k}= \\ = 2^{2^{k-1} \quad \times \quad (1-2)} = \\ = 2^{-2^{k-1}} = \\ = 1 / 4^{k-1}
ma anche qui errore ci fu... alla fine risulta cosi' (e tutto torna)
 = 1 / 2^{2^{k-1}} 
Logged
alex180788
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 422


« Reply #8 on: 20-10-2010, 06:37:17 »

si è capito che con latex non sono pratico eh?! Cheesy
comunque grazie Wink
Logged

Codice etico e di pratica professionale dello sviluppo software:
..
..
7. Colleghi. Gli sviluppatori software devono essere leali e di supporto nei confronti dei loro colleghi.
...
Vincenzo Cutello
Administrator
Forumista
*****
Offline Offline

Gender: Male
Posts: 600


« Reply #9 on: 22-10-2010, 14:15:40 »

Ho letto alcune risposte e mi sono rifiutato di continuare 
Allora, l' equazione è
T(n)\ =\ \sqrt{n}\ T(\sqrt{n})\ +\ n

Poniamo
n=2^m e quindi  m=\log n

Quindi,
T(2^m)\ =\ 2^{\frac{m}{2}}T(2^{\frac{m}{2}})\ +\ 2^m

Dividendo per 2^m, si ottiene

\frac{T(2^m)}{2^m}\ =\ \frac{T(2^{\frac{m}{2}})}{2^{\frac{m}{2}}} + 1

Ponendo,  S(m)\ =\ \frac{T(2^m)}{2^m}, si ha
S(m)\ =\ S(m/2) + 1

Per il secondo caso del teorema master
S(m)\ =\ \Theta(\log m)
Quindi ?
Logged
alex180788
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 422


« Reply #10 on: 22-10-2010, 14:33:27 »

\Theta{(n \log \log n)}  
Logged

Codice etico e di pratica professionale dello sviluppo software:
..
..
7. Colleghi. Gli sviluppatori software devono essere leali e di supporto nei confronti dei loro colleghi.
...
Pages: [1]   Go Up
Print
Jump to: