Metodo del Potenziale

Data una struttura dati e una sequenza di $n$ operazioni su di essa, si definisca come $D_{0}$ la struttura iniziale, per $D_{i}$ la struttura dati che si ottiene eseguendo l'$i$-esima operazione sulla struttura $D_{i-1}$. Per ogni $1 \leq i \leq n$, sia $c_{i}$ é il costo effettivo della $i$-esima operazione della sequenza. È possibile definire una funzione potenziale (o più semplicemente potenziale) $\Phi(D)$ che associa allo stato della struttura un numero reale detto appunto potenziale¹.
Il costo ammortizzato è cosí definito:

$$\hat{c_i} = c_i + \Phi(D_{i}) - \Phi(D_{i-1})$$

Il costo ammortizzato delle $n$ operazioni quindi sará:

$$\sum_{i=1}^n\hat{c_i} = \sum_{i=1}^n (c_i+\Phi(D_{i})-\Phi(D_{i-1}))$$

$$\qquad = \sum_{i=1}^n c_i+\Phi(D_{n})-\Phi(D_{0})$$

Per garantire che $\sum_{i=1}^n\hat{c_i}$ domini il costo effettivo totale deve valere che $\Phi(D_n)\geq\Phi(D_0)$ cioè che l'analisi della complessità è terminata con un ``credito'' anzichè con un ``debito''.
Non essendo sempre noto il numero di operazioni che potrebbero essere eseguite, è indispensabile garantire che $\Phi(D_i)\geq\Phi(D_0)$ per tutti i valori di $i$. Per semplicità spesso si definisce $\Phi(D_0)=0$ e basta poi dimostrare che $\Phi(D_i)\geq 0$ $\forall{i}$ per essere sicuri di avere ottenuto un limite superiore al costo effettivo totale.

• Esempio(Operazioni su pile): si consideri una pila con le operazioni Push, Pop e MultiPop e si definisca $\Phi$ come il numero di elementi presenti nella pila. Si osservi come $\Phi$ sia funzione del solo stato della struttura dati, ossia $\Phi$ è effettivamente una funzione potenziale. Nel caso iniziale la pila è vuota e si ha $\Phi(D_0)=0$; dopo un numero indefinito $i$ di operazioni il potenziale è $\Phi(D_0)\geq 0$. Questo fatto, come detto in precedenza, garantisce che il costo ammortizzato totale di n operazioni rispetto alla funzione potenziale $\Phi$ domini il costo effettivo delle operazioni stesse.
  Definiamo $e$ il numero di elementi presenti nella pila.
  Non resta che calcolare i costi ammortizzati delle varie operazioni:

  Push:

  se la $i$-esima operazione è una Push si ha:
  $c_i = 1;$
  $\Phi(D_{i})-\Phi(D_{i-1}) = e - (e-1) = 1$;
  Sostituendo in $\hat{c_i} = c_i+\Phi(D_{i})-\Phi(D_{i-1})$ si ha:
  $c_i = 1 + e - (e-1) = 2$;
  Il costo ammortizzato è costante.

  Pop:

  se la $i$-esima operazione è una Pop si ha:
  $c_i = 1;$
  $\Phi(D_{i})-\Phi(D_{i-1}) = e - (e+1) = -1$;
  Sostituendo in $\hat{c_i} = c_i+\Phi(D_{i})-\Phi(D_{i-1})$ si ha:
  $c_i = 1 + e - (e+1) = 0$;
  Il costo ammortizzato é costante.

  MultiPop:

  se la $i$-esima operazione è una MultiPop si ha:
  $c_i = t'$ dove $t'$ e` il numero di elementi tolti alla pila;
  $\Phi(D_i)-\Phi(D_{i-1}) = e - (e+t') = -t'$;
  Sostituendo in $\hat{c_i} = c_i+\Phi(D_i)-\Phi(D_{i-1})$ si ha:
  $c_i = t' + e - (e+t') = 0$;
  Il costo ammortizzato è costante.

  Il costo ammortizzato di tutte e tre le operazioni é $O(1)$, quindi il costo di una qualsiasi sequenza di $n$ operazioni é $O(n)$.