Reinventarlo

La condición

Una operación no siempre cuesta lo mismo. Agregar al final de un array que crece suele ser una escritura, pero a veces copia todo. Buscar en una tabla hash (una estructura que calcula dónde guardar cada clave; la verás en la unidad 4) suele mirar una casilla, pero con mala suerte mira muchas.

Por eso un costo se dice con su condición:

• peor caso: lo máximo que puede costar una operación;
• amortizado: la media en cualquier secuencia larga de operaciones, aunque alguna cueste mucho;
• esperado: la media según el azar (por ejemplo, de cómo reparte las claves una tabla hash).

En la figura, el costo de nueve inserciones al final de un array que crece: casi todas cuestan 1, y una cuesta 9.