Divide and Conquer
Divide and Conquer (divide y vencerás) es una técnica muy popular para resolver problemas algorítmicos. Ya hemos visto algunos métodos para abordar estas situaciones. La estrategia greedy toma en cada paso la opción que parece más ventajosa. La programación dinámica construye el estado actual basándose en los anteriores. En el caso de Divide and Conquer, el problema se separa en subproblemas más pequeños que se resuelven uno por uno, y luego se combinan los resultados al final. De esta manera, dividimos el problema en partes más pequeñas y vencemos (conquer) el problema inicial al reunir las soluciones de esos subproblemas.
Challenge
Imagina que tienes 512 números y dispones de 512 computadoras especializadas (muy pequeñas y diseñadas para una sola tarea) que únicamente pueden calcular y devolver el máximo de dos números.
Deseas encontrar el valor máximo entre esos 512 números en el menor tiempo posible.
Cada computadora puede recibir dos números y, en 1 segundo, responder cuál de los dos es mayor (sí, son un poco lentas 🐌). ¿Puedes idear un algoritmo que permita calcular el máximo de todos esos números lo más rápido posible?