Divide y vencerás y el árbol de recursión
En resumen: Divide y vencerás divide un problema en partes más pequeñas del mismo tipo, las resuelve de forma recursiva y combina la respuesta; el árbol de recursión muestra el coste como niveles por trabajo de cada nivel.
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:
static long CountPairs(int[] ranks){ long inversions = 0; for (int i = 0; i < ranks.Length; i++) { for (int j = i + 1; j < ranks.Length; j++) { if (ranks[i] > ranks[j]) { inversions++; } } } return inversions;}int[] ranks = { 4, 1, 7, 3, 8, 2, 6, 5 };Console.WriteLine("Inversiones: " + CountPairs(ranks));Inversiones: 12Con 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:
static long SortCount(int[] ranks){ if (ranks.Length <= 1) { return 0; } int mid = ranks.Length / 2; int[] left = ranks[..mid]; int[] right = ranks[mid..]; long a = SortCount(left); long b = SortCount(right); long cross = 0; int i = 0, j = 0, 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.
int[] ranks = { 4, 1, 7, 3, 8, 2, 6, 5 };Console.WriteLine("Inversiones: " + SortCount(ranks));Console.WriteLine("Ordenado: [" + string.Join(", ", ranks) + "]");Inversiones: 12Ordenado: [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 C# la función puede devolver los dos resultados como una tupla,(int[] Sorted, long 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?
static long SortCount(int[] ranks){ if (ranks.Length <= 1) { return 0; } int mid = ranks.Length / 2; int[] left = ranks[..mid]; int[] right = ranks[mid..]; long a = SortCount(left); long b = SortCount(right); long cross = 0; int i = 0, j = 0, 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;}
int[] ranks = { 2, 4, 6, 1, 3, 5 };Console.WriteLine("Inversiones: " + SortCount(ranks));El 1 sale primero y cuenta los tres que quedan a la izquierda (2, 4, 6). Luego el 2 de la izquierda, el 3 de la derecha cuenta 4 y 6, el 4 de la izquierda, el 5 de la derecha cuenta 6, y por último el 6. La suma es 3 + 2 + 1 = 6. De los 15 pares, 6 están intercambiados.
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.
static long SortCount(int[] ranks){ if (ranks.Length <= 1) { return 0; } int mid = ranks.Length / 2; int[] left = ranks[..mid]; int[] right = ranks[mid..]; long a = SortCount(left); long b = SortCount(right); long cross = 0; int i = 0, j = 0, 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;}static int Find(int[] ranks, int target, int lo, int hi){ if (lo > hi) { return -1; } int mid = (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);}static long CountSlow(int[] ranks, int n){ if (n <= 1) { return 0; } long inv = CountSlow(ranks, n - 1); for (int i = 0; i < n - 1; i++) { if (ranks[i] > ranks[n - 1]) { inv++; } } return inv;}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.
int[] sorted = { 1, 2, 3, 4, 5, 6, 7, 8 };Console.WriteLine("Find: " + Find(sorted, 8, 0, sorted.Length - 1));int[] ranks = { 4, 1, 7, 3, 8, 2, 6, 5 };Console.WriteLine("CountSlow: " + CountSlow(ranks, ranks.Length));Console.WriteLine("SortCount: " + SortCount(ranks));Find: 7CountSlow: 12SortCount: 12La 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 |
static long SortCount(int[] ranks){ if (ranks.Length <= 1) { return 0; } int mid = ranks.Length / 2; int[] left = ranks[..mid]; int[] right = ranks[mid..]; long a = SortCount(left); long b = SortCount(right); long cross = 0; int i = 0, j = 0, 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:
static long checks = 0;static long comparisons = 0;
static int[] Deliveries(int n){ int[] ranks = new int[n]; for (int k = 0; k < n; k++) { ranks[k] = k + 1; } long x = 2026; for (int k = n - 1; k > 0; k--) { x = x * 48271 % 2147483647; int j = (int)(x % (k + 1)); (ranks[k], ranks[j]) = (ranks[j], ranks[k]); } return ranks;}
static long CountPairs(int[] ranks){ long inversions = 0; for (int i = 0; i < ranks.Length; i++) { for (int j = i + 1; j < ranks.Length; j++) { checks++; if (ranks[i] > ranks[j]) { inversions++; } } } return inversions;}
static long SortCount(int[] ranks){ if (ranks.Length <= 1) { return 0; } int mid = ranks.Length / 2; int[] left = ranks[..mid]; int[] right = ranks[mid..]; long a = SortCount(left); long b = SortCount(right); long cross = 0; int i = 0, j = 0, 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;}
foreach (int n in new[] { 10, 1000 }){ checks = 0; long inv = CountPairs(Deliveries(n)); Console.WriteLine($"por pares, n = {n}: {checks} comprobaciones, {inv} inversiones");}foreach (int n in new[] { 10, 1000, 100000 }){ comparisons = 0; long inv = SortCount(Deliveries(n)); Console.WriteLine($"por mezcla, n = {n}: {comparisons} comparaciones, {inv} inversiones");}por pares, n = 10: 45 comprobaciones, 14 inversionespor pares, n = 1000: 499500 comprobaciones, 249193 inversionespor mezcla, n = 10: 21 comparaciones, 14 inversionespor mezcla, n = 1000: 8693 comparaciones, 249193 inversionespor mezcla, n = 100000: 1536329 comparaciones, 2504458463 inversionesint se queda en 2 147 483 647. Por eso los contadores son long. Con int el número daría la vuelta y saldría negativo, sin ningún 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:
int[] ranks = { 4, 1, 7, 3, 8, 2, 6, 5 };Console.WriteLine("Inversiones: " + SortCount(ranks));Console.WriteLine("Ordenado: [" + string.Join(", ", ranks) + "]");Inversiones: 5Ordenado: [1, 2, 3, 4, 5, 6, 7, 8]¿En qué línea está el error?
Elige la línea con el error.
La función devuelve solo cross: los pares entre las mitades de esta llamada. Las inversiones dentro de la mitad izquierda (a) y de la mitad derecha (b) las contó la recursión, pero aquí se tiran. Así solo suben los pares de la última mezcla, 5. Divide y vencerás construye la respuesta con las tres partes: a + b + cross.
Pruébalo
Completa
El número de la derecha es menor y baja. ¿Cuánto crece cross?
static long SortCount(int[] ranks)
{
if (ranks.Length <= 1)
{
return 0;
}
int mid = ranks.Length / 2;
int[] left = ranks[..mid];
int[] right = ranks[mid..];
long a = SortCount(left);
long b = SortCount(right);
long cross = 0;
int i = 0, j = 0, 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;
}La mitad izquierda está ordenada, e i apunta al primer número sin tomar de ella. Todos desde i hasta el final son mayores que el de la derecha y llegaron antes: son left.Length - i pares. Con cross++ contarías uno por toma y te perderías la mayoría.
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 8Pares intercambiados: 8 de 45Má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