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

Gender: Male
Posts: 2.679


La musica è la forma d'arte suprema.


« on: 24-11-2010, 19:11:11 »

T(n)=2T(n/2)+n/logn

Stavo provando a risolverla per sostituzione...ma mi blocco...

n=2^m

T(2^m)=2T(2^m/2)+2^m/logn
S(m)=T(2^m)
S(m)=2(S(m)/2)+2^m/m

Qui non sparei continuare...
Logged

"Utilizzare sempre de l'Hôpital.....è come andare a caccia di farfalle con un bazooka".
shiny
Forumista
***
Offline Offline

Posts: 810



WWW
« Reply #1 on: 25-11-2010, 14:37:05 »

T(n)=2T(n/2)+n/logn

Stavo provando a risolverla per sostituzione...ma mi blocco...

n=2^m

T(2^m)=2T(2^m/2)+2^m/logn
S(m)=T(2^m)
S(m)=2(S(m)/2)+2^m/m

Qui non sparei continuare...
giusto cosi' per dire ma esiste una regole delle potenze che recita: la divisione di potenze aventi la stessa base risulta in una potenza avente per base la stessa base e come esponente la differenza degli esponenti... quindi

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

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

\frac{S(m)}{2^m}=\frac{S(m-1)}{2^{m-1}}+\frac{1}{m}
« Last Edit: 25-11-2010, 14:40:07 by shiny » Logged
Daréios89
Forumista Eroico
*****
Offline Offline

Gender: Male
Posts: 2.679


La musica è la forma d'arte suprema.


« Reply #2 on: 25-11-2010, 15:11:11 »

Scusa ma non capisco qui cosa fai:

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

Dividi per 2^m giusto?

Perchè abbiamo \frac{S(m-1)}{2^{m-1}}?

Dividendo non dovremmo avere: \frac{S(m-1)}{2^m} ?

avrei \frac{2}{2^m}

2^{1-m}

Per caso fai l'inverso e ottieni \frac{1}{2^{m-1}} ?
Logged

"Utilizzare sempre de l'Hôpital.....è come andare a caccia di farfalle con un bazooka".
Crasher
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 417



« Reply #3 on: 25-11-2010, 19:05:33 »

ti 6 risposto da solo 
Logged

Diventa ciò che sei nato per essere
Daréios89
Forumista Eroico
*****
Offline Offline

Gender: Male
Posts: 2.679


La musica è la forma d'arte suprema.


« Reply #4 on: 25-11-2010, 21:47:45 »

ti 6 risposto da solo 

AH bene..

E arrivato a questo punto......non mi viene altro che usare il teorema Master...sareste d'accordo?
Logged

"Utilizzare sempre de l'Hôpital.....è come andare a caccia di farfalle con un bazooka".
shiny
Forumista
***
Offline Offline

Posts: 810



WWW
« Reply #5 on: 26-11-2010, 22:28:53 »

io continuerei cosi'

\frac{S(m)}{2^m}=R(m)

R(m)=R(m-1)+\frac{1}{m}

Da cui otteniamo la seguente serie

R(m)\ =\ \sum_{i=1}^m\ \frac{1}{i}\ =\ O(\log m)

T(n)\ =\ O(n \log\log n)
Logged
Daréios89
Forumista Eroico
*****
Offline Offline

Gender: Male
Posts: 2.679


La musica è la forma d'arte suprema.


« Reply #6 on: 26-11-2010, 23:34:06 »

Ah..vero non ci avevo pensato, come si arriva a concludere che quella serie \frac{1}{i} è O(logm)?

Alla fine dato che dalla serie trovo O(logm) la soluzione non dovrebbe essere solo O(loglogn)? Perchè c'è un n a moltiplicare?
« Last Edit: 26-11-2010, 23:35:42 by Daréios » Logged

"Utilizzare sempre de l'Hôpital.....è come andare a caccia di farfalle con un bazooka".
shiny
Forumista
***
Offline Offline

Posts: 810



WWW
« Reply #7 on: 28-11-2010, 18:19:22 »

Ah..vero non ci avevo pensato, come si arriva a concludere che quella serie \frac{1}{i} è O(logm)?
\sum_{i=1}^m\ \frac{1}{i}\ \leq\ \sum_{i=0}^{\lfloor\log m \rfloor} \sum_{j=0}^{2^i -1}\ \frac{1}{2^i}\ =\ \sum_{i=0}^{\lfloor\log m \rfloor}\ 1\ \leq\ \log m\ +\ 1\ =\ \theta(\log m)

Alla fine dato che dalla serie trovo O(logm) la soluzione non dovrebbe essere solo O(loglogn)? Perchè c'è un n a moltiplicare?
T(2^m)\ =\ S(m)\ =\ 2^m R(m)\ =\ 2^m\log m

quindi

T(n)\ = n \log\log n

« Last Edit: 28-11-2010, 21:35:53 by shiny » Logged
Pages: [1]   Go Up
Print
Jump to: