Il tempo ammortizzato è il modo di esprimere la complessità temporale quando un algoritmo ha la complessità temporale pessima solo una volta ogni tanto oltre alla complessità temporale che si verifica la maggior parte delle volte. Un buon esempio potrebbe essere una ArrayList che è una struttura dati che contiene un array e può essere estesa. Un’altra definizione da Stack Overflow è il tempo medio impiegato per operazione, se si fanno molte operazioni.
Quando ArrayList colpisce la capacità dell’array in esso, allora crea un nuovo array con la dimensione raddoppiata del vecchio array e copia tutti gli elementi nel vecchio array nel nuovo array. In ArrayList, esistono due complessità temporali; una è O(1) e l’altra è O(n).
Quando l’array non ha raggiunto la sua capacità e ha ancora abbastanza spazio per inserire elementi
Per inserire un elemento nell’array in questo caso, dobbiamo solo mettere l’elemento dopo l’ultimo elemento. Abbiamo ancora spazio per inserire elementi.
Quando l’array ha raggiunto la sua capacità e deve ricrearsi con la dimensione raddoppiata
L’array ha raggiunto la capacità e non abbiamo slot disponibili. Allora abbiamo bisogno di creare una nuova matrice con la dimensione raddoppiata. E poi copiare gli elementi in quello vecchio in quello nuovo, il che richiede O(n) dove n è la capacità del vecchio array e il caso peggiore.
Per esprimere queste due complessità temporali, il tempo ammortizzato è qui. Ciò che fa è descrivere il caso peggiore che si verifica una volta ogni tanto ogni volta che l’array interno colpisce la sua capacità.
Ma una volta che accade, non accadrà più per così tanto tempo che il costo è “ammortizzato”. (Cracking the Coding Interview 6th edition 43)
Come descrivere le due complessità?
Nel caso dell’ArrayList, possiamo dire che
L’inserimento richiede O(n) quando la capacità è stata raggiunta, e il tempo ammortizzato per ogni inserimento è O(1).
Ma cerchiamo di essere precisi per la peggiore complessità temporale senza semplificare questo tempo. Se la capacità interna dell’array inizia con 1, allora le capacità saranno 1, 2, 4, 8, 16… X quando colpisce la capacità e viene raddoppiata. Ci vogliono 1, 2, 4, 8 16… X elementi per copiare nel nuovo array a seconda della capacità raggiunta. Quindi la complessità temporale sarà 1 + 2 + 4 + 8 + 16 +… X. Se si pensa da X, questo sarà X + X/2 + X/4 + X/8… + 1 = 2X circa. Quindi in altre parole con precisione,
L’inserimento richiede O(2X) quando la capacità di X è stata raggiunta, e il tempo ammortizzato per ogni inserimento è O(1).
