Problemi con complessità heap:

[Darèios89]

Trovo in un testo che l' equazione di ricorrenza di questo algoritmo:

Max_Heapify(A,j,n)
k=j
if 2j+1 ≤ n and A[2j+1] > A[k]
then k=2j+1
if 2j ≤ n and A[2j] > A[k]
then k=2j
if k ≠ j
then t=A[j], A[j]=A[k], A[k]=t
Max_Heapify(A,k,n)

è: [tex]T(k)=T(2k/3)+\theta(1)[/tex]

Perchè?

Nel testo dice che la dimensione dei sottoalberi di ogni figlio non può superare 2k/3, ma perchè?

Mi sapreste dimostrare perchè il numero massimo di nodi ad altezza h in un albero binario è:

[tex]\left \lceil n/2^{h+1} \right \rceil[/tex]?

Per me è: [tex]n=2^{h+1}-1[/tex]

Non so come arrivi a quella formula.

[hamming_burst]

Ciao,

Per capirla ciò messo un po' non l'avevo mai vista questa limitazione

allora, la proprietà che citi cioè: "la dimensione dei sottoalberi dei figli hanno ciascuno dimensione al più $2k/3$"
è dovuta al fatto che gli alberi binari B (o heap binari) sono degli alberi completi e dalla loro proprietà dell'accatastamento a sinistra al livello $h$.

ma ti linko un post: http://radheshg.wordpress.com/2010/10/2 ... -n-is-2n3/
te lo spiega meglio in poche righe, di come possa spiegartelo io.
Se hai dubbi chiedi pure, perchè sono arrivato ad una conclusione simile


per il secondo problema, prova a limitare $h$ a $log_2(n)$ e sostituire, vedrai che il tuo dubbio non è lontano dalla tua formuala, sono equivalenti.

[Darèios89]

Scusa se rispondo ora, ma purtroppo studio algoritmi una volta alla settimana

Non ho guardato bene ancora il link da te suggerito, quanto al secondo problema effettuando la sostituzione non so cosa fare:

[tex]n=2^{\log_2{n+1}}-1[/tex]

Ma....come arrivo a [tex]n/2^{h+1}[/tex]