Heapsort - costo computazionale « frammenti di razionalità

Heapsort - costo computazionale 21 Gennaio 2008

Posted by Calogero in Algoritmi, Heapsort, Informatica, Matematica, Ordinamento.
Tags: Cormen, Heapsort, Leiserson, Master Theorem, math, Rivest, Stein
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:

$n$ è dispari se $x$ è pari
$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)$

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