4. Ammortizzazione.md

---

Ammortizzazione

Il tempo di esecuzione ammortizzato di un’operazione all’interno di una serie di operazioni è il tempo di esecuzione nel caso pessimo diviso per il numero di operazioni.

Esempio Estensione Di Un Array

Ho un array di dimensione C, e voglio farlo arrivare a dimensione $N=kc, k \in Z$

Ogni volta che voglio ingrandire l’array ho due opzioni:

• ingrandisco di altre C dimensioni, copio la dimensione dell’array (1C, 2C,..ecc) e esegui C operazioni O(1) (strategia incrementale).
• raddoppio la dimensione dell'array, copio i suoi elementi (1C, 2C, 4C, 8C, ...) e eseguo le operazioni di aggiunta. (strategia del raddoppio)

Compariamo le due strategie analizzando il tempo totale T(n) impiegato per eseguire n operazioni di aggiunta.

Chiamiamo tempo ammortizzato di operazioni di aggiunta il tempo medio impiegato da un'operazione di aggiunta oltre le serie di operazioni.

Assumendo di iniziare con una lista vuota rappresentata da un array di dimensione 1.

Strategia Incrementale

Dopo n operazioni di aggiunta, rimpiazziamo l'array k= n/c volte, dove c è una costante.

Il tempo totale T(n) di una serie di n operazioni di aggiunta è proporzionale a

$$n+c+2c+3c+4c+...+kc=$$

$$n+c(1+2+3+4+...+k)=$$

$$n+\frac{ck(k+1)}2$$

Dato che c è una costante, T(n) è $O(n+k^2)$, ovvero $O(n^2)$, e il tempo di esecuzione ammortizzato è

$$\frac {O(n^2)}n=O(n)$$

Strategia Del Raddoppio

Rimpiazziamo l'array $k=\log_2(n)$ volte, il tempo totale T(n) di una serie di n operazioni è proporzionale a

$$n+1+2+4+8+...+2^k=$$

$$n+2^{k+1}-1=3n-1$$

T(n) è O(n).

Il tempo di esecuzione ammortizzato è O(1)