Pages: [1]   Go Down
Print
Author Topic: Ricorrenza  (Read 1494 times)
0 Members e 1 Utente non registrato stanno visualizzando questa discussione.
AnGeL88
Matricola
*
Offline Offline

Gender: Female
Posts: 96



« on: 28-10-2010, 12:32:14 »

come risolvereste questa ricorrenza tramite sostituzione?
T(n)= 2T(\sqrt n)+1

Grazie per la risposta  
« Last Edit: 28-10-2010, 12:34:32 by AnGeL88 » Logged

I computer sono incredibilmente veloci, accurati e stupidi. Gli uomini sono incredibilmente lenti, inaccurati e intelligenti. Insieme sono una potenza che supera l'immaginazione.
andreacannella
Administrator
Forumista Esperto
*****
Offline Offline

Gender: Male
Posts: 1.488


Andea Cannella - www.andreacannella.com


WWW
« Reply #1 on: 28-10-2010, 16:17:38 »

come risolvereste questa ricorrenza tramite sostituzione?
T(n)= 2T(\sqrt n)+1

Grazie per la risposta 


Allora:
1) T(n)= 2T(\sqrt n)+1;
2) \log n=m \Leftrightarrow n=2^{m}
3) T(2^{m})= 2T(2^{\frac{m}{2}})+1;
4) S(m)= T(2^{m});
5) S(m)= S(\frac{m}{2})+1;

