Mejor caso, caso promedio y peor caso en JavaScript

Problema

En la prueba fue instantáneo

El equipo de soporte de la tienda busca un pedido por número cuando llama un cliente. Los pedidos del mes están en una lista, en el orden en que llegaron. El compañero que escribió la búsqueda la probó con el pedido 1001 y dijo: «Una comprobación. Es instantáneo, sean cuantos sean los pedidos».

Un mes después soporte se queja: a veces la búsqueda es rápida y a veces es lenta. Es más lenta cuando el cliente se equivoca de número y ese pedido no existe.

Las dos cosas son ciertas. La misma búsqueda hace una comprobación o las hace todas. Entonces, ¿qué tan rápida es? ¿Qué número le dices a soporte?

La idea

Tres casos de un algoritmo

El número de operaciones no depende solo de n, sino también de cuál es la entrada. Por eso se miran tres casos:

el mejor caso: la entrada con menos trabajo. Aquí el pedido buscado es el primero;
el peor caso: la entrada con más trabajo. Aquí el pedido es el último o no existe;
el caso promedio: cuánto trabajo hay en promedio si las entradas siguen alguna regla, normalmente «cada una es igual de probable».

El compañero midió el mejor caso y dijo O(1). Pero la búsqueda lineal es O(n): con n pedidos las comprobaciones pueden ser n.

Míralo

La búsqueda con contador

La búsqueda comprueba los pedidos uno por uno y se detiene cuando encuentra el número:

let checks = 0;

function findOrder(ids, wanted) {
  for (let i = 0; i < ids.length; i++) {
    checks++;
    if (ids[i] === wanted) {
      return i;
    }
  }
  return -1;
}

report pone el contador a cero, busca e imprime la posición (-1 si el pedido no está) y las comprobaciones:

function report(ids, wanted) {
  checks = 0;
  const at = findOrder(ids, wanted);
  console.log(`${wanted}: ${at}, comprobaciones: ${checks}`);
}

Tres búsquedas en 1 000 pedidos: el primero, el del medio y un número que no existe:

const ids = Array.from({ length: 1000 }, (_, k) => 1001 + k);
report(ids, 1001);
report(ids, 1501);
report(ids, 999);

1001: 0, comprobaciones: 1
1501: 500, comprobaciones: 501
999: -1, comprobaciones: 1000

Míralo

Una búsqueda, tres casos

let checks = 0;

function findOrder(ids, wanted) {
  for (let i = 0; i < ids.length; i++) {
    checks++;
    if (ids[i] === wanted) {
      return i;
    }
  }
  return -1;
}

function report(ids, wanted) {
  checks = 0;
  const at = findOrder(ids, wanted);
  console.log(`${wanted}: ${at}, comprobaciones: ${checks}`);
}

const ids = Array.from({ length: 8 }, (_, k) => 1001 + k);
report(ids, 1001);
report(ids, 1005);
report(ids, 999);

Paso a paso, en palabras

8 pedidos del mes, numerados de 1001 a 1008 en el orden en que llegaron. La búsqueda va desde el principio, uno por uno.
El mejor caso: el pedido es el primero. 1 comprobación y la búsqueda termina. Salida: 1001: 0, comprobaciones: 1.
El pedido está en el medio: 5 comprobaciones, n/2 + 1. Salida: 1005: 4, comprobaciones: 5.
El peor caso: ese pedido no existe. La búsqueda comprueba los 8 y solo entonces devuelve -1. Salida: 999: -1, comprobaciones: 8.
El caso promedio: si cada pedido se busca con la misma frecuencia, las comprobaciones son 1, 2, …, 8. En promedio (1 + … + 8) / 8 = 4,5: unas n/2. Sigue siendo O(n).
Lo que se promete es el peor caso: como máximo n comprobaciones, se busque lo que se busque. La búsqueda lineal es O(n).

Los mismos 8 pedidos, la misma búsqueda. La única diferencia es qué se busca.

La idea

Por qué prometemos el peor caso

El mejor caso no dice nada. Casi cualquier algoritmo es rápido si la entrada le conviene. Prometer el mejor caso es contar con la suerte.

El peor caso es una promesa. «Como máximo n comprobaciones, se busque lo que se busque». Con ese número planificas: cuántos pedidos puede buscar soporte antes de que la página se ponga lenta. Por eso, cuando se dice «la búsqueda lineal es O(n)», se habla del peor caso.

El caso promedio es útil, pero necesita una suposición. Si cada pedido se busca con la misma frecuencia (entrada aleatoria), buscar cada uno una vez da el promedio:

const ids = Array.from({ length: 1000 }, (_, k) => 1001 + k);
let total = 0;
for (const wanted of ids) {
  checks = 0;
  findOrder(ids, wanted);
  total += checks;
}
console.log("Total: " + total);
console.log("Promedio: " + total / ids.length);

