Complejidad amortizada
En resumen: La complejidad amortizada es el costo promedio de una operación en una secuencia larga: añadir a un array dinámico a veces copia todo, pero como el array crece por un factor (por ejemplo ×2), es O(1) en promedio.
Problema
La importación que copia todo
La tienda importa los pedidos de un sistema antiguo, uno por uno. Alguien escribió la importación de modo que con cada pedido el array se hace un lugar más grande:
function importOrders(n) { let orders = []; let copies = 0; for (let i = 0; i < n; i++) { copies += orders.length; orders = [...orders, 100000 + i]; } return copies;}Parece inofensivo: una línea por pedido. Pero cada array nuevo es una copia del anterior más un lugar. El programa cuenta las copias:
for (const n of [1000, 10000]) { console.log(`${n} pedidos: ${importOrders(n)} copias`);}1000 pedidos: 499500 copias10000 pedidos: 49995000 copiasCon 10 veces más pedidos hay 100 veces más copias. Con 100 000 pedidos son 4 999 950 000, y la importación, que en la prueba dura un instante, ahora tarda minutos. Sin embargo, push con los mismos 100 000 pedidos termina de inmediato, aunque también a veces copia todo el array. ¿Cómo?
La idea
La lista no crece un lugar a la vez
Por dentro, una lista es un array con más lugares que elementos. Cuando se llena, crea un array nuevo, más grande, y copia todo en él:
const cart = ["Pan", "Leche", "Café"];cart.push("Mantequilla");cart.splice(cart.indexOf("Leche"), 1);console.log(cart);console.log(`Productos: ${cart.length}`);Paso a paso, en palabras
- cart apunta a un array. Por dentro tiene length y un array aparte, elements, con 3 lugares.
- Los productos del código llenan los lugares uno a uno. El array está lleno: 3 de 3.
- No hay sitio. push crea un array con 22 lugares y copia en él los elementos.
- Ahora elements apunta al array nuevo, y el viejo ya no lo necesita nadie. «Mantequilla» va al lugar libre.
- splice quita «Leche», y todo lo que viene después se mueve un lugar a la izquierda. No queda ningún hueco.
- Desde fuera solo ves un array de tres productos. El motor V8 decide cuántos lugares tiene por dentro: el lenguaje no lo promete.
El secreto es cuánto más grande es el array nuevo. Si tiene un lugar más, cada adición después de que el array se llene copia todo, como en la importación de arriba. Si es el doble de grande, la siguiente copia llega solo después de otras tantas adiciones.
Míralo
Tu propio array que se duplica
Aquí está el mismo mecanismo escrito a mano, con un contador de copias. El array empieza con un lugar:
class OrderList { constructor() { this.items = new Array(1); this.size = 0; this.copies = 0; }
add(order) { if (this.size === this.items.length) { const bigger = new Array(this.items.length * 2); for (let i = 0; i < this.size; i++) { bigger[i] = this.items[i]; this.copies++; } this.items = bigger; } this.items[this.size] = order; this.size++; }}for (const n of [9, 1000]) { const orders = new OrderList(); for (let i = 0; i < n; i++) { orders.add(100000 + i); } console.log(`${n} pedidos: ${orders.copies} copias, 2n = ${2 * n}`);}9 pedidos: 15 copias, 2n = 181000 pedidos: 1023 copias, 2n = 2000class OrderList { constructor() { this.items = new Array(1); this.size = 0; this.copies = 0; }
add(order) { if (this.size === this.items.length) { const bigger = new Array(this.items.length * 2); for (let i = 0; i < this.size; i++) { bigger[i] = this.items[i]; this.copies++; } this.items = bigger; } this.items[this.size] = order; this.size++; }}
const orders = new OrderList();for (let i = 0; i < 9; i++) { orders.add(100000 + i);}Paso a paso, en palabras
- El array empieza con un lugar y size es 0. Contamos solo las copias de elementos antiguos.
- El primer pedido: hay espacio, add lo escribe. Copias: 0.
- El segundo: el array está lleno. Un array nuevo con 2 lugares, y el pedido antiguo se copia en él: 1 copia.
- El tercero: otra vez lleno, 4 lugares y 2 copias. El cuarto entra sin copiar.
- El quinto copia 4, el noveno 8. Las copias crecen, pero entre ellas llegan cada vez más adiciones sin copiar.
- 9 adiciones, 1 + 2 + 4 + 8 = 15 copias, menos de 2n = 18. Repartidas entre todas las adiciones, son menos de 2 por adición: O(1) amortizado.
Una adición que encuentra el array lleno copia todo: 1, 2, 4, 8, 16 … Pero después vienen tantas adiciones sin copiar como copió ella. La suma 1 + 2 + 4 + … + 2ᵏ es siempre menor que 2 · 2ᵏ, y la última copia 2ᵏ es menor que n. Así que las copias son menos de 2n, por grande que sea n.
La idea
Complejidad amortizada
Una adición puede costar O(n): la que copia todo. Pero n adiciones cuestan menos de 3n operaciones en total: n escrituras y menos de 2n copias. Dividido entre n, son menos de 3 por adición: O(1).
El costo repartido entre una secuencia entera de operaciones se llama complejidad amortizada. Añadir al final de una lista es O(1) amortizado.
Esto no es «en promedio para una entrada aleatoria». La promesa vale para cualquier secuencia de adiciones, sin suerte: las caras son raras, y siempre igual de raras.
Pruébalo
Predice la salida
Cinco pedidos en un array que empieza con un lugar y se duplica. ¿Cuántas copias?
class OrderList { constructor() { this.items = new Array(1); this.size = 0; this.copies = 0; }
add(order) { if (this.size === this.items.length) { const bigger = new Array(this.items.length * 2); for (let i = 0; i < this.size; i++) { bigger[i] = this.items[i]; this.copies++; } this.items = bigger; } this.items[this.size] = order; this.size++; }}
for (const n of [5]) { const orders = new OrderList(); for (let i = 0; i < n; i++) { orders.add(100000 + i); } console.log(`${n} pedidos: ${orders.copies} copias`);}Míralo
Un lugar más: O(n²)
La misma clase, solo que el array nuevo tiene un lugar más:
const bigger = new Array(this.items.length + 1);for (const n of [9, 1000]) { const orders = new OrderList(); for (let i = 0; i < n; i++) { orders.add(100000 + i); } console.log(`${n} pedidos: ${orders.copies} copias`);}9 pedidos: 36 copias1000 pedidos: 499500 copiasCon 1000 pedidos, la duplicación copia 1023 veces y el crecimiento de un lugar, 499 500 veces: 1 + 2 + … + 999. Ejecuta los dos crecimientos y mira las curvas. Contamos solo las copias:
- Crecimiento ×2: copias
O(n) - Crecimiento +1: copias
O(n²)
| Algoritmo | n = 10 | n = 1000 | n = 100.000 |
|---|---|---|---|
| Crecimiento ×2: copias | 15 | 1023 | 131.071 |
| Crecimiento +1: copias | 45 | 499.500 | ≈ 4.995.000.000 |
La duplicación crece como una recta: O(n) en total, O(1) por adición. El crecimiento de un lugar crece como una parábola: O(n²) en total, O(n) por adición.
Pruébalo
Completa
¿Cuántos lugares tiene el array nuevo para que añadir sea O(1) amortizado?
if (this.size === this.items.length) {
const bigger = new Array();El array nuevo es el doble de grande que el viejo. Así, el siguiente crecimiento llega solo después de otras tantas adiciones como elementos hay ahora.
Pruébalo
Encuentra el error
Un colega reemplazó la duplicación «para no desperdiciar memoria». Con 1000 pedidos la prueba pasa rápido, y la importación nocturna de 100 000 se arrastra:
for (const n of [1000, 100000]) { const orders = new OrderList(); for (let i = 0; i < n; i++) { orders.add(100000 + i); } console.log(`${n} pedidos: ${orders.copies} copias`);}1000 pedidos: 4510 copias100000 pedidos: 49951000 copiasCon 100 veces más pedidos hay 10 000 veces más copias. ¿En qué línea está el error?
Elige la línea con el error.
El array crece de 100 en 100 lugares. Eso aplaza el crecimiento, pero no lo hace raro: cada 100 adiciones llega una copia de todo lo anterior, y la suma sigue siendo cuadrática, unas n²/200. El crecimiento debe ser una multiplicación (×2, ×1,5), no una suma, por grande que sea el número que se suma.
La idea
Cómo crece cada lenguaje
Ningún lenguaje duplica exactamente, pero todos multiplican:
-
Java
ArrayList: ×1,5; -
C#
List<T>: ×2; - Python (CPython): aproximadamente ×1,125;
- JavaScript (V8 en Node y Chrome): el tamaño nuevo es n + n/2 + 16, aproximadamente ×1,5. El lenguaje no lo promete; lo decide el motor.
Cualquier factor mayor que 1 da O(1) amortizado. Cuanto menor es, más copias (menos de 3n con ×1,5, menos de 9n con ×1,125) y menos lugares vacíos después de un crecimiento. La elección es un intercambio entre tiempo y memoria, como en la lección «Complejidad en espacio».
Más precisamente, para curiosos
O(1) amortizado no significa que cada adición sea rápida. La adición que copia es O(n). En la mayoría de los programas no lo notas, pero en un programa que no puede detenerse (una caja, un juego, procesamiento de audio), la adición del elemento un millón puede ser la lenta. Si sabes cuántos elementos habrá, fija los lugares de antemano: new Array(n). Así la lista nunca copia.
new Array(n) crea un array con huecos, que V8 guarda más lento que uno denso. Normalmente push es la mejor opción, y no se crean huecos.La cota para ×2 tiene también otra forma: cada adición «paga» 2 copias por adelantado y las ahorra. Cuando el array con k elementos se llena, las últimas k/2 adiciones han ahorrado k, justo lo que cuesta la copia. Lo ahorrado nunca es negativo, así que la suma queda por debajo de 2n.
Ejercicio
Crecimiento como en Java
Resuelve la tarea en tu editor.
Crecimiento a la mitad. Cambia el crecimiento de OrderList para que el array nuevo tenga los lugares viejos más la mitad (al menos un lugar más). Cuenta las copias con 1000 y con 100 000 pedidos. ¿Son menos de 2n? ¿Y menos de 3n?
1000 pedidos: 2137 copias, 2n = 2000100000 pedidos: 276521 copias, 2n = 200000Más tareas
- Quitar del final. Añade
removeLast. ¿Cuándo debe encogerse el array para que quitar también sea O(1) amortizado? Prueba «a la mitad, cuando está medio lleno» y alterna añadir y quitar justo en el límite. Después prueba «a la mitad, cuando está lleno a un cuarto». ¿Por qué el segundo es O(1) amortizado y el primero no? - Cuántos lugares desperdicia. Después de 1000 adiciones con duplicación, ¿cuántos lugares están vacíos? ¿Y con crecimiento ×1,5?
Test