Applichiamo il teorema master alla 5. E` verificato il secondo caso in quanto le due funzioni sono \Theta l'una dell'altra. Quindi la soluzione della 5 è \Theta (\log m) e quindi la soluzione sarà T(n) = \Theta (\log \log n)

Spero di non aver commesso errori/orrori...

Saluti
 ciao ciao

Andrea
« Last Edit: 28-10-2010, 17:36:39 by andreacannella » Logged

Le tre grandi virtù di un programmatore: pigrizia, impazienza e arroganza. (Larry Wall)

Good times for a change
See, the luck I've had
Can make a good man
Turn bad

So please, please, please
Let me, let me, let me
Let me get what I want
This time

The Smiths
esteta84
Apprendista Forumista
**
Offline Offline

Posts: 284



« Reply #2 on: 06-11-2010, 12:02:18 »

Magari sto per fare una domanda stupida...
però mi chiedevo se dal punto 5 è possibile continuare a  risolvere senza applicare il teorema master?
Logged
shiny
Forumista
***
Offline Offline

Posts: 810



WWW
« Reply #3 on: 06-11-2010, 13:59:36 »

questi dovrebbero essere gli altri passaggi:

6 ) m\ =\ 2^{k}\ \Leftrightarrow\ \log m\ =\ k
7 ) S(2^{k})\ =\ S(2^{k-1})\ +\ 1
8 ) R(k)\ =\ R(k-1)+1
9 ) R(k)\ =\ \Theta(k)\ =\ \Theta(\log m)\ =\ \Theta(\log \log n)
« Last Edit: 06-11-2010, 14:03:45 by shiny » Logged
esteta84
Apprendista Forumista
**
Offline Offline

Posts: 284



« Reply #4 on: 06-11-2010, 16:59:28 »

Ma cmq penso ci sia un errore al punto 5... non dovrebbe esserci il 2 a moltiplicare?

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

e quest'ultima se non sbaglio dovrebbe essere  O(m lgm)

spero che io non stia fantasticando  testate
« Last Edit: 06-11-2010, 17:16:07 by esteta84 » Logged
Crasher
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 417



« Reply #5 on: 06-11-2010, 19:20:00 »

mmh ecco come una costante fa fallire la risoluzione di un'intera ricorrenza...

la costante probabilmente ci va messa, ma in ogni caso non ricadiamo sul 1° caso del Master? Quindi O(m) = O(logn)testate

Logged

Diventa ciò che sei nato per essere
shiny
Forumista
***
Offline Offline

Posts: 810



WWW
« Reply #6 on: 07-11-2010, 01:03:27 »

Ma cmq penso ci sia un errore al punto 5... non dovrebbe esserci il 2 a moltiplicare?

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

e quest'ultima se non sbaglio dovrebbe essere  O(m lgm)

spero che io non stia fantasticando  testate
mi sa che hai ragione... io avevo supposto che i passaggi fatti fossero giusti senza neanche leggerli... questi dovrebbero essere i passaggi corretti

6 ) m\ =\ 2^{k}\ \Leftrightarrow\ \log m\ =\ k
7 ) S(2^{k})\ =\ 2S(2^{k-1})\ +\ 1
8 ) \frac{S(2^k)}{2^k}\ =\ \frac{S(2^{k-1})}{2^{k-1}}\ +\ \frac{1}{2^k}
8 ) R(k)\ =\ R(k-1)\ +\ \frac{1}{2^k}
9 ) R(k)\ =\ \sum_{i=0}^{k}{\frac{1}{2^k}} \ =\ 2\ -\ \frac{1}{2^k} \
10 ) S(2^k)=2^k\ R(k)=\Theta(2^k)\ \rightarrow\ S(m)=\Theta(m)\ \rightarrow\ T(n)\ =\ \Theta(\log n)
Logged
esteta84
Apprendista Forumista
**
Offline Offline

Posts: 284



« Reply #7 on: 10-11-2010, 13:01:34 »

ho un altro dubbio  testate
ma il punto 9) non dovrebbe essere così?
 R(k)\ =\ \sum_{i=0}^{k}{\frac{1}{2^k}} \ =\ 2

perchè siamo in presenza di una serie geometrica di ragione, in valore assoluto, <1
Logged
shiny
Forumista
***
Offline Offline

Posts: 810



WWW
« Reply #8 on: 10-11-2010, 21:00:24 »

ho un altro dubbio  testate
ma il punto 9) non dovrebbe essere così?
 R(k)\ =\ \sum_{i=0}^{k}{\frac{1}{2^k}} \ =\ 2

perchè siamo in presenza di una serie geometrica di ragione, in valore assoluto, <1

appunto perche' una serie geometrica di ragione \frac{1}{2} fa

R(k)\ =\ \sum_{i=0}^{k}{\frac{1}{2^i}} \ =\ \frac{1\ -\ \frac{1}{2^{k+1}}}{1 - \frac{1}{2}}\ =\ 2\ -\ 2\ \frac{1}{2^{k+1}}\ =\ 2\ -\ \frac{1}{2^{k}

il 2 da dove l'hai preso? testate testate testate testate

« Last Edit: 14-11-2010, 11:53:46 by shiny » Logged
esteta84
Apprendista Forumista
**
Offline Offline

Posts: 284



« Reply #9 on: 11-11-2010, 07:17:51 »

io pensavo che si risolvesse così:

R(k)\ =\ \sum_{i=0}^{k}{\frac{1}{2^i}} \ =\ \frac{1}{1-\frac{1}{2}}\ =\ 2

però quello si applica solo nel caso in cui nella sommatoria, i va da 0 a infinito.
Ok penso di aver capito grazie shiny
« Last Edit: 11-11-2010, 07:28:55 by esteta84 » Logged
Daréios89
Forumista Eroico
*****
Offline Offline

Gender: Male
Posts: 2.679


La musica è la forma d'arte suprema.


« Reply #10 on: 15-11-2010, 19:48:32 »

come risolvereste questa ricorrenza tramite sostituzione?
T(n)= 2T(\sqrt n)+1

Grazie per la risposta 


Allora:
1) T(n)= 2T(\sqrt n)+1;
2) \log n=m \Leftrightarrow n=2^{m}
3) T(2^{m})= 2T(2^{\frac{m}{2}})+1;
4) S(m)= T(2^{m});
5) S(m)= S(\frac{m}{2})+1;

Applichiamo il teorema master alla 5. E` verificato il secondo caso in quanto le due funzioni sono \Theta l'una dell'altra. Quindi la soluzione della 5 è \Theta (\log m) e quindi la soluzione sarà T(n) = \Theta (\log \log n)

Spero di non aver commesso errori/orrori...

Saluti
 ciao ciao

Andrea


Io ho seguito questo ragionamento, alla fine manca il due a moltiplicare e dovremmo avere:
S(m)=2S(m/2)+1

Quindi...dovremmo ricadere nel primo caso del teorema Master?
La soluzione dovrebbe essere \theta(m) e quindi \theta(logn) ?
Logged

"Utilizzare sempre de l'Hôpital.....è come andare a caccia di farfalle con un bazooka".
Pages: [1]   Go Up
Print
Jump to: