Pages: [1]   Go Down
Print
Author Topic: Ricorrenza con albero  (Read 1371 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: 03-08-2011, 17:59:22 »

T(n)=T(n/2)+T(n/4)+T(n/8)+n

Come costruireste l' albero? Non capisco come determinare l' altezza visto che ho tre chiamate....
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: 03-08-2011, 21:39:28 »

si costruisce il seguente albero di ricorsione

Link Immagine

il costo totale totale di tutti i nodi alla profondità i e'

 (\frac{7}{8})^i n

per calcolare l'altezza dell'albero prendo il cammino più lungo che è

n \rightarrow \frac{n}{2}\rightarrow \frac{n}{4} \rightarrow . . . .\rightarrow 1

poiché
(\frac{1}{2})^k n\Rightarrowk=\log_2(n)

quindi in definitiva abbiamo

\sum_{i=0}^{\log_2(n)} (\frac{7}{8})^i n

calcolandoti questa serie troverai l'andamento asintotico dell'equazione di ricorrenza che se non sbaglio dovrebbe essere

\theta(n)

spero di esserti stato di aiuto
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: 03-08-2011, 21:42:05 »

Leggerò  domani che sono più fresco  yoh
Intanto potresti anche darmi una dritta per la ricorrenza che ho riportato in questa discussione? Grazie mille.

http://forum.sdai.unict.it/index.php?topic=13430.0

Scusa, non ti seguo su una cosa, non capisco come fai a sapere e individuare  il cammino più lungo?
« Last Edit: 03-08-2011, 21:46:18 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: 03-08-2011, 21:58:47 »

Scusa, non ti seguo su una cosa, non capisco come fai a sapere e individuare  il cammino più lungo?

Devi prendere il cammino che parte da n e arriva a 1 che ci fa più lentamente asintoticamente....

se per esempio abbiamo i seguenti cammini

n \rightarrow\frac{n}{3}\rightarrow\frac{n}{9}\rightarrow...\rightarrow1

n \rightarrow\frac{n}{2}\rightarrow\frac{n}{4}\rightarrow...\rightarrow1

quello più "lento" è questo

n \rightarrow\frac{n}{2}\rightarrow\frac{n}{4}\rightarrow...\rightarrow1
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: 03-08-2011, 23:08:14 »

Quindi nella mia ricorrenza dove compaiono \frac{n}{2}, \frac{n}{4}, \frac{n}{8} Come farei scusa? Tu hai confrontato due casi di crescita asintotica e ci siamo ma se devo confrontare solo quei valori come faccio?, il più lento non è \frac{n}{8} ?
Cioè quì a differenza del tuo esempio dove confronto due cammini ne ho uno solo, ma come faccio a stabilire la frazione mi indica l' altezza?
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 #5 on: 03-08-2011, 23:19:30 »

no perchè quello che va più lentamente è il cammino n \rightarrow \frac{n}{2} \rightarrow \frac{n}{4}

quei percorsi che ho fatto io sono solo un esempio

qui sotto c'è un altro esempio che non c'entra nulla con l'esercizio
n \rightarrow\frac{n}{4}\rightarrow\frac{n}{16}\rightarrow...\rightarrow1

n \rightarrow\frac{n}{8}\rightarrow\frac{n}{64}\rightarrow...\rightarrow1

quello più "lento" è questo

n \rightarrow\frac{n}{4}\rightarrow\frac{n}{16}\rightarrow...\rightarrow1
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 #6 on: 04-08-2011, 18:18:17 »

Ah, e per esempio nell' ultimo tuo esempio, se dovessi stabilire la base dell' altezza di un albero sarebbe \log_4(n) ?
Inoltre nella serie non trascuri il costo del lavoro esterno? Cioè anche sulla base di quello che c' è tra gli appunti la serie dovrebbe anche contenere il numero di nodi per cui il costo diventa poi \theta(1), quindi del tipo:

\sum_{i=0}^{\log(n)-1} {\frac{7}{8}}^in+n^{\log_2(\frac{7}{8})}\theta(1)

Se non la vedi bene:

Link Immagine

Sempre se l' altezza è log_2(n) e si può fare quel passaggio, è l' unica cosa che mi manca...
« Last Edit: 04-08-2011, 18:28:39 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 #7 on: 04-08-2011, 20:33:49 »

bisogna risolvere questa serie:
rispolverando i manuali di analisi ti accorgi che la serie è la serie geometrica:
\sum_{i=0}^{n} (x)^i = \frac{1-(x)^{n+1}}{1-x}

quindi tornando all'esercizio:

n\sum_{i=0}^{\log_2(n)} (\frac{7}{8})^i= \rightarrown viene portato fuori perché è una costante

=n\frac{1-(\frac{7}{8})^{\log_2(n)+1}}{1-\frac{7}{8}}

applicando le regole delle potenze e dei logaritmi dovrebbe risultarti \theta(n)
« Last Edit: 29-11-2012, 15:31:43 by corel_86 » Logged

Se trovo qualcosa che non va lo faccio presente subito

Saluti ciaociao ciao

A.C.
Pages: [1]   Go Up
Print
Jump to: