Data Structure & Algorithms
Análisis amortizado de secuencias, trade-offs entre tiempo y memoria, latencia, preprocesamiento y diseño de benchmarks representativos.
El peor costo de una operación individual no siempre representa el costo de una secuencia. El análisis amortizado distribuye operaciones ocasionalmente caras entre muchas operaciones baratas y ofrece una garantía para cualquier secuencia válida, sin asumir una distribución probabilística.
También debes evaluar trade-offs: reducir tiempo puede exigir memoria, preprocesamiento, complejidad de código o garantías más débiles.
Los benchmarks miden una implementación concreta; el análisis asintótico explica cómo escala una familia de entradas. Se complementan, no se sustituyen.
Un array dinámico puede tener push amortizado O(1) aunque una expansión particular cueste O(n).
Suma el costo de m operaciones y divide por m.
Si la capacidad se duplica:
capacity: 1 → 2 → 4 → 8 → ...
copy: 1 + 2 + 4 + ... < 2mAdemás de las m escrituras normales, se copian menos de 2m elementos.
costo total O(m)
costo amortizado O(1) por pushEsto no dice que cada push sea constante. Dice que cualquier secuencia de m pushes cuesta lineal en total.
Asigna un costo ficticio mayor a operaciones baratas y guarda crédito para pagar una futura operación cara.
Ejemplo conceptual:
La cuenta nunca debe quedar negativa. Si puedes demostrarlo, el costo cobrado es una cota amortizada.
Define una función Φ(state) que representa trabajo almacenado.
costo amortizado
a_i = costo real c_i + Φ(state_i) - Φ(state_(i-1))Al sumar una secuencia, los potenciales intermedios se cancelan. Si Φ es no negativa y comienza controlada, la suma amortizada acota el costo real.
Es útil para estructuras con un estado más complejo que simples expansiones.
Operaciones:
push: añade un elemento;pop: retira uno;multipop(k): retira hasta k.Una llamada a multipop puede costar O(n), pero cada elemento solo puede salir una vez después de entrar.
Para m operaciones, la cantidad total de pops no supera la cantidad total de pushes. Costo total O(m) y amortizado O(1).
Un elemento entra una vez y sale como máximo una vez. Aunque exista un while anidado, el total de pops es O(n).
Este razonamiento “cada elemento paga una vez” aparece en:
Una hash table puede duplicar buckets y reinsertar n entradas en O(n). Si crece geométricamente, el trabajo total de todos los rehashes durante n inserciones es O(n).
El lookup sigue siendo promedio, no garantizado, por las colisiones. Son dos análisis distintos:
O(n) tiempo, O(1) memoria.O(n) preprocesamiento y memoria, lookup promedio O(1).Conviene indexar cuando el número de consultas compensa el costo inicial y la memoria.
O(n).O(n), consulta O(1), memoria O(n).No existe una optimización gratuita. Especifica qué recurso intercambias.
Supón:
q · n;n + q promedio.Con una consulta pequeña, construir el índice puede ser innecesario. Con muchas, domina el ahorro.
La decisión también depende de actualizaciones. Un índice estático puede requerir reconstrucción; una estructura dinámica añade costos de mantenimiento.
Una operación amortizada O(1) puede tener picos O(n). Para una aplicación interactiva o de tiempo real, el throughput total puede ser bueno y aun así la latencia máxima ser inaceptable.
Opciones:
Big O amortizado no responde por sí solo requisitos de latencia.
No sumes toda memoria creada a lo largo del tiempo si se libera antes de crear la siguiente. La complejidad espacial suele medir el máximo simultáneo.
En recursión:
En merge sort, buffers por niveles pueden reutilizarse. Una implementación con slices crea más asignaciones totales, pero el pico debe analizarse según qué referencias siguen vivas.
Un benchmark responde:
¿Cuánto tarda esta implementación, en este runtime, hardware, dataset y configuración?
No responde automáticamente:
n.JavaScript puede interpretar, compilar y optimizar funciones durante la ejecución. Las primeras iteraciones pueden incluir costos que después cambian.
Un benchmark corto puede medir warm-up más que el algoritmo. También puede provocar deoptimization si los tipos cambian.
No “calientes” ocultando un comportamiento real de una función que solo se ejecutará una vez. El benchmark debe modelar el uso.
Date.now() alrededor de una operación demasiado pequeña;n = 100 sobre n = 10^7.Dos algoritmos O(n) pueden diferir por:
Un array suele superar una linked list en recorridos por localidad, aunque ambos sean O(n).
Big O oculta constantes deliberadamente; el benchmark las muestra para un contexto.
Un algoritmo con mejor complejidad puede ser más lento en entradas pequeñas.
insertion sort O(n²) con bajo overhead
merge sort O(n log n) con buffers y recursiónPor eso sorts híbridos usan insertion sort en segmentos pequeños.
El punto de cruce se mide, no se deriva solo de Big O.
Un benchmark promedio puede ocultar:
Incluye casos que desafíen la garantía que te importa.
Evalúa:
correctitud
→ restricciones de n
→ operaciones dominantes
→ tiempo esperado y peor caso
→ memoria y pico
→ mutación y estabilidad
→ complejidad de implementación
→ medición representativaUna solución teóricamente óptima puede no ser la mejor si es difícil de mantener, si la entrada es pequeña o si una librería ofrece una implementación probada.
O(1).¿Por qué un push amortizado O(1) todavía puede ser problemático en un sistema con límites estrictos de latencia?
Porque una operación concreta puede disparar una expansión y copiar n elementos. El costo total de muchas operaciones es bueno, pero el pico individual puede superar el límite de latencia.