Limitazione del grado massimo

Affinchè il costo ammortizzato della fuzione DECREASE-KEY e DELETE sia realmente $O(\log n)$, dobbiamo dimostrare che il limite superiore al grado di un qualsiasi nodo di uno Heap di Fibonacci è $O(\log n)$.

Chiameremo x$\to$size il numero di nodi dell'albero radicato in x (compreso x stesso). La dimostrazione mostra anche come x$\to$size è esponenziale a x$\to$grado.

Lemma 1   Sia $x$ un nodo di un qualsiasi Heap di Fibonacci tale che abbia (x$\to$grado)=k. Siano $y_1,y_2\dots,y_k$ i suoi figli ordinati in base al loro ordine di arrivo. Allora vale che ($y_1\to$grado$)\geq 0$ e ($y_i\to$grado$)\geq i-2$ per i = 2,3,$\dots$k.

Dimostrazione: per dire che ($y_1\to$grado$)\geq 0$ non serve dimostrazione; dato $i\geq2$ si nota che quando $y_i$ è diventato figlio di $x$, $x$ aveva i figli $y_1,y_2\dots,y_{i-1}$ e quindi ($x\to$grado$)\geq i-1$; poichè $y_i$ può essere stato aggiunto solo se aveva grado uguale a $x$, in quel momento si aveva ($y_i\to$grado$)\geq i-1$. Da quell'istante $y_i$ a perso al più un figlio perchè altrimenti sarebbe stato tagliato (vedi sottosezione 2.8 ed in particolare la funzione taglio-a-cascata). Ne consegue che ($y_i\to$grado $)\geq i-2. \qquad\Box$

Con quello che stiamo per vedere si capisce finalmente perchè questo tipo di struttura si chiami ``Heap di Fibonacci''. Come tutti sanno l' $i$-esimo numero di Fibonacci è:

$$F_i= \left\{\begin{array}{ll} 0 & \textrm{se } i = 0\\ 1... ..._{i-1}+F_{i-2} & \textrm{se } i\geq 2\\ \end{array}\right.$$

Il seguente lemma dimostra che $F_i$ può essere espresso in un'altro modo:

Lemma 2   per tutti gli $i\geq 0$ si possono esprimere i numeri di Fibonacci come segue:

$$F_{i+2} = 1 + \sum_{j=0}^{i} F_j$$

Dimostrazione: Per induzione su $i$:
Per $i = 0$

$$1 + \sum_{j=0}^{0} F_j = 1 + F_0 = 1 + 0 = 1 = F_2$$

Data l'ipotesi induttiva $\quad F_{i+1} = 1 + \sum_{j=0}^{i-1} F_j \quad$, si ha:

$$F_{i+2} = F_i + F_{i+1} = F_i + (1 + \sum_{j=0}^{i-1} F_j) = 1 + \sum_{j=0}^{i} F_j \qquad\Box$$

Indichiamo con $\phi$ il cosiddetto rapporto aureo definito come

$$\phi = (1+\sqrt{5})/2 = 1.61803\dots$$

Il Lemma 4 che termina la dimostrazione utilizza il seguente Lemma 3.

Lemma 3        $F_{i+2}\geq\phi^i$

Dimostrazione(per induzione su $i$):
Caso Base:
Semplice verifica per $i = 0$ e $i=1$
Passo Induttivo:
per ipotesi

$F_{i+2}=F_{i+1}+F_i \geq \phi^{i-1}+\phi^{i-2} =\phi^{i-2} \cdotp (\phi + 1)$

basta quindi dimostrare che

$\phi^{i-2} \cdotp (\phi + 1) \geq \phi^i$

cioè che

$\phi + 1 \geq \phi^2$

ed infatti sostituendo il valore di $\Phi$ si verifica che

$(3+\sqrt{5})/2 = (6+2\sqrt{5})/4$ $\qquad\Box$

Lemma 4   sia $x$ un nodo di uno Heap di Fibonacci e $k=x\to grado$. Allora vale che $(x\to size) \geq F_{k+2} \geq \phi^k$ dove $\phi = (1+\sqrt{5})/2$.

Dimostrazione: Definiamo $s_k$ il minimo valore possibile di $z\to size$ tra i nodi $z$ t.c. $z\to grado = k$. Chiaramente si ha che $s_0=1, s_1=2$ e $s_2=3$.
Dato un nodo $x$, siano $y_1,y_2\dots,y_k$ i suoi figli ordinati in base al loro ordine di arrivo. Troviamo ora un limite inferiore su $s\to size$: sommiamo $1$ per $x$ stesso, $1$ per il primo figlio $y_1$ e poi applichiamo via via il Lemma 1 per gli altri figli. Si ha quindi:

$$x\to size \geq s_k \geq 2+ \sum_{i=2}^k s_{i-2}$$

Resta ora da dimostrare per induzione su $k$ che $s_k \geq F_{k+2}$. I casi di base (per $k=0$ e $k=1$) sono di verifica immediata.
Con $k\geq 2$ si prenda come ipotesi induttiva che $s_i\geq F_{i+2}$ per $i=0,1,2,\dots, k$.
Abbiamo quindi:

$$s_k \geq 2 + \sum_{i=2}^k s_{i-2}\\ \geq 2 + \sum_{i=2}^k... ...=1}^k F_i\\ = 1 + \sum_{i=0}^k F_i\\ = F_{k+2} \qquad\Box$$

Abbiamo quindi dimostrato che:

$$x\to size \geq s_k \geq F_{k+2} \geq\phi^k$$

dove l'ultima disuguaglianza è data dal Lemma 3.
Con il Corollario 5 termina la parte relativa alla limitazione del grado massimo.

Corollario 5   Il grado massimo $D(n)$ di un nodo di uno Heap di Fibonacci composto da $n$ nodi é $O(\log n)$.

Dimostrazione: Sia $x$ un nodo di heap di Fibonacci composto da $n$ nodi e sia
$x\to size = k$. Possiamo dire che $n\geq x\to size \geq \phi^k$ dato il Lemma 3. Utilizzando $\log_\phi$ si ottiene $\log_\phi n \geq \log_\phi \phi^k$, cioè $k\leq \log_\phi n$. Il grado massimo (quello che noi avevamo chiamato $D(n)$) di un qualunque nodo di uno heap di Fibonacci è dunque $O(\log n).\qquad\Box$