Anziché rappresentare il lavoro prepagato come credito memorizzato su specifici oggetti nella struttura dati, il metodo del potenziale rappresenta il lavoro prepagato come una sorta di “energia potenziale” che può essere liberata per pagare operazioni future.
Il potenziale è associato alla struttura dati nella sua interezza, anzichè a specifici oggetti.
Definiamo:
una generica struttura dati iniziali, su cui vengono eseguite operazioni; la Funzione Potenziale, che associa ciascuna struttura dati a un numero reale , che è il potenziale della struttura dati ; - Il costo ammortizzato
della i-esima operazione rispetto alla funzione potenziale è:
- In altre parole, il suo costo effettivo più la variazione di potenziale scaturita dall’operazione.
- Il costo ammortizzato totale è dato da una serie telescopica:
La scelta della funzione potenziale sta a noi, è di fatto arbitraria, a una condizione: la somma dei costi ammortizzati deve sempre essere maggiore della somma dei costi reali.
Difatti, se definiamo una funzione potenziale tale che
Nella pratica, non sappiamo quante operazioni potrebbero essere eseguite, quindi questo upper bound è necessario per avere la garanzia che paghiamo in anticipo.
Se imponiamo che
Intuitivamente, se
Negli esercizi, risulta utile porre
\phi(D_{0})=0, e poi dimostrare che\phi(D_{i})\geq 0
Info
Funzioni potenziali diverse possono produrre costi ammortizzati diversi, che sono comunque limiti superiori per i costi effettivi. Spesso la funzione potenziale scelta è il risultato di qualche compromesso.
Lemma:
Nota Bene: anche se vale questo lemma, non ci è garantito un buon tempo di esecuzione.
La difficoltà sta nell’inventare o trovare una funzione potenziale adatta, ma poi il resto dei calcoli risulta semplificato rispetto agli altri due metodi trattati.
Esempi: