jump to navigation

Heapsort – costo computazionale 21 gennaio 2008

Posted by fripp in Algoritmi, Heapsort, Informatica, Matematica, Ordinamento.
Tags: , , , , , ,
trackback

Per dimostrare che il costo computazionale dello heapsort è O(n \log n) occorre prima dimostrare alcune proprietà dello heap.

Proprietà 1

Uno heap con n nodi ha altezza \Theta(\log n)

Dimostrazione:

Sia h il numero di livello dello heap. I primi (h-1) livelli sono tutti completi, e il numero di nodi in esso contenuti è pari a \sum_{i=0}^{h-1}2^{i}=2^{h}-1.

In maniera analoga, il numero di nodi in h livelli è \leq 2^{h+1}-1.

Da questo concludiamo che 2^{h}-1 \leq n \leq 2^{h+1}-1.

Prendendo il logaritmo di ambo i membri otteniamo che h=\Theta(\log n)

Proprietà 2

Il numero di nodi di altezza h in uno heap con n nodi è \left \lceil \frac{n}{2^{h+1}}\right \rceil.

Dimostrazione:

Dimostriamo la proprietà per induzione rispetto ad h.
Dimostriamo il passo induttivo di base. Tutti i nodi ad altezza h=0 sono foglie. In uno heap le foglie si trovano ai livelli D e D-1. Sia x il numero di nodi al livello più profondo, allora n-x è sicuramente dispari, dato che lo heap è un albero binario completo almeno fino al penultimo livello. Se n-x è dispari, ci possiamo trovare in due situazioni distinte:

  1. n è dispari se x è pari
  2. n è pari se x è dispari

Caso 1: se x è pari, allora tutti i nodi dello heap hanno o 0 2 figli e quindi lo heap è un albero binario per cui vale la proprietà secondo la quale il numero di nodi interni è pari al numero delle foglie diminuito di uno. Detto n il numero di nodi dello heap, HI il numero di nodi interni e HL il numero di foglie, si ha che n=HI+HL=HL+HL-1=2\cdot-1, da cui otteniamo che HL=\frac{n+1}{2}=\left \lceil \frac{n}{2} \right \rceil dato che n è dispari.

Caso 2: se x è dispari, allora n è pari. In questo caso possiamo aggiungere una foglia allo heap, facendolo diventare un albero binario per cui vale la relazione di cui prima. Come nel caso precedente avremo che n=HL+HI=2\cdot HL-1 e quindi HL= \left \lceil \frac{n+1}{2} \right \rceil=\left \lceil \frac{n}{2} \right \rceil+1, dato che n è pari. Quindi il numero di nodi ad altezza 0 senza l’aggiunta della foglia è \left \lceil \frac{n}{2} \right \rceil.

In questo modo abbiamo dimostrato che vale il caso base per h=0.

Per ipotesi induttiva, supponiamo che la proprietà che vogliamo dimostrare valga per ogni livello dello heap H tra 0 e h-1.

Dimostriamo il passo induttivo.

Sia n_{h} il numero di nodi ad altezza h; sia H^{'} l’albero ottenuto rimuovendo da H le foglie e sia n^{'} il numero di nodi di H^{'}, avremo che n^{'}=n-n_{0}=n-\left \lceil \frac{n}{2} \right \rceil=\left \lfloor \frac{n}{2} \right \rfloor.

Osservando che n_{h}=n_{h-1}^{'}, \forall h>0, possiamo concludere che:

n_{h}=n_{h-1}^{'}\leq \left \lceil \frac{n^{'}}{2^{h}} \right \rceil=\left \lceil \left \lfloor \frac{n}{2} \right \rfloor /2^{h}\right \rceil \leq \left \lceil \frac{n}{2}/2^{h} \right \rceil =

\left \lceil \frac{n}{2^{h+1}} \right \rceil

Costo di heap_heapify

Il costo di heap_heapify O(h) per un nodo di altezza h.

Per l’analisi del caso peggiore consideriamo uno heap con n nodi e altezza h avente l’ultima riga completa per metà; sia n_{s} il numero di nodi nel sottoalbero sinistro e n_{d} il numero di nodi nel sottoalbero destro, avremo che n=1+n_{s}+n_{d}, dove n_{s}=2^{h}-1 e n_{d}=2^{h-1}-1. Dato che n_{d}=(n_{s}+1)/2-1, avremo che n=1+n_{s}+n_{d}=\frac{3}{2}n+\frac{1}{2}, da cui risulta che n_{s}=\frac{2}{3}n-\frac{1}{3} \leq \frac{2}{3}n.

Il costo di heap_heapify è dato dal costo necessario a ripristinare l’ordinamento tra il nodo i e i suoi figli, che è \Theta(1), più il costo della chiamata ricorsiva su un figlio di i. Dato che nel caso peggiore in un sottoalbero di i ci sono al più \frac{2}{3}n nodi, la relazione di ricorrenza è

