En el Módulo 2 aprendimos a medir algoritmos: sabemos calcular su coste temporal, su consumo de memoria y distinguir el mejor caso del peor. Pero medir no es crear. Cuando el equipo de RutaBus se enfrenta a un problema nuevo — encontrar la hora punta de una línea, detectar las dos paradas más próximas entre sí —, necesita algo más que un cronómetro: necesita estrategias de diseño, patrones probados para construir algoritmos desde cero. Esta lección inaugura el Módulo 3 con la primera y quizá más elegante de las cuatro grandes estrategias que anticipamos en 01-02: divide y vencerás (divide and conquer). La idea es engañosamente simple — partir el problema en trozos, resolver cada trozo y recomponer la solución — pero de ella nacen algunos de los algoritmos más eficientes jamás escritos.

1. El esquema general: dividir, conquistar, combinar
2. Cuándo aplica (y cuándo no)
3. Primer ejemplo RutaBus: la hora punta de una línea
4. Segundo ejemplo RutaBus: el par de paradas más cercanas en 1D
5. Razonar el coste: contar niveles de división
6. Algoritmos célebres de la estrategia

Divide y vencerás resuelve un problema de tamaño n mediante tres fases:

1. Dividir: partir la entrada en dos o más subproblemas del mismo tipo pero de menor tamaño (habitualmente dos mitades).
2. Conquistar: resolver cada subproblema recursivamente. Cuando el subproblema es tan pequeño que la respuesta es inmediata (una parada, una franja horaria), estamos en el caso base — el mismo concepto que estudiamos al ver recursividad en 01-02.
3. Combinar: fusionar las soluciones parciales en la solución del problema original.

Fíjate en que la recursión hace casi todo el trabajo por nosotros: nuestro esfuerzo de diseño se concentra en decidir cómo dividir y, sobre todo, cómo combinar. La fase de combinación es donde suelen esconderse tanto la genialidad como los errores.

No todo problema se deja trocear. Divide y vencerás funciona bien cuando se cumplen tres condiciones:

• Los subproblemas son del mismo tipo que el original. Buscar el máximo en media lista sigue siendo "buscar el máximo en una lista". Si al dividir el problema cambia de naturaleza, la recursión no encaja.
• Los subproblemas son independientes. Resolver la mitad izquierda no necesita nada de la mitad derecha. Esta condición es crucial: si los subproblemas se solapan (comparten trabajo), divide y vencerás repite cálculos y se vuelve ineficiente — ese escenario es justo el que resolverá la programación dinámica en 03-03.
• Combinar es más barato que resolver desde cero. Si fusionar las soluciones parciales cuesta tanto como el problema entero, no hemos ganado nada.

Empecemos con un ejemplo deliberadamente sencillo para fijar el esquema. RutaBus registra cuántos pasajeros suben en la línea L1 en cada franja de 15 minutos. El servicio de planificación quiere conocer la hora punta: el máximo de esa lista de conteos.

Ya sabríamos resolverlo con un bucle O(n), como hicimos con parada_mas_cercana en 01-01. Vamos a resolverlo ahora con divide y vencerás para ver el esquema en su forma más pura:

Desglosemos cada pieza:

• Caso base (inicio == fin): un rango de una sola franja no se puede dividir más; su máximo es trivial. Sin este caso la recursión no terminaría — recuerda la propiedad de finitud de Knuth (01-01).
• Dividir: calculamos medio y obtenemos dos rangos, [inicio..medio] y [medio+1..fin]. Observa que pasamos índices en lugar de hacer slices (conteos[:medio]): en 02-01 vimos que cada slice copia datos y cuesta O(k); con índices, la división es O(1).
• Conquistar: dos llamadas recursivas, cada una sobre la mitad de las franjas.
• Combinar: una única comparación, O(1).

La ejecución sobre las 8 franjas forma un árbol de llamadas:

Una confesión importante: este algoritmo hace exactamente n − 1 comparaciones, las mismas que el bucle lineal. Aquí divide y vencerás no gana nada en tiempo (y además consume pila de recursión, como analizamos en 02-02). Lo hemos usado porque muestra el esquema con total claridad. La ganancia real aparece cuando dividir nos permite evitar trabajo, como en el siguiente ejemplo.

En 02-01 escribimos pares_conectables, que comparaba todas las parejas de paradas: O(n²). Un problema hermano: el equipo de infraestructura quiere detectar las dos paradas más próximas entre sí de una avenida (si están demasiado juntas, probablemente una sobre). Simplificamos a 1D: cada parada queda representada por su kilómetro sobre la avenida.

La fuerza bruta compararía las n(n−1)/2 parejas — la suma aritmética que dedujimos en 02-01 —: O(n²). Divide y vencerás lo baja a O(n log n):

Puntos clave:

• La fase de combinar ya no es trivial: la mejor pareja podría tener una parada en cada mitad. Gracias a la ordenación previa, basta examinar una pareja fronteriza, no todas las cruzadas.
• El caso base devuelve float("inf") ("infinito"): un valor neutro que nunca gana a un min. Es un patrón muy habitual para "aquí no hay solución".
• Siendo honestos: con la lista ya ordenada, un simple recorrido de parejas adyacentes también resolvería esto en O(n). Usamos la versión recursiva porque (a) ilustra una combinación no trivial y (b) es la antesala directa del problema real en 2D (paradas sobre un mapa), donde el recorrido lineal ya no existe y divide y vencerás mantiene exactamente esta estructura.

¿Cómo se analiza un algoritmo que se llama a sí mismo dos veces? En 02-01 contamos llamadas recursivas una a una; con divide y vencerás hay un método más cómodo: contar niveles.

