Pages: [1]   Go Down
Print
Author Topic: Svolgimento ricorrenza con albero di ricorsione  (Read 1658 times)
0 Members e 1 Utente non registrato stanno visualizzando questa discussione.
Fra83
Apprendista Forumista
**
Offline Offline

Posts: 213



« on: 08-05-2011, 22:21:37 »

Salve a tutti, ho svolto questa ricorrenza T(n)=T(\frac{n}{3})+2T(\frac{n}{2})+n, ma ho qualche dubbio...Ecco il procedimento (con l'albero di ricorsione):

                                                                    n  --------------------->  n
                                                                /   |   \
                                                               /    |    \
                                                         1/3n  1/2n  1/2n ------------>  (4/3) n
                                                          /  |  \
                                                         /   |   \
                                                 1/9n  1/4n  1/4n . . . . . .... -------> (4/3)^2n
                                                           .
                                                           .
                                                           .




                      T(n)=\sum_{i=0}^log n (4/3)^i
                     Facendo i vari calcoli, alla fine mi risulta T(n)=\theta(n^2).
                    
Qualcuno potrebbe postare il procedimento corretto? (se ho fatto errori).
Grazie
« Last Edit: 08-05-2011, 22:33:48 by Fra83 » Logged
Daréios89
Forumista Eroico
*****
Offline Offline

Gender: Male
Posts: 2.679


La musica è la forma d'arte suprema.


« Reply #1 on: 08-05-2011, 23:40:29 »

Non ho capito come hai costruito l' albero.....perchè nei nodi metti:

1/3n 1/2n ?

non dovrebbe essere:

n/3 n/2 n/2 ?
Logged

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

Posts: 810



WWW
« Reply #2 on: 09-05-2011, 00:52:49 »

i passaggi corretti sono questi

0: n

1: \frac{n}{3} + \frac{n}{2} + \frac{n}{2}

2: \frac{n}{9} + \frac{n}{6} + \frac{n}{6} + \frac{n}{6} + \frac{n}{4} + \frac{n}{4} + \frac{n}{6} + \frac{n}{4} + \frac{n}{4}

...
Logged
Daréios89
Forumista Eroico
*****
Offline Offline

Gender: Male
Posts: 2.679


La musica è la forma d'arte suprema.


« Reply #3 on: 09-05-2011, 10:07:28 »

A me verrebbe \theta(n) non so.
P.S ma qui nella sommatoria come si fa a stabilire l' altezza dell' albero?
« Last Edit: 09-05-2011, 10:15:28 by Daréios » Logged

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

Posts: 213



« Reply #4 on: 09-05-2011, 11:03:13 »

Code:
Non ho capito come hai costruito l' albero.....perchè nei nodi metti:

1/3n 1/2n ?

non dovrebbe essere:

n/3 n/2 n/2 ?]

1/3 n è la stessa cosa di n/3.
Code:
P.S ma qui nella sommatoria come si fa a stabilire l' altezza dell' albero?
Si prende l'altezza maggiore, e in questo caso è \log_2(n)


Logged
Fra83
Apprendista Forumista
**
Offline Offline

Posts: 213



« Reply #5 on: 09-05-2011, 12:07:17 »

Code:
i passaggi corretti sono questi

0:

1:

2:

...
Grazie shiny.

Ho provato a svolgerla di nuovo e mi risulta sempre T(n)=\theta(n^2). Potresti cortesemente postare il procedimento? Grazie mille
Logged
Daréios89
Forumista Eroico
*****
Offline Offline

Gender: Male
Posts: 2.679


La musica è la forma d'arte suprema.


« Reply #6 on: 09-05-2011, 12:32:40 »

Quote
1/3 n è la stessa cosa di n/3

Si ma la tua scrittura era ambigua 

Non dovrei avere un calcolo come questo?

\sum_{i}\frac{4}{3}^i+\theta(n^{\log_23})
Logged

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

Posts: 213



« Reply #7 on: 09-05-2011, 16:27:54 »

Si, e dal calcolo della serie mi viene THETA(n^2)
Logged
Daréios89
Forumista Eroico
*****
Offline Offline

Gender: Male
Posts: 2.679


La musica è la forma d'arte suprema.


« Reply #8 on: 09-05-2011, 16:45:27 »

Si ho fatto i conti male io, il logaritmo dovrebbe essere circa 1.58, per cui arrotondando a 2 il risultato sembra corretto.
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: 10-05-2011, 23:23:53 »

Grazie shiny.

Ho provato a svolgerla di nuovo e mi risulta sempre T(n)=\theta(n^2). Potresti cortesemente postare il procedimento? Grazie mille

T(n)\ =\ \sum_{i=0}^{\log_2 n}\ \(\frac{4}{3}\)^i

T(n)\ =\ \frac{\(\frac{4}{3}\)^{\log_2(n)+ 1}\ -\ 1}{\frac{4}{3} -1}

T(n)\ =\ \frac{4^{\log_2(n)+ 1}}{3^{\log_2(n)}}\ -\ 3

T(n)\ =\ \frac{4^{\log_2(n)+ 1}}{3^{\log_2(n)}}\ -\ 3

T(n)\ =\ \frac{4 n^2}{n^{\log_2 3}}\ -\ 3

T(n)\ =\ O(n^2)
« Last Edit: 10-05-2011, 23:30:17 by shiny » Logged
Fra83
Apprendista Forumista
**
Offline Offline

Posts: 213



« Reply #10 on: 10-05-2011, 23:31:50 »

Grazie mille!
Logged
shiny
Forumista
***
Offline Offline

Posts: 810



WWW
« Reply #11 on: 10-05-2011, 23:33:49 »

non so se ho sbagliato qualcosa ma i passaggi dovrebbero essere corretti  
Logged
Daréios89
Forumista Eroico
*****
Offline Offline

Gender: Male
Posts: 2.679


La musica è la forma d'arte suprema.


« Reply #12 on: 11-05-2011, 09:36:48 »

La somma non dovrebbe essere:

\frac{1-x^{n+1}}{1-x} ?
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: 11-05-2011, 10:34:37 »

La somma non dovrebbe essere:

\frac{1-x^{n+1}}{1-x} ?

e scusa io cosa ho scritto? testate
Logged
Pages: [1]   Go Up
Print
Jump to: