Pages: [1] 2   Go Down
Print
Author Topic: Altra ricorrenza  (Read 1509 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: 26-08-2011, 19:10:14 »

T(n)=8T(n/2)+n^2\log(n)

Ho posto m=\log_2(n)

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

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

R(m)=4R(m-1)+m

Se fin qui vi quadra, adesso dovrei risolvere questa con l' albero, i costi sono:

m
4m-4
16m-16
.
.
.

Non riesco come al solito a formalizzare questo costo, perchè ovviamente si tratta di 4^i però non riesco a formalizzarlo correttamente perchè mi manca qualcosa sempre....
Ma con il teorema Master si può risolvere? Non mi risulta.
« Last Edit: 26-08-2011, 23:10:16 by Daréios » Logged

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

Gender: Male
Posts: 570



« Reply #1 on: 26-08-2011, 23:27:42 »

T(n)=8T(n/2)+n^2\log(n)

Ho posto m=\log_2(n)

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

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

R(m)=4R(m-1)+m

Se fin qui vi quadra, adesso dovrei risolvere questa con l' albero, i costi sono:

m
4m-4
16m-16
.
.
.

Non riesco come al solito a formalizzare questo costo, perchè ovviamente si tratta di 4^i però non riesco a formalizzarlo correttamente perchè mi manca qualcosa sempre....
Ma con il teorema Master si può risolvere? Non mi risulta.

hai sbagliato il risultato applicato il telescoping è questo
T(n)=8^m \sum_{i=1}^m (\frac{i}{2^i})

e sostituendo m si ottiene

T(n)=n^3 \sum_{i=1}^{log(n)} (\frac{i}{2^i})

risolvendo la sommatoria ottieni il risultato finale

riguardati i passaggi che abbiamo scritto qui
Logged

Se trovo qualcosa che non va lo faccio presente subito

Saluti ciaociao ciao

A.C.
Daréios89
Forumista Eroico
*****
Offline Offline

Gender: Male
Posts: 2.679


La musica è la forma d'arte suprema.


« Reply #2 on: 26-08-2011, 23:32:50 »

Che significa ho sbagliato il risultato? Sapresti indicarmi il punto dove ho sbagliato?

EDIT: Si credo di avere trovato, forse devo sostituire R(m)=\frac{T(m)}{2^{2m}} sarà da queste parti l' errore, vediamo se domani lo becco.
« Last Edit: 26-08-2011, 23:38:45 by Daréios » Logged

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

Gender: Male
Posts: 570



« Reply #3 on: 26-08-2011, 23:40:51 »

ti posto tutti i passaggi

T(n)=8T(n/2)+n^2\log(n)

n=2^m \rightarrow m=\log_2(n)

T(2^m)=8T(2^{m-1})+4^{m}m
--------------------------------------------------------------------
S(m)=T(2^m)

T(m)=8T(m-1)+4^{m}m
--------------------------------------------------------------------
R(m)=S(m)/8^m

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

R(m)=R(m-1)+(\frac{1}{2})^m m
--------------------------------------------------------------------
applico la regola del telescoping e ottengo

T(n)=8^m \sum_{i=1}^{m} (\frac{i}{2^i})

T(n)=n^3 \sum_{i=1}^{log(n)} (\frac{i}{2^i})

trovata la sommatoria ottengo il risultato finale
Logged

Se trovo qualcosa che non va lo faccio presente subito

Saluti ciaociao ciao

A.C.
Daréios89
Forumista Eroico
*****
Offline Offline

Gender: Male
Posts: 2.679


La musica è la forma d'arte suprema.


« Reply #4 on: 26-08-2011, 23:43:04 »

Grazie, provo domani a rifarla e in caso dò un' occhiata se ho problemi, per ora non guardo, grazie corel 
Logged

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

Gender: Male
Posts: 564


"Quanto manca alla vetta?";"Tu sali e non pensare"


« Reply #5 on: 27-08-2011, 01:27:43 »

corel_86 noto con profondo piacere che ci stai aiutando veramente parecchio......e di questo ti ringrazio veramente tanto!!
Volevo chiedere ma in questo caso questa ricorrenza non si poteva fare usando il teorema master??perchè:
a=8 , b=2, -> n^log_2 ( 8 )  = n^3 -> f(n)=Θ( n^3 )
Visto che si verificano queste ipotesi non possiamo applicare il secondo caso del teorema master?e quindi T(n)=O(n^3\log(n) )??
Logged

"A cavallina....a cavallina.....a chi era bedda quannu  curreva" [Cit.  Dal Tenerissimo via plebiscito]
shiny
Forumista
***
Offline Offline

Posts: 810



WWW
« Reply #6 on: 27-08-2011, 03:03:08 »

Io l'ho svolta cosi'...

  • applicando il teo master, per il primo caso, la complessita' e'
    T(n)\ =\ \Theta(n^3)
  • dal risultato di corel
    T(n)\ =\ n^3 \sum_{i=1}^{log(n)} (\frac{i}{2^i})\ \leq\ n^3 \sum_{i=1}^{\infty} (\frac{i}{2^i})\ \leq\ n^3\ O(1)\ =\ \Theta(n^3)


« Last Edit: 27-08-2011, 13:25:50 by shiny » Logged
corel_86
Forumista
***
Offline Offline

Gender: Male
Posts: 570



« Reply #7 on: 27-08-2011, 09:15:11 »

corel_86 noto con profondo piacere che ci stai aiutando veramente parecchio......e di questo ti ringrazio veramente tanto!!
Volevo chiedere ma in questo caso questa ricorrenza non si poteva fare usando il teorema master??perchè:
a=8 , b=2, -> n^log_2 ( 8 )  = n^3 -> f(n)=Θ( n^3 )
Visto che si verificano queste ipotesi non possiamo applicare il secondo caso del teorema master?e quindi T(n)=O(n^3\log(n) )??

Il teorema master si applica alle equazioni di ricorrenza che si presentano nella forma

T(n)=aT(n/b) + f(n)

quindi si può applicare a quella ricorrenza

proprio come ha fatto shiny che ha applicato il 1° Teorema Master

Comunque cambiando discorso per me aiutare è un piacere dato che io ho già dato questa materia non vedo perchè non debba aiutare quelli che ne hanno bisogno......

Sono sempre a disposizione....o quasi   [Emoticon] Asd [Emoticon] Asd
Logged

Se trovo qualcosa che non va lo faccio presente subito

Saluti ciaociao ciao

A.C.
Daréios89
Forumista Eroico
*****
Offline Offline

Gender: Male
Posts: 2.679


La musica è la forma d'arte suprema.


« Reply #8 on: 27-08-2011, 11:02:57 »

Io avrei:

n^2\log(n)    e  n^3

Dovrei trovare un \epsilon>0 tale che f(n)=O(n^{\log_b(a)})

Per esempio se scelgo \frac{1}{2} mi sembra funzioni, giusto?

Invece con il metodo di corel arrivo a conclusioni diverse, perchè io ho:

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

Il telescoping io sapevo si applica quando si ha una sola funzione, abbiamo un prodotto noi, comunque ho pensato:

\sum_{i=0}^{m-1}(\frac{1}{2})^i*m

E' sbagliato far partire da zero la serie?
che comunque mi risulta 2, e con m a moltiplicare 2m.
Poi rifacendo le sostituzioni, e trascurando la costante 2, mi risulta come aveva postato un utente T(n)=O(n^3\log(n))  testate
Logged

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

Posts: 810



WWW
« Reply #9 on: 27-08-2011, 13:28:18 »



\sum_{i=0}^{m-1}(\fr<br />che comunque mi risulta 2, e con [tex]m a moltiplicare 2m.
Poi rifacendo le sostituzioni, e trascurando la costante 2, mi risulta come aveva postato un utente T(n)=O(n^3\log(n))  testate

Non so come hai svolto la serie o come ci arrivi ma cio' che ha scritto corel e' coretto e inoltre io ti ho espletato i passaggi per la risoluzione e in particolare ti sara' sfuggito questo passaggio n^3 \sum_{i=1}^{\infty} (\frac{i}{2^i})\ \leq\ n^3\ O(1) che ho svolto applicando il criterio del rapporto alla serie, la quale essendo convergente posso sostituirla con O(1)
Logged
corel_86
Forumista
***
Offline Offline

Gender: Male
Posts: 570



« Reply #10 on: 27-08-2011, 15:30:49 »

per Dareidos tu hai scritto la serie in questo modo

\sum_{i=0}^{m-1}(\frac{1}{2})^i*m

quando invece la serie è così

8^m\sum_{i=1}^{m}(\frac{1}{2})^i\times i non per m come hai scritto tu

e come ha detto shiny la serie è convergente.......inoltre la serie risulta
\frac{1}{2} +\frac{2}{4} +\frac{3}{8}+\frac{4}{16}+......... questo valido per m

comunque i passaggi sono giusti gli ho verificati due volte ho applicato il metodo che c'è sulle slide
Logged

Se trovo qualcosa che non va lo faccio presente subito

Saluti ciaociao ciao

A.C.
callo
Forumista
***
Offline Offline

Gender: Male
Posts: 564


"Quanto manca alla vetta?";"Tu sali e non pensare"


« Reply #11 on: 27-08-2011, 17:56:23 »

Io avrei:

n^2\log(n)    e  n^3

Dovrei trovare un \epsilon>0 tale che f(n)=O(n^{\log_b(a)})

Per esempio se scelgo \frac{1}{2} mi sembra funzioni, giusto?

Invece con il metodo di corel arrivo a conclusioni diverse, perchè io ho:

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

Il telescoping io sapevo si applica quando si ha una sola funzione, abbiamo un prodotto noi, comunque ho pensato:

\sum_{i=0}^{m-1}(\frac{1}{2})^i*m

E' sbagliato far partire da zero la serie?
che comunque mi risulta 2, e con m a moltiplicare 2m.
Poi rifacendo le sostituzioni, e trascurando la costante 2, mi risulta come aveva postato un utente T(n)=O(n^3\log(n))  testate

epsilon deve essere un numero compreso tra 0 e 1 ma  1/2 ancora non va bene......con valori di epsilon però maggiori di 0.5 vai tranquillo!!
Comunque pensandoci bene non può essere il secondo caso(come avevo detto precedentemente) perché f(n)=O(n^...) e non come avevo detto io f(n)=theta(n^....) ....che errore!!anzi...che ORRORE!!    quindi per valori di epsilon >0.5>0 T(n)=theta(n^3)
Logged

"A cavallina....a cavallina.....a chi era bedda quannu  curreva" [Cit.  Dal Tenerissimo via plebiscito]
Daréios89
Forumista Eroico
*****
Offline Offline

Gender: Male
Posts: 2.679


La musica è la forma d'arte suprema.


« Reply #12 on: 27-08-2011, 18:09:36 »

Quote
epsilon deve essere un numero compreso tra 0 e 1 ma  1/2 ancora non va bene

Se \epsilon=\frac{1}{2} avrei n^2\log(n)  e  n^{\frac{5}{2}}

Se considero il limite:

\frac{n^2\log(n)}{n^{\frac{5}{2}} dovrebbe diventare \frac{\log(n)}{\sqrt{n}}

Che fa 0, quindi il numeratore è infinito di ordine inferiore rispetto al denominatore e quindi ci ritroveremmo nel primo caso del teorema master....

corel non metto in dubbio il tuo, ma il mio procedimento  testate

Non capisco:

T(n)=8^m \sum_{i=1}^{m} (\frac{i}{2^i})

Perchè se avevamo R(m) hai sostituito prima mettendo T(n)? Come mai c' è quell'8^m prima della somma? Nella ricorrenza c' era un m a moltiplicare......riseguendo il classico ragionamento che abbiamo fatto l' altra volta non riesco a seguirti. Cioè 8^m equivale ad n^3 ma all' interno della sommatoria avremmo \frac{1}{2}^m che moltiplica m, non capisco proprio come sei arrivato a fare quella cosa.
« Last Edit: 27-08-2011, 18:29:18 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 #13 on: 28-08-2011, 02:00:19 »

Ad un certo punto, corel, ha usato questa sostituzione

R(m)\ =\ S(m)/8^m\ \Longrightarrow\ 8^mR(m)=S(m)=T(n)\quad\quad (1)

da cui se

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

allora per la (1)

T(n)=S(m)=8^mR(m)=8^m\sum_{i=1}^{m} (\frac{i}{2^i})

Spero di essere stato chiaro perche' meglio di cosi' non lo saprei spiegare
« Last Edit: 28-08-2011, 02:06:00 by shiny » Logged
Daréios89
Forumista Eroico
*****
Offline Offline

Gender: Male
Posts: 2.679


La musica è la forma d'arte suprema.


« Reply #14 on: 28-08-2011, 10:36:25 »

Si ora si, ho capito, mi mancava una sostituzione, resta solo una cosa.
Il telescoping si applica ad esempio in

T(n)=T(n-1)+n

E diventa \sum_{i}{}f(i)

Ma prima ancora di quella sostituzione di cui mi hai parlato, la sommatoria, o meglio la ricorrenza è:

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

Allora che si possa usare il telescoping si, perchè abbiamo la serie geometrica, ma come facciamo a liberarci della m a moltiplicare?
« Last Edit: 28-08-2011, 10:44:53 by Daréios » Logged

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