Pages: [1]   Go Down
Print
Author Topic: Aiuto soluzione ricorrenza  (Read 1453 times)
0 Members e 1 Utente non registrato stanno visualizzando questa discussione.
Angelo
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 274



« on: 15-09-2011, 07:52:44 »

T(n)= T(n/2) + \sqrt{n} ....come risolverla?
Logged

..elimindo il ponte pedonale di andrea doria..hanno eliminato una parte di me!..
Daréios89
Forumista Eroico
*****
Offline Offline

Gender: Male
Posts: 2.679


La musica è la forma d'arte suprema.


« Reply #1 on: 15-09-2011, 11:37:35 »

Mh....hai provato a sostituire m=\log_2(n) ?
Si potrebbe anche tentare un' altra strada......hai la soluzione? Per caso è T(n)=\theta(\sqrt{n}) ?
« Last Edit: 15-09-2011, 11:41:42 by Daréios » Logged

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

Gender: Male
Posts: 274



« Reply #2 on: 15-09-2011, 11:55:54 »

si la soluzione è proprio quella..quindi per sostituzione..
Logged

..elimindo il ponte pedonale di andrea doria..hanno eliminato una parte di me!..
shiny
Forumista
***
Offline Offline

Posts: 810



WWW
« Reply #3 on: 15-09-2011, 13:34:22 »

T(n)\ =\ T(n/2) + \sqrt n

T(2^k)\ =\ T(2^{k-1}) + 2^{k/2}

S(k)\ =\ S(k-1) + 2^{k/2}

S(k)\ =\ \sum_{i=0}^{k-1}\ 2^{i/2}\ =\ 2^{k/2} - 1

T(n)\ =\ \sqrt n -1\ =\ \Theta(\sqrt n)


« Last Edit: 17-09-2011, 12:19:02 by shiny » Logged
Daréios89
Forumista Eroico
*****
Offline Offline

Gender: Male
Posts: 2.679


La musica è la forma d'arte suprema.


« Reply #4 on: 15-09-2011, 13:39:22 »

si la soluzione è proprio quella..quindi per sostituzione..

O per sostituzione, o con l' albero di ricorsione, oppure forse con il 3° caso del teorema master, non ho verificato la condizione di regolarità.
Logged

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

Gender: Male
Posts: 603


« Reply #5 on: 15-09-2011, 16:39:41 »

T(n)\ =\ T(n/2) + \sqrt n

T(2^k)\ =\ T(2^{k-1}) + 2^{k/2}

S(k)\ =\ S(k-1) + 2^{k/2}

S(k)\ =\ \sum_{i=0}^{k-1}\ 2^{i/2}\ =\ 2^{k/2} - 1

T(n)\ =\ \sqrt n



Shiny ma chi sei, ti conosco ? 
Logged
shiny
Forumista
***
Offline Offline

Posts: 810



WWW
« Reply #6 on: 15-09-2011, 16:53:18 »

Quest'anno ho seguito A.I. e il mio nome e' Gabriele Basile non se se si ricorda... ero il ragazzo alto e magro che accendeva il proiettore in sostituzione del ragazzo titolare  univ
Logged
Vincenzo Cutello
Administrator
Forumista
*****
Offline Offline

Gender: Male
Posts: 603


« Reply #7 on: 15-09-2011, 22:25:47 »

Quest'anno ho seguito A.I. e il mio nome e' Gabriele Basile non se se si ricorda... ero il ragazzo alto e magro che accendeva il proiettore in sostituzione del ragazzo titolare  univ
Ho un vago ricordo. Passa a trovarmi quando puoi e facciamo 2 chiacchere.
Logged
Pages: [1]   Go Up
Print
Jump to: