Divide y vencerás y el árbol de recursión en JavaScript

Problema

Cuántas entregas se intercambiaron

La empresa de mensajería promete a cada cliente una hora de entrega. Así que los pedidos tienen un orden prometido: 1, 2, 3 y así sucesivamente. Pero las furgonetas conducen como conducen, y por la tarde el informe pregunta: ¿qué tan lejos está el orden de las entregas de hoy del prometido?

La medida es el número de pares intercambiados: el pedido 5 se entregó antes que el 3, aunque el 3 se prometió antes. Un par así se llama inversión. Si las entregas están exactamente en el orden prometido, hay 0 inversiones.

La primera solución comprueba cada par:

function countPairs(ranks) {
  let inversions = 0;
  for (let i = 0; i < ranks.length; i++) {
    for (let j = i + 1; j < ranks.length; j++) {
      if (ranks[i] > ranks[j]) {
        inversions++;
      }
    }
  }
  return inversions;
}

const ranks = [4, 1, 7, 3, 8, 2, 6, 5];
console.log(`Inversiones: ${countPairs(ranks)}`);

Inversiones: 12

Con 8 pedidos son 28 pares. Con n pedidos son n(n − 1)/2, o sea O(n²). La empresa hace 100 000 entregas al día, y los pares son 4 999 950 000. El informe que tarda un momento en las pruebas tarda minutos por la tarde.

La idea

Dividir, contar, combinar

El enfoque es divide y vencerás, como en el ordenamiento por mezcla: divide las entregas en la primera mitad y la segunda mitad. Cada par intercambiado es de uno de tres tipos:

los dos pedidos están en la primera mitad;
los dos están en la segunda;
uno está en la primera y el otro en la segunda.

Los dos primeros tipos son el mismo problema, solo que la mitad de grande: la recursión los cuenta. Lo difícil es el tercer tipo, los pares entre las mitades. Si compruebas cada uno, vuelves a n².

Aquí ayuda la mezcla. Supón que las dos mitades ya están ordenadas. Al mezclar tomas el menor de los dos primeros números sin tomar. Cuando el menor está a la derecha, todo número sin tomar a la izquierda es mayor que él y llegó antes, porque es de la primera mitad. Cada uno de ellos es una inversión. Así, una comparación cuenta de golpe tantas como números quedan a la izquierda.

De este modo el conteo «va montado» en el ordenamiento por mezcla: la misma división, la misma mezcla y una línea más.

Míralo

Contar mientras se mezcla

sortCount ordena las entregas en el sitio y devuelve cuántas inversiones tienen. Mira la última mezcla: cada número de la derecha que baja cuenta los números sin tomar de la izquierda:

function sortCount(ranks) {
  if (ranks.length <= 1) {
    return 0;
  }
  const mid = Math.floor(ranks.length / 2);
  const left = ranks.slice(0, mid);
  const right = ranks.slice(mid);
  const a = sortCount(left);
  const b = sortCount(right);
  let cross = 0;
  let i = 0;
  let j = 0;
  let k = 0;
  while (i < left.length && j < right.length) {
    if (left[i] <= right[j]) {
      ranks[k++] = left[i++];
    } else {
      cross += left.length - i;
      ranks[k++] = right[j++];
    }
  }
  while (i < left.length) {
    ranks[k++] = left[i++];
  }
  while (j < right.length) {
    ranks[k++] = right[j++];
  }
  return a + b + cross;
}

Paso a paso, en palabras

sortCount recibe 8 pedidos en el orden en que llegaron. Cada número es el lugar del pedido en el orden prometido.
mid = 4: las primeras cuatro entregas [4, 1, 7, 3] y las últimas cuatro [8, 2, 6, 5]. Cada par intercambiado está dentro de una mitad o entre las dos.
Cada mitad llama a sortCount para sí misma: cuenta sus propios pares (a = 3, b = 4) y vuelve ordenada.
Ahora los pares entre las mitades. i y j apuntan al primer número sin tomar. 1 < 2: baja el de la izquierda, sin inversión.
2 a la derecha es menor. Cada número que queda a la izquierda ([3, 4, 7]) es mayor y llegó antes: left.length - i = 3 inversiones de golpe.
La misma regla cada vez: 5 suma 1, 6 suma 1. cross = 5, tras 7 comparaciones.
Un lado se ha acabado. El resto va al final sin comparar: no suma inversiones.
a + b + cross = 3 + 4 + 5 = 12. La comprobación por pares mira los 28 pares; la mezcla encuentra las mismas 12 con 17 comparaciones en total.

const ranks = [4, 1, 7, 3, 8, 2, 6, 5];
console.log(`Inversiones: ${sortCount(ranks)}`);
console.log(`Ordenado: [${ranks.join(", ")}]`);

Inversiones: 12
Ordenado: [1, 2, 3, 4, 5, 6, 7, 8]

La función ordena el arreglo que recibe. Si también necesitas el orden de las entregas, pasa una copia.

En JavaScript la función puede devolver los dos resultados como un arreglo, return [merged, count], y quien llama los toma con const [sorted, count] = …. Aquí el ordenamiento ocurre en el propio arreglo, así que el código es como en los otros lenguajes.

Pruébalo

Predice la salida

Las dos mitades, [2, 4, 6] y [1, 3, 5], ya están ordenadas, así que dentro de ellas no hay inversiones. ¿Cuántas hay entre ellas?

function sortCount(ranks) {
  if (ranks.length <= 1) {
    return 0;
  }
  const mid = Math.floor(ranks.length / 2);
  const left = ranks.slice(0, mid);
  const right = ranks.slice(mid);
  const a = sortCount(left);
  const b = sortCount(right);
  let cross = 0;
  let i = 0;
  let j = 0;
  let k = 0;
  while (i < left.length && j < right.length) {
    if (left[i] <= right[j]) {
      ranks[k++] = left[i++];
    } else {
      cross += left.length - i;
      ranks[k++] = right[j++];
    }
  }
  while (i < left.length) {
    ranks[k++] = left[i++];
  }
  while (j < right.length) {
    ranks[k++] = right[j++];
  }
  return a + b + cross;
}

const ranks = [2, 4, 6, 1, 3, 5];
console.log(`Inversiones: ${sortCount(ranks)}`);

Respuesta

Inversiones: 3

Inversiones: 6

Inversiones: 15

La idea

El árbol de recursión

¿Cuánto cuesta esto? Dibuja las llamadas como un árbol. Arriba está la llamada con los n pedidos. Debajo, las dos llamadas que hace, con n/2 cada una. Debajo de cada una, dos más, y así hasta abajo.

Luego marca para cada llamada su trabajo: lo que hace por sí misma, fuera de sus llamadas recursivas. Aquí es la mezcla: pasa una vez por cada pedido que recibió la llamada.

Ahora suma por niveles. Arriba el trabajo es n. En el nivel siguiente hay dos llamadas con n/2 cada una: otra vez n. Luego cuatro con n/4: otra vez n. Los niveles son las veces que n se divide por la mitad hasta 1, unos log₂ n. Así que el coste es los niveles por el trabajo de cada nivel: n · log₂ n.

Esto se llama el árbol de recursión. Así cuentas el coste de cualquier divide y vencerás: no adivinas, sumas nivel por nivel.

Míralo

Tres árboles, tres costes

El mismo conteo para tres funciones con 8 pedidos. La búsqueda binaria de su lección, escrita con recursión. Contar mezclando. Y una tercera función que también divide, pero mal: los primeros n − 1 pedidos de forma recursiva, y el último comparado con todos los anteriores.

function sortCount(ranks) {
  if (ranks.length <= 1) {
    return 0;
  }
  const mid = Math.floor(ranks.length / 2);
  const left = ranks.slice(0, mid);
  const right = ranks.slice(mid);
  const a = sortCount(left);
  const b = sortCount(right);
  let cross = 0;
  let i = 0;
  let j = 0;
  let k = 0;
  while (i < left.length && j < right.length) {
    if (left[i] <= right[j]) {
      ranks[k++] = left[i++];
    } else {
      cross += left.length - i;
      ranks[k++] = right[j++];
    }
  }
  while (i < left.length) {
    ranks[k++] = left[i++];
  }
  while (j < right.length) {
    ranks[k++] = right[j++];
  }
  return a + b + cross;
}

function find(ranks, target, lo, hi) {
  if (lo > hi) {
    return -1;
  }
  const mid = Math.floor((lo + hi) / 2);
  if (ranks[mid] === target) {
    return mid;
  }
  if (ranks[mid] < target) {
    return find(ranks, target, mid + 1, hi);
  }
  return find(ranks, target, lo, mid - 1);
}