T(n)\leq T \left(\frac{2}{3}n \right ) + \Theta(1)

Per il caso 2 del Teorema Master, T_{heapheapify}(n)=\Theta(\log n).

Costo di heap_build

Per ottenere il costo della heap_build occorre sommare il prodotto tra il costo della heap_heapify per ogni nodo ad altezza h (che sappiamo esser O(h)) e il numero di nodi presenti al livello h dello heap per il numero totale dei livelli dello heap.

Usando le proprietà precedentemente enunciate possiamo esprimere la sommatoria che determina il costo computazionale della heap_build:

T_{heapbuild}=\sum_{h=0}^{\left \lfloor \log n \right \rfloor} \left \lceil \frac{n}{2^{h+1}} \right \rceil O(h) =

O \left ( \sum_{h=0}^{\left \lfloor \log n \right \rfloor} \left \lceil \frac{n}{2^{h+1}} \right \rceil h\right) =

O\left (n \sum_{h=0}^{\left \lfloor \log n \right \rfloor} \frac{h}{2^{h}} \right ) =

O(2n)=O(n)

Il precedente risultato è stato ottenuto usando la seguente sommatoria:

\sum_{k=0}^{\infty}kx^{k}=\frac{x}{(1-x)^{2}}

con x=\frac{1}{2}

 

Dopo questi 4 conticini (:D!!), possiamo esprimere il costo di heap_sort:

T_{heapsort}(n)=T_{heapsuild}(n)+(n-1)\cdot T_{heapheapify}(n) =

O(n) + (n-1)O(\log n) =O(n \log n)

Annunci

Commenti»

1. Gnappo - 18 gennaio 2008

Come faccio per esempio a dimostrare che nel caso peggiore di Heapify su un heap di dimensione n è Teta (lg n)?

2. fripp - 18 gennaio 2008

Mi sembra che l’abbia scritto nella sezione del post intitolata “Costo di heap_heapify”. Per calcolare la formula di ricorrenza, parto dal presupposto che lo heap abbia l’ultimo livello completo per metà. Questo particolare caso è proprio il caso peggiore: ho il massimo sbilanciamento possibile per lo heap. Se segui tutti i passaggi, vedi come da queste considerazioni io calcoli la relazione di ricorrenza. Dalla relazione di ricorrenza, applicando il caso 2 del teorema Master, ottengo che il costo della heap_heapify nel caso peggiore è Theta(log n)

3. Gnappo - 18 gennaio 2008

Praticamente se ho capito bene bisogna dimostrtare che lg n >= c * lg n ? Quindi verificandola facilmente per c = 1 ? Tnx

4. fripp - 18 gennaio 2008

Non è proprio così………
Se hai la relazione di ricorrenza T(n)<=T(2/3n)+ Theta(1) e vuoi ottenere il costo asintotico, puoi usare diversi strumenti matematici. Nel nostro caso, mi sono affidato al Teorema fondamentale delle ricorrenza o teorema Master, di cui trovi l’enunciato sulla wiki (http://it.wikipedia.org/wiki/Master_theorem). Il teorema Master ti permette di trovare la soluzione senza dover fare tutta una serie di passaggi matematici spesso poco agevoli o complessi.

5. Gnappo - 18 gennaio 2008

Sorry… dovrei dimostrare che è Omega (lg n) 😦

6. fripp - 18 gennaio 2008

Per dimostrare che T(n)=Theta(log n) devi dimostrare che contemporaneamente T(n)=O(log n) e T(n)=Omega(log n)

7. Lune - 21 gennaio 2008

ahhhh mi perdoni vero se dopo la terza riga ho deciso che questo post non fa per me?
🙂

8. fripp - 21 gennaio 2008

Solo alla terza riga?

9. ajkain - 23 gennaio 2008

scusa una curiosità OT,
come fai a scrivere le formule?

10. fripp - 23 gennaio 2008

@ajkain: per scrivere le formule utilizzo LaTeX http://it.wikipedia.org/wiki/LaTeX. WordPress.com supporta i plugin per formule matematiche di LaTeX.
Trovi maggiori info qui: http://faq.wordpress.com/2007/02/18/can-i-put-math-or-equations-in-my-posts/

11. ajkain - 24 gennaio 2008

@fripp: grazie! mi documento studio i link

12. fripp - 24 gennaio 2008

@ajkain: di nulla


Rispondi

Inserisci i tuoi dati qui sotto o clicca su un'icona per effettuare l'accesso:

Logo WordPress.com

Stai commentando usando il tuo account WordPress.com. Chiudi sessione / Modifica )

Foto Twitter

Stai commentando usando il tuo account Twitter. Chiudi sessione / Modifica )

Foto di Facebook

Stai commentando usando il tuo account Facebook. Chiudi sessione / Modifica )

Google+ photo

Stai commentando usando il tuo account Google+. Chiudi sessione / Modifica )

Connessione a %s...

%d blogger hanno fatto clic su Mi Piace per questo: