jump to navigation

Heapsort - costo computazionale 21 Gennaio 2008

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

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)
(more…)

“Il Bloggatore” 21 Gennaio 2008

Posted by fripp in Senza Categoria.
add a comment

Da oggi i post riguardanti l’informatica del mio blog saranno presenti sull’aggregatore di feed Il bloggatore.

Cliccate qui per maggiori informazioni su questo interessante progetto.