Paso a paso, en palabras

Cada caja es una llamada, y el número que contiene es cuántos pedidos recibe. find mira la mitad una vez: trabajo 1.
Luego se llama a sí misma con UNA mitad: 8 → 4 → 2 → 1. Una rama, y cada nivel hace 1.
4 niveles × 1 = 4. Los niveles son las veces que n se divide por la mitad hasta 1, unos log₂ n: O(log n).
sortCount se llama a sí misma con LAS DOS mitades. La mezcla de arriba pasa por los 8 pedidos; las dos de abajo pasan por 4 + 4 = 8.
En cada nivel hay el doble de llamadas, cada una con la mitad de pedidos: el trabajo por nivel sigue siendo 8. Las llamadas con un pedido solo vuelven: 0.
3 niveles × 8 = 24: log₂ n niveles de n cada uno, O(n log n). Con 100.000 pedidos son 17 niveles, no 100.000.
countSlow también divide, pero mal: los primeros n − 1 pedidos y el último. La recursión sigue con n − 1: 8 → 7 → 6 …
En cada nivel el último pedido se compara con todos los anteriores: 7, 6, … 1. 8 niveles, y 7 + 6 + 5 + … + 1 = 28: exactamente los 28 pares, O(n²).
El coste es la forma del árbol: niveles × trabajo por nivel. Dividir por la mitad da log n niveles; separar de uno en uno da n niveles. No basta con dividir: las mitades tienen que ser iguales.

const sorted = [1, 2, 3, 4, 5, 6, 7, 8];
console.log("find:", find(sorted, 8, 0, sorted.length - 1));
const ranks = [4, 1, 7, 3, 8, 2, 6, 5];
console.log("countSlow:", countSlow(ranks, ranks.length));
console.log("sortCount:", sortCount(ranks));

find: 7
countSlow: 12
sortCount: 12

La forma del árbol decide:

Una rama, la mitad: log₂ n niveles con poco trabajo. O(log n).
Dos ramas, mitades: log₂ n niveles de n. O(n log n).
Una rama, una menos: n niveles de n. O(n²). Eso es comprobar pares, solo que escrito con recursión.

Lo mismo pasa en el quicksort con mal pivote: con una entrada ordenada el pivote separa un precio, y los otros n − 1 se quedan en una parte. El árbol es una cadena de n niveles, y la complejidad es n².

Míralo

Mídelo: por pares contra por mezcla

Ejecuta los dos con las mismas entregas. Para los pares contamos los pares comprobados, para la mezcla las comparaciones. Por pares con 100 000 no se ejecuta de verdad: Bench lo estima a partir de la curva.

Inversiones por pares O(n²)
Inversiones al mezclar O(n log n)

Algoritmo	n = 10	n = 1000	n = 10.000	n = 100.000
Inversiones por pares	45	499.500	49.995.000	≈ 4.999.500.000
Inversiones al mezclar	21	8693	120.553	1.536.329

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.

function sortCount(ranks) {
  if (ranks.length <= 1) {
    return 0;
  }
  const mid = Math.floor(ranks.length / 2);
  const left = ranks.slice(0, mid);
  const right = ranks.slice(mid);
  const a = sortCount(left);
  const b = sortCount(right);
  let cross = 0;
  let i = 0;
  let j = 0;
  let k = 0;
  while (i < left.length && j < right.length) {
    if (left[i] <= right[j]) {
      ranks[k++] = left[i++];
    } else {
      cross += left.length - i;
      ranks[k++] = right[j++];
    }
  }
  while (i < left.length) {
    ranks[k++] = left[i++];
  }
  while (j < right.length) {
    ranks[k++] = right[j++];
  }
  return a + b + cross;
}

Con 1000 entregas los pares son 499.500, y las comparaciones 8693. Con 100 000 la mezcla hace 1.536.329 comparaciones contra 4 999 950 000 pares: más de 3000 veces menos. Y las inversiones son las mismas, 2.504.458.463.

Más precisamente, para curiosos

Los mismos números en tu lenguaje. Las entregas se mezclan con un pequeño generador con semilla, así que son las mismas en cada ejecución, en cada lenguaje y en Bench:

let checks = 0;
let comparisons = 0;