Cada nivel de recursión divide el tamaño por 2: n → n/2 → n/4 → … → 1. La pregunta "¿cuántas veces puedo dividir n entre 2 hasta llegar a 1?" tiene por respuesta, precisamente, log₂ n — la misma intuición que asociamos a O(log n) en la jerarquía de 01-03.

El coste total se estima así:

coste total ≈ (número de niveles) × (trabajo por nivel)

Dos lecturas de esta tabla:

• En maximo_pasajeros, cada llamada combina en O(1); el árbol tiene unos 2n − 1 nodos en total, así que el coste es O(n). Por eso no mejoraba al bucle: el trabajo lo mandan las hojas.
• Cuando combinar cuesta O(n) por nivel, tenemos O(n) de trabajo en cada uno de los log₂ n niveles: O(n log n), la complejidad estrella de los buenos algoritmos de ordenación.

Este segundo patrón se escribe formalmente como la recurrencia T(n) = 2·T(n/2) + O(n): "el coste para tamaño n es el de dos subproblemas de tamaño n/2 más un trabajo lineal de combinación". Resolveremos esta recurrencia con todo rigor cuando analicemos merge sort en 04-03; por ahora, quédate con el método de los niveles, que da la respuesta correcta en los casos habituales.

Divide y vencerás es la partida de nacimiento de varios clásicos que estudiaremos, ya con implementación completa, en el Módulo 4:

No los implementaremos aquí: en este módulo nos interesa la estrategia; en el Módulo 4, los clásicos que engendró.

• Olvidar el caso base o definirlo mal. Un rango vacío o de un elemento debe cortarse en seco. Prueba siempre tu función con n = 0, n = 1 y n = 2 antes que con listas grandes.
• Dividir con slices en lugar de índices. lista[:medio] copia O(k) elementos en cada nivel (coste oculto de 02-01) y dispara la memoria (02-02). Pasa inicio y fin.
• Errores de ±1 en la frontera. Si las mitades fueran [inicio..medio] y [medio..fin] (con medio repetido), la recursión podría no reducir el tamaño y no terminar nunca. Verifica que ambas mitades son estrictamente más pequeñas que el rango original.
• Ignorar las soluciones que cruzan la frontera. En distancia_minima, olvidar la pareja fronteriza produce resultados incorrectos silenciosos. Al diseñar la combinación pregúntate siempre: "¿puede la solución tener un pie en cada mitad?".
• Aplicar la estrategia por inercia. Si combinar no abarata nada (caso del máximo), un bucle simple es mejor: igual de rápido, más legible y sin gastar pila de recursión.

Escribe total_pasajeros(conteos, inicio, fin) que sume los pasajeros de un rango de franjas usando divide y vencerás. Identifica su caso base y sus tres fases, y razona su coste total contando niveles. ¿Gana algo respecto a sum(conteos)?

RutaBus quiere la franja valle (mínimo de pasajeros) y la hora punta (máximo) a la vez. Escribe min_y_max(conteos, inicio, fin) que devuelva la tupla (minimo, maximo) con una sola pasada de divide y vencerás.

En distancia_minima, ¿por qué es imprescindible que la lista esté ordenada para que la combinación pueda mirar una sola pareja? Construye una lista desordenada concreta con la que el algoritmo, aplicado sin ordenar antes, devuelva un resultado incorrecto.

Solución 1

Combinar cuesta O(1); como en maximo_pasajeros, el árbol tiene ~2n nodos y el coste total es O(n). No gana nada frente a sum (también O(n)) y encima consume O(log n) de pila (02-02). Buen ejercicio de esquema; mala idea en producción.

Solución 2

La gracia está en que cada llamada devuelve las dos respuestas a la vez y la combinación sigue siendo O(1); el coste total es O(n). (Dato curioso: refinando el caso base para que procese parejas — comparar los dos elementos una vez y decidir quién compite por el mínimo y quién por el máximo —, esta estructura baja a ~1,5n comparaciones frente a las ~2n de calcular mínimo y máximo por separado.)

Solución 3

La combinación solo mira la pareja (kms[medio], kms[medio+1]) porque, con la lista ordenada, cualquier otra pareja cruzada está más separada: los elementos de la izquierda son todos ≤ kms[medio] y los de la derecha todos ≥ kms[medio+1]. Sin orden, esa garantía desaparece. Contraejemplo: [0.3, 5.1, 0.4, 9.0]. Las mitades dan 4.8 (izquierda: |5.1−0.3|) y 8.6 (derecha: |9.0−0.4|), y la pareja fronteriza es |0.4−5.1| = 4.7. El algoritmo devolvería 4.7, pero la respuesta real es |0.4−0.3| = 0.1 — una pareja cruzada que la frontera no ve.

Divide y vencerás nos ha dado nuestro primer molde de diseño: dividir el problema en subproblemas independientes del mismo tipo, conquistarlos recursivamente desde un caso base sólido y combinar sus respuestas — la fase donde vive la verdadera dificultad. Hemos aprendido a estimar su coste contando niveles (log₂ n divisiones) y hemos comprobado, con la hora punta de la L1, que la estrategia solo compensa cuando dividir ahorra trabajo, como en el par de paradas más cercanas (de O(n²) a O(n log n)). Los frutos más famosos del molde — búsqueda binaria, merge sort, quick sort — nos esperan en el Módulo 4. Pero antes hay que conocer al resto de la familia. Divide y vencerás resuelve todos los subproblemas y luego decide; la siguiente estrategia es mucho más impaciente: toma en cada paso la decisión que ahora mismo parece mejor y jamás vuelve atrás. A veces esa audacia produce algoritmos óptimos y velocísimos; otras veces, desastres silenciosos. Son los algoritmos greedy, y aprender a distinguir cuándo funcionan es el objetivo de la próxima lección.