El tiempo amortizado es la forma de expresar la complejidad temporal cuando un algoritmo tiene la complejidad temporal muy mala sólo de vez en cuando además de la complejidad temporal que ocurre la mayor parte del tiempo. Un buen ejemplo sería un ArrayList que es una estructura de datos que contiene un array y puede ser extendido. Otra definición de Stack Overflow es el tiempo promedio que se toma por operación, si se hacen muchas operaciones.
Cuando ArrayList alcanza la capacidad del array en él, entonces crea un nuevo array con el tamaño duplicado del antiguo array y copia todos los elementos del antiguo array al nuevo array. En ArrayList, existen dos complejidades de tiempo; una es O(1) y la otra es O(n).
Cuando el array en él no ha alcanzado su capacidad y todavía tiene espacio suficiente para insertar elementos
Para insertar un elemento al array en este caso, sólo tenemos que poner el elemento después del último elemento. Todavía tenemos espacio para insertar elementos.
Cuando el array ha alcanzado su capacidad y necesita volver a crearse con el tamaño duplicado
El array ha alcanzado su capacidad y no tenemos ranuras disponibles. Entonces necesitamos crear un nuevo array con el tamaño duplicado. Y luego copiar los elementos de la antigua a la nueva, que toma O(n) donde n es la capacidad de la antigua matriz y el peor caso.
Para expresar estos dos complejidad de tiempo, el tiempo amortizado está aquí. Lo que hace es permitirnos describir que el peor caso ocurre de vez en cuando cada vez que el array interno alcanza su capacidad.
Pero una vez que ocurre, no volverá a ocurrir durante tanto tiempo que el coste está «amortizado». (Cracking the Coding Interview 6th edition 43)
Entonces, ¿cómo describimos las dos complejidades?
En el caso del ArrayList, podemos decir que
La inserción tarda O(n) cuando se ha alcanzado la capacidad, y el tiempo amortizado para cada inserción es O(1).
Pero seamos precisos para la peor complejidad temporal sin simplificar este tiempo. Si la capacidad del array interno comienza con 1, entonces las capacidades serán 1, 2, 4, 8, 16… X cuando llegue a la capacidad y se duplique. Se necesitan 1, 2, 4, 8 16… X elementos para copiar en el nuevo array dependiendo de la capacidad que se haya alcanzado. Así que la complejidad de tiempo será 1 + 2 + 4 + 8 + 16 +… X. Si piensas desde X, esto será X + X/2 + X/4 + X/8… + 1 = 2X aproximadamente. Así que en otras palabras con precisión,
La inserción toma O(2X) cuando se ha alcanzado la capacidad de X, y el tiempo amortizado para cada inserción es O(1).
