Complejidad amortizada

Código en:JavaC#PythonJavaScript

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:

static long importOrders(int n) {
    int[] orders = new int[0];
    long copies = 0;
    for (int i = 0; i < n; i++) {
        copies += orders.length;
        orders = Arrays.copyOf(orders, orders.length + 1);
        orders[orders.length - 1] = 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 (int n : new int[] {1000, 10000}) {
    System.out.println(n + " pedidos: " + importOrders(n) + " copias");
}

Salida

1000 pedidos: 499500 copias
10000 pedidos: 49995000 copias

Con 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, ArrayList.add 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:

ArrayList<String> cart = new ArrayList<>(3);
cart.add("Pan");
cart.add("Leche");
cart.add("Café");
cart.add("Mantequilla");
cart.remove("Leche");
System.out.println(cart);
System.out.println("Productos: " + cart.size());

Paso a paso, en palabras

1. cart apunta a un objeto ArrayList. Dentro hay un array con 3 lugares y un contador size.
2. add pone cada elemento en el primer lugar libre y aumenta size.
3. El array está lleno. ArrayList crea uno nuevo con 4 lugares y copia en él los tres elementos.
4. Ahora el objeto apunta al array nuevo, y el viejo ya no lo necesita nadie. «Mantequilla» va al lugar libre.
5. remove quita «Leche», y todo lo que viene después se mueve un lugar a la izquierda. No queda ningún hueco.
6. Desde fuera solo ves una lista de tres productos: ArrayList se encarga de copiar y de mover.

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 {
    private int[] items = new int[1];
    private int size = 0;
    long copies = 0;

    void add(int order) {
        if (size == items.length) {
            int[] bigger = new int[items.length * 2];
            for (int i = 0; i < size; i++) {
                bigger[i] = items[i];
                copies++;
            }
            items = bigger;
        }
        items[size] = order;
        size++;
    }
}

for (int n : new int[] {9, 1000}) {
    OrderList orders = new OrderList();
    for (int i = 0; i < n; i++) {
        orders.add(100000 + i);
    }
    System.out.println(n + " pedidos: " + orders.copies + " copias" + ", 2n = " + 2 * n);
}

Salida

9 pedidos: 15 copias, 2n = 18
1000 pedidos: 1023 copias, 2n = 2000

class OrderList {
    private int[] items = new int[1];
    private int size = 0;
    long copies = 0;

    void add(int order) {
        if (size == items.length) {
            int[] bigger = new int[items.length * 2];
            for (int i = 0; i < size; i++) {
                bigger[i] = items[i];
                copies++;
            }
            items = bigger;
        }
        items[size] = order;
        size++;
    }
}

OrderList orders = new OrderList();
for (int i = 0; i < 9; i++) {
    orders.add(100000 + i);
}

Paso a paso, en palabras

1. El array empieza con un lugar y size es 0. Contamos solo las copias de elementos antiguos.
2. El primer pedido: hay espacio, add lo escribe. Copias: 0.
3. El segundo: el array está lleno. Un array nuevo con 2 lugares, y el pedido antiguo se copia en él: 1 copia.
4. El tercero: otra vez lleno, 4 lugares y 2 copias. El cuarto entra sin copiar.
5. El quinto copia 4, el noveno 8. Las copias crecen, pero entre ellas llegan cada vez más adiciones sin copiar.
6. 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 {
    private int[] items = new int[1];
    private int size = 0;
    long copies = 0;

    void add(int order) {
        if (size == items.length) {
            int[] bigger = new int[items.length * 2];
            for (int i = 0; i < size; i++) {
                bigger[i] = items[i];
                copies++;
            }
            items = bigger;
        }
        items[size] = order;
        size++;
    }
}

for (int n : new int[] {5}) {
    OrderList orders = new OrderList();
    for (int i = 0; i < n; i++) {
        orders.add(100000 + i);
    }
    System.out.println(n + " pedidos: " + orders.copies + " copias");
}

Respuesta

5 pedidos: 7 copias

5 pedidos: 4 copias

5 pedidos: 10 copias

Comprobar

Míralo

Un lugar más: O(n²)

La misma clase, solo que el array nuevo tiene un lugar más:

int[] bigger = new int[items.length + 1];

for (int n : new int[] {9, 1000}) {
    OrderList orders = new OrderList();
    for (int i = 0; i < n; i++) {
        orders.add(100000 + i);
    }
    System.out.println(n + " pedidos: " + orders.copies + " copias");
}

Salida

9 pedidos: 36 copias
1000 pedidos: 499500 copias

Con 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

El código se ejecuta en tu navegador, en JavaScript. La cantidad de operaciones es la misma en todos los lenguajes, porque el algoritmo es el mismo. El tiempo depende de la máquina, así que solo sirve para comparar. «≈» es una estimación a partir de la curva: un n tan grande no lo ejecutamos, para que la página no se congele.

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 (size == items.length) {
    int[] bigger = new int[];

Comprobar

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 (int n : new int[] {1000, 100000}) {
    OrderList orders = new OrderList();
    for (int i = 0; i < n; i++) {
        orders.add(100000 + i);
    }
    System.out.println(n + " pedidos: " + orders.copies + " copias");
}

Salida

1000 pedidos: 4510 copias
100000 pedidos: 49951000 copias

Con 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.

1class OrderList {2 private int[] items = new int[1];3 private int size = 0;4 long copies = 0;56 void add(int order) {7 if (size == items.length) {8 int[] bigger = new int[items.length + 100];9 for (int i = 0; i < size; i++) {10 bigger[i] = items[i];11 copies++;12 }13 items = bigger;14 }15 items[size] = order;16 size++;17 }18}

Comprobar

La idea

Cómo crece cada lenguaje

Ningún lenguaje duplica exactamente, pero todos multiplican:

• Java ArrayList: el tamaño nuevo es el viejo más la mitad, ×1,5. Una lista vacía recibe 10 lugares en la primera adición.
• C# List<T>: ×2;
• Python (CPython): aproximadamente ×1,125;
• JavaScript (V8): aproximadamente ×1,5.

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 ArrayList<>(n). Así la lista nunca copia.

ArrayList también tiene ensureCapacity(n) para una lista que ya existe.

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?

Salida

1000 pedidos: 2137 copias, 2n = 2000
100000 pedidos: 276521 copias, 2n = 200000

Má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

Ponte a prueba

1. Un array se duplica cuando se llena. ¿Cuántas copias hacen en total 1000 adiciones si empieza con 1 lugar?

1000 × 1000Menos de 2000Exactamente 1000

2. ¿Qué significa «añadir es O(1) amortizado»?

Cada adición es rápidaAñadir es rápido en promedio para una entrada aleatorian adiciones cuestan O(n) en total, aunque una de ellas copie todo

3. Un colega cambia el crecimiento de ×2 a +1000 lugares «para no desperdiciar memoria». ¿Qué pasa con un millón de adiciones?

Nada, 1000 son muchos lugaresLas copias pasan a ser unas n²/2000: quinientos millones en lugar de aproximadamente un millónVa más rápido, porque el array es más pequeño

4. ¿Por qué Java crece ×1,5 y no ×2 o ×10?

Cuanto mayor es el factor, menos copias, pero más lugares vacíos después de un crecimientoSolo ×1,5 da O(1) amortizadoPorque ×1,5 es más rápido para el procesador

5. Un programa para la caja no puede detenerse más de un milisegundo por adición. ¿Qué haces?

Cambias al crecimiento +1Nada, añadir es O(1)Fijas los lugares de antemano si sabes cuántos elementos habrá

Comprobar

Empezar la lección de nuevo

Lecciones relacionadas

• Se basa en: Complejidad en tiempo: contar pasos · Big-O: cómo crece el trabajo · Mejor caso, caso promedio y peor caso · Complejidad en espacio
• Continúa en: El arreglo dinámico por dentro · Lista enlazada · Pila y cola · Tabla hash
• Ejercicios sobre el tema: Complejidad