Un dynamic array duplica su capacidad cuando se llena. ¿Cuál es el coste amortizado de append?
Opciones
- O(n)
- O(log n)
- O(1) (Opción correcta)
- O(n²)
Respuesta
O(1)
Por qué
La mayoría de los append solo usan una posición libre: O(1). Cuando el array está lleno, reserva el doble de espacio y copia todo: O(n) para ese append.
Pero las copias ocurren solo en los tamaños 1, 2, 4, 8, ... y suman menos de 2n en n appends. Repartido entre todos los append, cada uno cuesta O(1).
Ese razonamiento de promediar entre muchas operaciones se llama análisis amortizado.
Recuerda
Pasos caros y raros repartidos entre muchos baratos = amortizado.