Pages: [1] 2   Go Down
Print
Author Topic: Algoritmo Max-Heapify  (Read 3892 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: 28-07-2011, 14:23:37 »

Nel codice, in particole tra gli appunti del professore è specificato che l' algoritmo viene eseguito a partire da un nodo j e supponendo che i sottoalberi di destra e sinistra siano Max-Heap, ma allora a cosa serve?
L' algoritmo dovrebbe servire a garantire la proprietà di una Max-Heap, ma se io suppongo che al di sotto ho una max-heap, allora il codice sarà eseguito solo una volta?
Logged

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

Posts: 2.014


OM


« Reply #1 on: 28-07-2011, 15:04:50 »

no perché dopo che esegui max-heapify nel primo nodo potresti aver violato la proprietà di max-heap di uno degli alberi sottostanti, e allora dovresti procedere in quello e scendere fino dove è necessario per ripristinare la proprietà.
Logged

Un "buon informatico" trova una soluzione ad ogni tipo di problema. Un "ottimo informatico" trova la soluzione più efficiente ad ogni tipo di problema! Non stancatevi di migliorare la vostra soluzione!
Daréios89
Forumista Eroico
*****
Offline Offline

Gender: Male
Posts: 2.679


La musica è la forma d'arte suprema.


« Reply #2 on: 28-07-2011, 16:11:30 »

Quindi io ho ad esempio:

                                 10
                               /     \
                            7        8
                          /  \      /  \
                       11    6  ...   ....
                      .........


Io parto dal nodo che ha come elemento 7, scambio 11 con il 7 e poi se l' albero avesse un' altezza maggiore allora continuerei sulla foglia a sinistra che in questo caso coincide con il nodo dove metterò 7?
Logged

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

Posts: 2.014


OM


« Reply #3 on: 28-07-2011, 16:14:12 »

praticamente si. Andrai a controllare il 7 ancora con le radici dei sotto alberi sottostanti. In modo da fargli trovare la sua posizione.
Logged

Un "buon informatico" trova una soluzione ad ogni tipo di problema. Un "ottimo informatico" trova la soluzione più efficiente ad ogni tipo di problema! Non stancatevi di migliorare la vostra soluzione!
Daréios89
Forumista Eroico
*****
Offline Offline

Gender: Male
Posts: 2.679


La musica è la forma d'arte suprema.


« Reply #4 on: 28-07-2011, 16:22:45 »

Ti ringrazio, una piccola cosa off-topic, stavo facendo questa ricorrenza:

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

Mi blocco.....ho sostituito n=2^m

T(2^m)=2T(2^m/2)+2^m/\log(2^m)

Ho pensato di porre S(m)=T(2^m)

S(m)=2S(m/2)+2^m/\log(2^m)

Ma mi sa che non funziona, o sbaglio o conviene fare qualcos' altro....
Logged

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

Posts: 2.014


OM


« Reply #5 on: 28-07-2011, 16:43:53 »

non faccio ste cose da un bel pò (ho dato questa materia un paio di anni fa). Comunque la prima sostituzione può andare, se semplifichi il costo esterno credo che possa aiutarti per la seconda sostituzione.
log(2^m)= m
e quindi il costo esterno :
\frac{2^m}{m}

Però dovrei ragionarci un pò.
Logged

Un "buon informatico" trova una soluzione ad ogni tipo di problema. Un "ottimo informatico" trova la soluzione più efficiente ad ogni tipo di problema! Non stancatevi di migliorare la vostra soluzione!
cock86
Forumista Eroico
*****
Offline Offline

Posts: 2.014


OM


« Reply #6 on: 28-07-2011, 16:46:10 »

Ah dimenticavo... quel tipo di sostituzione se non ricordo male va fatta proprio per eliminarsi di torno la divisione per un logaritmo.
Logged

Un "buon informatico" trova una soluzione ad ogni tipo di problema. Un "ottimo informatico" trova la soluzione più efficiente ad ogni tipo di problema! Non stancatevi di migliorare la vostra soluzione!
corel_86
Forumista
***
Offline Offline

Gender: Male
Posts: 570



« Reply #7 on: 03-08-2011, 22:55:19 »

Per prima cosa guarda le slide qui cosi capirai i passaggi

Dobbiamo trasformare la ricorrenza in modo da poter applicare il Telescoping

T(n)=2T(n/2)+n/\log(n)
            |        |
            |        |
            a       b

1) pongo n=2^mquindi   m=\log_2(n) in generale n=b^mquindi   m=\log_b(n)

sostituisco e ottengo

T(2^m)=2T(2^{m-1})+\frac{2^m}{\log(2^m)} cioè

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

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

e sostituendo ottengo

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

3) pongo R(m)=S(m)/2^m in generale R(m)=S(m)/a^m

e sostituendo ottengo

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

4) Adesso applichiamo il Telescoping che troverai sulle slide e il risultato finale sarà

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

5) sostituendo m si ottiene

T(n)=n \sum_{i=1}^{\log_2n} 1/i

approssimando la sommatoria in \log_2n (Serie armonica)

otteniamo che T(n)=\theta (n\log_2\log_2n)

i passaggi dovrebbero essere giusti
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: 03-08-2011, 23:16:46 »

Scusa una cosa non mi quadra al passaggio 3, quel 2S(m-1), come mai scompare il 2? Per le potenze non diventa 2^{1-m}?
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 #9 on: 03-08-2011, 23:20:10 »

se ti guardi le slide capirai il perchè soprattutto l'esempio
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 #10 on: 04-08-2011, 20:46:13 »

Mh, non trovo quello che mi serve, a che pagina ti riferisci? A me non quadra quel passaggio 
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 #11 on: 04-08-2011, 21:20:26 »

pagina 13 puoi constatare che risulta R(m)=R(m-1) +\frac{f(b^m)}{a^m}

il termine a dall'equazione di ricorrenza non c'è più
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 #12 on: 04-08-2011, 21:49:21 »

Si, giusto, ma non capisco come fa a sparire, dalle proprietà delle potenze mi risulta un' altra cosa......non può scomparire semplicemente così.....se al denominatore nella ricorrenza venisse 2^{m-1} allora siamo d' accordo, ma viene con gli esponenti esattamente al contrario..
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 #13 on: 04-08-2011, 22:17:23 »

forse dipende dal fatto che c'è S(m-1)
anzichè S(m)

considera che verrebbe in questo modo
R(m)=\frac{S(m)}{a^m} quindi S(m)=R(m) a^m

sostituendo si ottiene

R(m) a^m=a R(m-1) a^{m-1} +f(b^m)

dividendo tutto per a^m si ha

R(m)= R(m-1)+\frac{f(b^m)}{a^m}

penso che sia cosi

« Last Edit: 04-08-2011, 22:26:38 by corel_86 » 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 #14 on: 04-08-2011, 22:24:39 »

Non mi convince....comunque non mi resta che prenderla per buona.... boh
Logged

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