Total: 500500
Promedio: 500.5

(1 + 2 + … + 1 000) / 1 000 = 500,5: unas n/2. La constante ½ no cambia la clase: el caso promedio también es O(n). Pero si se buscan sobre todo pedidos nuevos, o sobre todo números equivocados, el promedio es otro. La suposición sobre la entrada forma parte de la respuesta.

Ejecuta los tres casos en Bench:

El pedido buscado es el primero O(1)
El pedido buscado está en el medio O(n)
No hay tal pedido O(n)

Algoritmo	n = 10	n = 1000	n = 100.000
El pedido buscado es el primero	1	1	1
El pedido buscado está en el medio	6	501	50.001
No hay tal pedido	10	1000	100.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

La búsqueda incorporada en una lista es la misma búsqueda lineal. indexOf, includes y find recorren los elementos uno por uno: O(n) en el peor caso. indexOf devuelve -1 si el elemento no está, y find devuelve undefined.

Cuando el caso promedio y el peor son muy distintos. Algunos algoritmos son rápidos casi siempre y, con entradas raras, se vuelven mucho más lentos. Quicksort es O(n log n) en promedio y, con una mala elección del pivote, pasa a O(n²) (lo verás en la lección sobre quicksort). Una tabla hash encuentra una clave con un paso en promedio, y con n si todas las claves caen en la misma cubeta (el módulo «Estructuras de datos»). Ahí se citan los dos casos, porque los dos importan.

Pruébalo

Predice la salida

Seis pedidos, tres búsquedas. ¿Cuántas comprobaciones imprime el programa?

const ids = [1001, 1002, 1003, 1004, 1005, 1006];
for (const wanted of [1004, 1006, 1010]) {
  checks = 0;
  findOrder(ids, wanted);
  console.log(checks);
}

Respuesta

3 / 5 / 6

4 / 6 / 0

4 / 6 / 6

Pruébalo

Encuentra el error

Alguien escribe la búsqueda así:

function findOrder(ids, wanted) {
  let found = -1;
  for (let i = 0; i < ids.length; i++) {
    checks++;
    if (ids[i] === wanted) {
      found = i;
    }
  }
  return found;
}

const ids = Array.from({ length: 8 }, (_, k) => 1001 + k);
report(ids, 1001);
report(ids, 1005);
report(ids, 999);

1001: 0, comprobaciones: 8
1005: 4, comprobaciones: 8
999: -1, comprobaciones: 8

Encuentra la posición correcta, pero cada búsqueda hace 8 comprobaciones. ¿En qué línea está el error?

Elige la línea con el error.

Ejercicio

Los pedidos nuevos son los que más se buscan

Resuelve la tarea en tu editor.

Buscar desde el final. Soporte casi siempre busca pedidos de los últimos días. Escribe findLatest, que busca del final al principio y cuenta las comprobaciones, y ejecútalo en report para 1 000 pedidos con los números 2000 (el último), 1001 (el primero) y 999 (no existe):

2000: 999, comprobaciones: 1
1001: 0, comprobaciones: 1000
999: -1, comprobaciones: 1000

¿Cuál es ahora el mejor caso? ¿Y el peor? ¿Ha cambiado la clase?

Más tareas

El promedio desde el final. Ejecuta el programa del caso promedio con findLatest. ¿Por qué el promedio es el mismo?
Números equivocados. Si la mitad de las búsquedas usa un número equivocado y la otra mitad es uniforme, ¿cuántas comprobaciones hay en promedio con 1 000 pedidos?
Ordenados por número. Los pedidos están ordenados por número. ¿Cómo puede la búsqueda detenerse antes cuando el número no existe? ¿Cuántas comprobaciones hace entonces para 999?

Test

Ponte a prueba

1. La búsqueda lineal encuentra el pedido en la primera comprobación. ¿Eso la hace O(1)?Sí, porque es una sola comprobaciónNo: ese es el mejor caso. En el peor caso son n comprobaciones, así que es O(n)Depende del lenguaje

2. ¿Por qué normalmente se cita el peor caso?Porque es el más fácil de calcularPorque es una promesa: se busque lo que se busque, el trabajo no es mayor que estoPorque es el más frecuente

3. Cada uno de 1 000 pedidos se busca con la misma frecuencia. ¿Cuántas comprobaciones hace la búsqueda lineal en promedio?1 000Unas 5001

4. Los clientes casi siempre buscan sus pedidos más recientes. ¿Cómo puedes acelerar la búsqueda sin cambiar el algoritmo?Nada ayudaBuscar dos vecesBuscar del final al principio

Mejor caso, caso promedio y peor caso

Cookies