function deliveries(n) {
  const ranks = Array.from({ length: n }, (_, k) => k + 1);
  let x = 2026;
  for (let k = n - 1; k > 0; k--) {
    x = (x * 48271) % 2147483647;
    const j = x % (k + 1);
    [ranks[k], ranks[j]] = [ranks[j], ranks[k]];
  }
  return ranks;
}

function countPairs(ranks) {
  let inversions = 0;
  for (let i = 0; i < ranks.length; i++) {
    for (let j = i + 1; j < ranks.length; j++) {
      checks++;
      if (ranks[i] > ranks[j]) {
        inversions++;
      }
    }
  }
  return inversions;
}

function sortCount(ranks) {
  if (ranks.length <= 1) {
    return 0;
  }
  const mid = Math.floor(ranks.length / 2);
  const left = ranks.slice(0, mid);
  const right = ranks.slice(mid);
  const a = sortCount(left);
  const b = sortCount(right);
  let cross = 0;
  let i = 0;
  let j = 0;
  let k = 0;
  while (i < left.length && j < right.length) {
    comparisons++;
    if (left[i] <= right[j]) {
      ranks[k++] = left[i++];
    } else {
      cross += left.length - i;
      ranks[k++] = right[j++];
    }
  }
  while (i < left.length) {
    ranks[k++] = left[i++];
  }
  while (j < right.length) {
    ranks[k++] = right[j++];
  }
  return a + b + cross;
}

for (const n of [10, 1000]) {
  checks = 0;
  const inv = countPairs(deliveries(n));
  console.log(`por pares, n = ${n}: ${checks} comprobaciones, ${inv} inversiones`);
}
for (const n of [10, 1000, 100000]) {
  comparisons = 0;
  const inv = sortCount(deliveries(n));
  console.log(`por mezcla, n = ${n}: ${comparisons} comparaciones, ${inv} inversiones`);
}

por pares, n = 10: 45 comprobaciones, 14 inversiones
por pares, n = 1000: 499500 comprobaciones, 249193 inversiones
por mezcla, n = 10: 21 comparaciones, 14 inversiones
por mezcla, n = 1000: 8693 comparaciones, 249193 inversiones
por mezcla, n = 100000: 1536329 comparaciones, 2504458463 inversiones

En JavaScript un número es de coma flotante y conserva exactos los enteros hasta 2⁵³, unos 9 · 10¹⁵. 2500 millones de inversiones están muy por debajo. En Java y C# el mismo contador debe ser un long: un int se queda en 2 147 483 647 y da la vuelta sin error.

Pruébalo

Encuentra el error

Un compañero ha reescrito la función. Para las 8 entregas de la escena dice 5 en lugar de 12:

const ranks = [4, 1, 7, 3, 8, 2, 6, 5];
console.log(`Inversiones: ${sortCount(ranks)}`);
console.log(`Ordenado: [${ranks.join(", ")}]`);

Inversiones: 5
Ordenado: [1, 2, 3, 4, 5, 6, 7, 8]

¿En qué línea está el error?

Elige la línea con el error.

Pruébalo

Completa

El número de la derecha es menor y baja. ¿Cuánto crece cross?

function sortCount(ranks) {
  if (ranks.length <= 1) {
    return 0;
  }
  const mid = Math.floor(ranks.length / 2);
  const left = ranks.slice(0, mid);
  const right = ranks.slice(mid);
  const a = sortCount(left);
  const b = sortCount(right);
  let cross = 0;
  let i = 0;
  let j = 0;
  let k = 0;
  while (i < left.length && j < right.length) {
    if (left[i] <= right[j]) {
      ranks[k++] = left[i++];
    } else {
      cross += ;
      ranks[k++] = right[j++];
    }
  }
  while (i < left.length) {
    ranks[k++] = left[i++];
  }
  while (j < right.length) {
    ranks[k++] = right[j++];
  }
  return a + b + cross;
}

Ejercicio

El informe diario

Resuélvelo en tu editor.

Pares intercambiados. Lee el orden de las entregas (los números prometidos, separados por espacios) e imprime cuántos pares están intercambiados y de cuántos. Usa sortCount de la lección.

3 1 2 6 4 5 10 7 9 8

Pares intercambiados: 8 de 45

Más tareas

