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:

def import_orders(n):
    orders = []
    copies = 0
    for i in range(n):
        copies += len(orders)
        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 n in [1000, 10000]:
    print(f"{n} pedidos: {import_orders(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, list.append 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:

cart = ["Pan", "Leche", "Café", "Mantequilla"]
cart.append("Queso")
cart.remove("Leche")
print(cart)
print("Productos:", len(cart))

Paso a paso, en palabras

1. cart apunta a un objeto list. Dentro hay un contador ob_size y un array ob_item con 4 lugares.
2. Los productos del código llenan los lugares uno a uno. El array está lleno: 4 de 4.
3. No hay sitio. append reserva un array con 8 lugares, y los elementos pasan a él.
4. Ahora ob_item apunta al array nuevo. «Queso» va al primer 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 cuatro productos. CPython 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:
    def __init__(self):
        self.items = [None]
        self.size = 0
        self.copies = 0

    def add(self, order):
        if self.size == len(self.items):
            bigger = [None] * (len(self.items) * 2)
            for i in range(self.size):
                bigger[i] = self.items[i]
                self.copies += 1
            self.items = bigger
        self.items[self.size] = order
        self.size += 1

for n in [9, 1000]:
    orders = OrderList()
    for i in range(n):
        orders.add(100000 + i)
    print(f"{n} pedidos: {orders.copies} copias, 2n = {2 * n}")

Salida

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

class OrderList:
    def __init__(self):
        self.items = [None]
        self.size = 0
        self.copies = 0

    def add(self, order):
        if self.size == len(self.items):
            bigger = [None] * (len(self.items) * 2)
            for i in range(self.size):
                bigger[i] = self.items[i]
                self.copies += 1
            self.items = bigger
        self.items[self.size] = order
        self.size += 1

orders = OrderList()
for i in range(9):
    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:
    def __init__(self):
        self.items = [None]
        self.size = 0
        self.copies = 0

    def add(self, order):
        if self.size == len(self.items):
            bigger = [None] * (len(self.items) * 2)
            for i in range(self.size):
                bigger[i] = self.items[i]
                self.copies += 1
            self.items = bigger
        self.items[self.size] = order
        self.size += 1


for n in [5]:
    orders = OrderList()
    for i in range(n):
        orders.add(100000 + i)
    print(f"{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:

bigger = [None] * (len(self.items) + 1)

for n in [9, 1000]:
    orders = OrderList()
    for i in range(n):
        orders.add(100000 + i)
    print(f"{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 self.size == len(self.items):
    bigger = [None] * ()

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 n in [1000, 100000]:
    orders = OrderList()
    for i in range(n):
        orders.add(100000 + i)
    print(f"{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 def __init__(self):3 self.items = [None]4 self.size = 05 self.copies = 067 def add(self, order):8 if self.size == len(self.items):9 bigger = [None] * (len(self.items) + 100)10 for i in range(self.size):11 bigger[i] = self.items[i]12 self.copies += 113 self.items = bigger14 self.items[self.size] = order15 self.size += 1

Comprobar

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 3.12): el tamaño nuevo es n + n/8 + 6, redondeado hacia abajo a un múltiplo de 4. Es aproximadamente ×1,125. El lenguaje no lo promete; lo decide CPython.
• 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».

Cuántos lugares tiene la lista en cada crecimiento, con 1000 adiciones:

import sys


def places(items):
    return (sys.getsizeof(items) - sys.getsizeof([])) // 8


orders = []
seen = []
for i in range(1000):
    orders.append(100000 + i)
    if not seen or seen[-1] != places(orders):
        seen.append(places(orders))
print("Los lugares en cada crecimiento:", " ".join(str(p) for p in seen))

Salida

Los lugares en cada crecimiento: 4 8 16 24 32 40 52 64 76 92 108 128 148 172 200 232 268 308 352 400 456 520 592 672 760 860 972 1100

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: [None] * n. Así la lista nunca copia.

[None] * n crea una lista de n elementos None, y luego escribes por índice, no con append.

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