Analisi della Complessità Ammortizzata

Prima di affrontare il discorso ``Heap di Fibonacci'' è fondamentale capire cosa sia l'analisi ammortizzata della complessità di un algoritmo.
Sostanzialmente, nell'analisi ammortizzata, per tempo di esecuzione di una sequenza di operazioni, si intende la media dei costi di tali operazioni. È però importante fare attenzione a non confondersi con l'analisi del costo medio in cui si fa riferimento a concetti di teoria della probabilità per valutare il costo di esecuzione sull'istanza media (lo spazio campionario è definito sull'insieme delle istanze).

Esistono diverse tecniche usate per l'analisi ammortizzata:

• Analisi aggregata:
  si determina un limite superiore del costo totale $T(n)$ di una sequenza di operazioni per poi ottenere il costo ammortizzato: $T(n)/n$ dove n è il numero di operazioni della sequenza.
• Metodo degli accantonamenti:
  consiste nel creare un ``debito'' inteso come differenza tra costo reale e costo attribuito all'operazione. Il debito viene poi saldato definendo più alto il costo attribuito a altre operazioni facendo attenzione a far quadrare il bilancio. Alla ``chiusura'' è ammesso un bilancio negativo, in modo tale che ogni debito sia stato pagato. Se questo vincolo è stato rispettato, resta legittimato il ragionamento in termini di costi attribuiti anzichè di costi reali.
• Metodo del potenziale:
  è una tecnica molto simile al Metodo degli accantonamenti in cui però il ``credito'' accumulato è direttamente associato alla struttura di dati e tale ``credito'' è visto come ``l'energia potenziale'' della struttura stessa. Utilizzeremo questa tecnica per una valutazione ammortizzata della complessità delle operazioni sui Fibonacci Heap. Pertanto nella sottosezione 1.1 spieghiamo la tecnica in maggior dettaglio illustrando un esempio che ne facilita la comprensione.