Dibuja el árbol. Una función divide su entrada en tres partes iguales y se llama a sí misma con cada una, y su trabajo fuera de las llamadas es n. Dibuja los niveles: ¿cuántos hay, y cuál es el trabajo por nivel? ¿Y si son dos partes, pero el trabajo de cada llamada es n²?
Quién se retrasa más. Para cada pedido cuenta cuántos pedidos con un número mayor se entregaron antes. La suma de estos números es el número de inversiones. ¿Cómo los recoges mientras mezclas? Pista: cuando un número baja desde la derecha, los números sin tomar de la izquierda cuentan para él.
Si está casi ordenado. Cuenta las inversiones en un orden casi ordenado (dos pedidos vecinos intercambiados). ¿Cuántas comparaciones hace la mezcla? ¿Y el ordenamiento por inserción de los ordenamientos simples con la misma entrada?

Más precisamente

El teorema maestro y los otros lenguajes

El árbol de recursión funciona para cualquier divide y vencerás. Para el tipo más común también hay una regla lista.

Más precisamente, para curiosos

El teorema maestro, como intuición. Una función que divide su entrada en b partes iguales, hace a llamadas recursivas y un trabajo f(n) fuera de las llamadas se escribe T(n) = a · T(n/b) + f(n). Dibuja el árbol y compara el trabajo de arriba con el de abajo:

El trabajo es el mismo en cada nivel. Multiplicas por el número de niveles, log n. Ordenamiento por mezcla: T(n) = 2 · T(n/2) + n, n por nivel, O(n log n). Búsqueda binaria: T(n) = T(n/2) + 1, 1 por nivel, O(log n).
El trabajo se reduce hacia abajo. Decide el nivel de arriba. T(n) = 2 · T(n/2) + n² es O(n²): los niveles de abajo son n²/2, n²/4 y así sucesivamente, y su suma es menor que otro n².
El trabajo crece hacia abajo. Deciden las hojas. La multiplicación de Karatsuba de números grandes es T(n) = 3 · T(n/2) + n: tres mitades en cada nivel, el trabajo crece 3/2 por nivel, y la complejidad es de unos n^1,58 en lugar del n² de la multiplicación escolar.

La mala división T(n) = T(n − 1) + n no es de este tipo en absoluto: la entrada no se divide entre b, se reduce en uno. El teorema no ayuda ahí, pero el árbol sí: n niveles de unos n, O(n²).

Las matemáticas que hay detrás están en cualquier libro de algoritmos. Para el trabajo basta la imagen: cuántos niveles y cuánto trabajo por nivel.

Hasta dónde llega la recursión. La pila de llamadas es tan alta como los niveles del árbol. Contar mezclando son 17 niveles con 100 000 pedidos y cabe en todas partes. La mala división son n niveles.

Java, C# y JavaScript no tienen un límite para el número de niveles, pero su pila es de unos 1 MB. Con 100 000 llamadas anidadas también se agota, como en el quicksort con mal pivote. En Python el límite es de 1000 niveles, y la mala división se cae ya con unos 1000 pedidos.

Las inversiones como medida. El número de inversiones entre dos ordenaciones mide cuánto se diferencian: así se comparan rankings, por ejemplo los resultados de un buscador con las valoraciones de las personas. El ordenamiento por inserción hace exactamente tantos movimientos como inversiones tiene su entrada. Por eso es rápido con una entrada casi ordenada y lento con una mezclada.

Test

Ponte a prueba

1. El árbol de recursión de una función tiene log₂ n niveles, y el trabajo de cada nivel suma n. ¿Cuál es el coste?O(log n)O(n)O(n log n)

2. Una función se llama a sí misma una vez, con la mitad de su entrada, y hace un trabajo constante. ¿Cuál es el coste?O(n)O(log n)O(n log n)

3. Una función divide su entrada en los primeros n − 1 y el último, se llama a sí misma con los n − 1 y compara el último con todos los demás. ¿Cuál es el coste?O(n log n)O(n²)O(n)

4. Al mezclar, el número de la derecha es menor, y quedan 3 números de la izquierda sin tomar. ¿Cuántas inversiones suma esta toma?301

5. ¿Por qué el número de inversiones es un long y no un int en Java y C#?Porque mezclar solo funciona con longlong es más rápido que intCon 100 000 pedidos las inversiones pueden ser unos 2500 millones, y un int se queda en unos 2100 millones

Divide y vencerás y el árbol de recursión

Cookies