13 - Operaciones amortizadas (concepto introductorio)

Una operación amortizada estima el costo promedio de una secuencia completa en lugar de enfocarse en un caso aislado. Esta visión evita sobreestimar procedimientos que rara vez son costosos y permite justificar el diseño de estructuras que reorganizan sus datos de forma esporádica.

Al entender el análisis amortizado sabrás cómo dimensionar buffers, decidir estrategias de redimensionamiento y explicar por qué una operación aparentemente lenta sigue siendo eficiente en el largo plazo.

13. Operaciones amortizadas

Las siguientes subsecciones construyen la intuición necesaria para usar este concepto al evaluar contenedores dinámicos.

13.1 Qué significa amortizado

La complejidad amortizada distribuye el costo de una operación cara entre varias operaciones baratas subsecuentes, de modo que el promedio se mantenga bajo.

• Se analiza una secuencia de n operaciones y se calcula el costo total dividido entre n.
• El enfoque demuestra que, aunque algunas operaciones individuales sean lentas, la mayoría ejecuta en tiempo constante.
• Métodos comunes para demostrarlo: contabilidad (asignar créditos) y potencial (medir energía almacenada en la estructura).

13.2 Cómo se aplica a estructuras dinámicas

Las estructuras dinámicas incrementan su capacidad o reorganizan referencias de forma puntual. Ese evento costoso se financia con los ahorros de las inserciones previas.

• Arrays dinámicos: copian sus elementos a un bloque más grande cuando alcanzan la capacidad. El resto del tiempo solo escriben en la siguiente posición libre.
• Hash tables: ejecutan rehash cuando la carga supera un umbral, pero todas las inserciones intermedias son O(1).
• Estructuras persistentes: pueden compartir secciones y copiar solo nodos modificados, amortizando el costo de referencias adicionales.

13.3 Ejemplo conceptual: crecimiento de un ArrayList

El siguiente pseudocódigo ilustra una lista que duplica su capacidad cuando se llena:

class ArrayList:
  def __init__(self):
    self.capacidad = 2
    self.datos = [None] * self.capacidad
    self.longitud = 0

  def append(self, valor):
    if self.longitud == self.capacidad:
      self._redimensionar()
    self.datos[self.longitud] = valor
    self.longitud += 1

  def _redimensionar(self):
    self.capacidad *= 2
    nuevo = [None] * self.capacidad
    for i, valor in enumerate(self.datos):
      nuevo[i] = valor
    self.datos = nuevo

Copiar n elementos durante la redimensionación cuesta O(n), pero ocurre infrecuentemente. Si ejecutas muchas operaciones append, el costo total se aproxima a 2n, resultando en un promedio O(1) por inserción.

13.4 Por qué importa para programar en el mundo real

Entender operaciones amortizadas evita elegir estructuras por percepciones erróneas y ayuda a negociar objetivos de rendimiento.

• Permite justificar diseños basados en heurísticas (p.ej., duplicar capacidad frente a incrementar en bloques fijos).
• Ayuda a definir alertas: cuando el amortizado deja de cumplirse (exceso de rehash o resize), es hora de revisar patrones de uso.
• Simplifica la comunicación con equipos de producto al explicar por qué un pico puntual no implica una regresión general.

Cuando documentas tus estructuras, incluye el costo amortizado para que otros desarrolladores sepan cómo escalará el sistema bajo cargas normales.