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

Posts: 87



« on: 15-12-2011, 11:15:17 »

Salve, ho un dubbio per quanto riguarda lo svolgimento della seguente ricorrenza:
T(n)=4T(\frac{n}{2}) + n \log_2(n)

Qualcuno può aiutarmi??
Logged
mafalda
Apprendista Forumista
**
Offline Offline

Posts: 430


CЯΣDΣЯCI SΣMPЯΣ, ΛЯЯΣПDΣЯSI MΛI!


« Reply #1 on: 15-12-2011, 13:48:08 »

Se non erro, applicando il teorema Master la soluzione è: O(n^{2})
Logged

...๔єςเ, ๔єςเ, ๔єςเ...
InTheZone
Matricola
*
Offline Offline

Posts: 40



« Reply #2 on: 15-12-2011, 13:52:15 »

Provo con il metodo della sostituzione:
poniamo n = 2^m ovvero: m=logn

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

Poniamo T(2^m)=S(m)

S(m)=4S(m-1)+ 2^mlog 2^m

Dividiamo tutto per 4^m

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

Poniamo \frac{S(m)}{4^m}=R(m)

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

sciogliamo:
\frac{ 2^mlog 2^m}{4^m}= \frac{2^m m(log2)}{4^m}
=
\frac{2^m}{4^m} *m

A questo punto abbiamo una serie telescopica
\sum_{i}   (\frac{1}{2})^i * i <= \sum_{i}   (\frac{1}{2})^i * m = m * \sum_{i}   (\frac{1}{2})^i

Questa è una serie geometrica di ragione 1/2 che risulta 2, quindi viene

m * 2

sappiamo che m=logn quindi 2logn
Ricordiamoci però che R(m) proviene da \frac{S(m)}{4^m}, portiamo 4^m al secondo membro e viene 4^m2log n
4^m=4^{logn} , ovvero, n^{log4} cioè n^2

quindi assemblando il tutto abbiamo 2n^2logn e quindi \Theta(n^2logn)

Spero di non aver fatto errori, e soprattutto di essere stato chiaro....Ciao!
Logged
vincenzo86
Forumista
***
Offline Offline

Gender: Male
Posts: 505



« Reply #3 on: 15-12-2011, 16:57:39 »

In questa ricorrenza rientramo nel primo caso del Teorema Master, quindi la soluzione dovrebbe essere T(n)=\theta(n^2)
Logged
Pages: [1]   Go Up
Print
Jump to: