Ir al contenido
wannacode

Complejidad en tiempo: contar pasos

En resumen: La complejidad en tiempo dice cómo crece el número de operaciones básicas con el tamaño de la entrada: un bucle anidado hace n(n − 1) / 2 pasos, una pasada con un conjunto hace n.

Problema

El informe que nunca termina

Cada mes la tienda en línea ejecuta un informe de ventas. Una de sus comprobaciones busca pagos duplicados: el mismo pago cobrado dos veces porque alguien volvió a pulsar el botón. La función compara cada pago con cada pago posterior:

function doublePayments(ids) {
  let found = 0;
  for (let i = 0; i < ids.length; i++) {
    for (let j = i + 1; j < ids.length; j++) {
      if (ids[i] === ids[j]) {
        found++;
      }
    }
  }
  return found;
}
const ids = [100231, 100232, 100233, 100232, 100234];
console.log("Pagos duplicados: " + doublePayments(ids));
Salida
Pagos duplicados: 1

Hace un año había 1 000 pedidos al mes y el informe estaba listo en 2 segundos. Hoy hay 100 000. El informe arranca por la tarde y por la mañana sigue ejecutándose. Nadie tocó el código. Los datos son 100 veces mayores, y el tiempo no es 100 veces mayor, es mucho mayor.

¿Por qué? ¿Y cómo podrías saberlo de antemano, sin esperar toda la noche?

La idea

Los segundos mienten, los pasos no

Cuántos segundos tarda un programa depende de muchas cosas ajenas a él:

  • la máquina: la laptop y el servidor dan números distintos;
  • la carga: el mismo informe es más lento mientras el servidor también atiende a clientes;
  • el lenguaje: el mismo cálculo es varias veces más lento en Python que en Java o C#.

Por eso medimos otra cosa: cuántas veces hace el programa su operación básica. Aquí es una comparación de dos números. Su cantidad no depende ni de la máquina ni del lenguaje, solo del algoritmo y de la entrada. Se llama número de operaciones (o número de pasos).

El número de operaciones no te dice los segundos. Te dice algo más útil: cuánto más trabajo llega cuando crecen los datos.

Míralo

Contar los pasos

Pones un contador junto a la comparación. Cada comparación es un paso:

let steps = 0;


function doublePayments(ids) {
  let found = 0;
  for (let i = 0; i < ids.length; i++) {
    for (let j = i + 1; j < ids.length; j++) {
      steps++;
      if (ids[i] === ids[j]) {
        found++;
      }
    }
  }
  return found;
}

El informe se ejecuta con 10, 1 000 y 2 000 pagos con números distintos:

for (const n of [10, 1000, 2000]) {
  const ids = Array.from({ length: n }, (_, k) => 100000 + k);
  steps = 0;
  doublePayments(ids);
  console.log(`n = ${n}: ${steps} pasos`);
}
Salida
n = 10: 45 pasos
n = 1000: 499500 pasos
n = 2000: 1999000 pasos

El primer pago se compara con n − 1 más, el segundo con n − 2, y así hasta el último, que ya no tiene con quién. La suma es

n(n − 1) / 2

Con 1 000 pagos son 499 500 pasos. Con 100 000 son 4 999 950 000: 10 010 veces más para 100 veces más datos. Si los dos segundos se iban casi por completo en las comparaciones, ahora se van más de cinco horas y media. La respuesta estaba en el código hace un año: solo había que contar.

Míralo

Por qué casi ×4

let steps = 0;


function doublePayments(ids) {
  let found = 0;
  for (let i = 0; i < ids.length; i++) {
    for (let j = i + 1; j < ids.length; j++) {
      steps++;
      if (ids[i] === ids[j]) {
        found++;
      }
    }
  }
  return found;
}
Paso a paso, en palabras
  1. Cuatro pagos. El bucle exterior toma el primero, i = 0: se comparará con cada pago posterior.
  2. j recorre los pagos posteriores a i. Cada comparación es un paso y se ilumina la celda del par: steps = 1, 2, 3.
  3. i avanza y j empieza de nuevo en i + 1. Los pares son 3 + 2 + 1 = 6: un triángulo.
  4. El doble de pagos: 8. Los pasos no son 12, sino 28.
  5. 28 = 6 pares viejos + 6 pares entre los nuevos + 16 pares de uno nuevo con uno viejo. Casi ×4: con 1 000 → 2 000 pagos los pasos son 499 500 → 1 999 000.
  6. La corrección recorre los pagos una vez y los recuerda en seen: 8 pagos, 8 pasos. Aquí el doble de pagos significa el doble de pasos.

Duplicar no es solo «otra vez tantos pagos». Los 6 pares viejos se quedan. 6 pares aparecen entre los pagos nuevos. Y 16 más: cada uno de los 4 nuevos con cada uno de los 4 viejos. En total, 28. La parte «nuevo con viejo» es un cuadrado, y es la que crece más rápido. Por eso, con n grande, duplicar da casi exactamente ×4.

Más precisamente, para curiosos

La cuenta para cualquier n: con 2n pagos los pares son 2n(2n − 1) / 2 = 4 · n(n − 1) / 2 + n. Es decir, cuatro veces los pares viejos y n más. Con n = 4 es 4 · 6 + 4 = 28, y con n = 1 000 es 4 · 499 500 + 1 000 = 1 999 000. El n de más es pequeño frente al resto, y cuanto mayor es n, más pequeño resulta.

Pruébalo

Predice la salida

Dos bucles anidados. El primero recorre 4 almacenes y, para cada uno, 3 horas de envío. El segundo recorre cada par de los 4 almacenes. ¿Qué imprime el programa?

let full = 0;
for (let i = 0; i < 4; i++) {
  for (let j = 0; j < 3; j++) {
    full++;
  }
}
let pairs = 0;
for (let i = 0; i < 4; i++) {
  for (let j = i + 1; j < 4; j++) {
    pairs++;
  }
}
console.log(full + " " + pairs);
Respuesta

Pruébalo

Completa

El informe debe comparar cada par exactamente una vez y nunca un pago consigo mismo. ¿Dónde empieza el bucle interior?

function doublePayments(ids) {
  let found = 0;
  for (let i = 0; i < ids.length; i++) {
    for (let j = ; j < ids.length; j++) {
      if (ids[i] === ids[j]) {
        found++;
      }
    }
  }
  return found;
}

Míralo

La corrección: una sola pasada

No hace falta comparar cada pago con todos los demás. Basta con recordar los números que ya has visto. Un conjunto (set) guarda esos números y te dice si un número está en él, sin recorrerlos uno por uno.

let steps = 0;


function doublePayments(ids) {
  const seen = new Set();
  let found = 0;
  for (const id of ids) {
    steps++;
    if (seen.has(id)) {
      found++;
    } else {
      seen.add(id);
    }
  }
  return found;
}
seen.has(id) pregunta al conjunto si el número está en él, y seen.add(id) lo registra.
for (const n of [10, 1000, 2000]) {
  const ids = Array.from({ length: n }, (_, k) => 100000 + k);
  steps = 0;
  doublePayments(ids);
  console.log(`n = ${n}: ${steps} pasos`);
}
Salida
n = 10: 10 pasos
n = 1000: 1000 pasos
n = 2000: 2000 pasos

Los pasos son tantos como los pagos. El doble de pagos significa el doble de pasos. Ejecuta los dos informes uno junto al otro:

  • Cada par de pedidos O(n²)
  • El informe con un conjunto (set) O(n)
Algoritmon = 10n = 1000n = 2000n = 4000n = 100.000
Cada par de pedidos45499.5001.999.0007.998.000≈ 4.998.750.000
El informe con un conjunto (set)10100020004000100.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.
Más precisamente, para curiosos

¿Cuál es la operación básica? La que más se repite y de la que depende el tiempo. En el informe lento es la comparación del bucle interior. Incrementar i y j y comprobar si el bucle ha terminado también se repiten, pero tantas veces como las comparaciones, no más. Por eso su cantidad no cambia el panorama y no se cuenta aparte.

¿La comprobación en el conjunto es un paso? No del todo: detrás del conjunto hay una tabla hash, que calcula el hash del número y mira en una cubeta. En promedio es siempre la misma pequeña cantidad de trabajo, haya los números que haya dentro. Verás cómo en el módulo «Estructuras de datos». Aquí lo contamos como un paso, igual que Bench.

Segundos en los distintos lenguajes. El número de pasos es el mismo, el tiempo no. V8 compila a código máquina el bucle caliente mientras se ejecuta, así que la primera ejecución es más lenta que las siguientes. Bench en esta página ejecuta exactamente este JavaScript, así que sus segundos son los más cercanos a los tuyos.

Ejercicio

Ventas por producto

Resuelve la tarea en tu editor.

Cuántos pasos. El informe de ventas cuenta cuántas veces se pidió cada uno de los 50 productos. Un pedido es el número del producto (de 0 a 49):

function salesByProduct(orders, products) {
  const sales = new Array(products).fill(0);
  for (let p = 0; p < products; p++) {
    for (const product of orders) {
      if (product === p) {
        sales[p]++;
      }
    }
  }
  return sales;
}

Añade un contador steps antes de la comparación. Ejecuta la función con 1 000 y con 2 000 pedidos, donde el producto del pedido k es k % 50, e imprime los pasos:

Salida
n = 1000: 50000 pasos
n = 2000: 100000 pasos

El bucle es anidado y, aun así, los pasos solo se duplican. ¿Por qué?

Más tareas

  • Una pasada. Escribe el informe de ventas con una sola pasada por los pedidos: sales[product] crece en uno por cada pedido. ¿Cuántos pasos hay con 1 000 pedidos?
  • El informe del año. ¿Cuántos pasos hace el informe lento de pagos duplicados para un año entero con 100 000 pagos al mes? Calcúlalo con n(n − 1) / 2, sin ejecutarlo.
  • Tu código. Busca un bucle anidado en tu propio código y cuenta sus pasos para dos tamaños de entrada. ¿Qué pasa cuando la entrada se duplica?

Test

Ponte a prueba

1. ¿Por qué contamos operaciones y no segundos?
2. El informe compara cada pago con cada pago posterior. Los pagos se duplican. ¿Cuántas veces más pasos hay?
3. El informe de ventas recorre los 50 productos y, para cada producto, recorre todos los pedidos. Los pedidos se duplican. ¿Cuántas veces más pasos hay?
4. ¿Cuántos pasos hace la corrección con el conjunto con 100 000 pagos?

Creado por Ivo Gergov como parte de la campaña de Evo Tech por una educación accesible en programación ·