Divide y Vencerás
Algunos de los algoritmos más famosos son aquellos que usan la estrategia de divide y vencerás. Quizá se deba al nombre tan llamativo que tienen y a la forma tan intuitiva de implementarlos. Sea cual sea la razón es importante saber qué son y cómo funcionan.
¿Qué es Divide y Vencerás?
La definición más popular es la siguiente (extraída de wikipedia):
El método está basado en la resolución recursiva de un problema dividiéndolo en dos o más subproblemas de igual tipo o similar. El proceso continúa hasta que éstos llegan a ser lo suficientemente sencillos como para que se resuelvan directamente. Al final, las soluciones a cada uno de los subproblemas se combinan para dar una solución al problema original.
En pocas palabras:
Divide y vencerás es una estrategia de diseño de algoritmos en la que divides un problema en problemas más pequeños hasta que sean fáciles de resolver. Al final las soluciones se combinan para obtener el resultado al problema original.
¿Cómo funciona?
Más que memorizar una definición que pueden encontrar con google en dos minutos creo que es importante entender su funcionamiento.
Imaginemos un escenario del mundo real: hacer una fiesta en tu casa!
Pensar en el hecho de organizar una fiesta enorme puede resultar un poco abrumador. Es muy fácil que se nos olvide algo si solo dejamos así.
¿Qué harían ustedes?
Quiero pensar que harían una lista (ya sea mental o en una aplicación) de lo que deben de tener para que su fiesta sea un rotundo éxito. Esto incluye, pero no está limitado a lo siguiente:
- Comprar las bebidas
- Comprar las botanas
- Invitar a los amigos
- Poner la música.
El siguiente paso sería realizar cada una de estas tareas: ir al centro comercial por las bebidas y botanas, llamar y/o mandar whatsapp a los amigos y poner el ambiente en tu casa con la música.
¡Una vez que tenemos todas estas cosas las juntamos en nuestra casa y se arma nuestra fiesta!
Podrán observar que seguimos los pasos de divide y vencerás:
- Identificamos nuestro problema/objetivo: organizar la fiesta.
- Dividimos el problema en partes más pequeñas: comprar cosas, invitar amigos, poner música, etc.
- Resolvimos los problemas más pequeños: fuimos al centro comercial, pusimos la ambiente en nuestra casa, etc.
- Juntamos todo para resolver nuestro problema original.
En la programación…
En las ciencias computacionales usamos esta estrategia de forma muy similar a lo que vimos para armar nuestra fiesta. Como ejemplo utilizaremos el método de ordenamiento merge sort.
Merge sort es un algoritmo que nos ayuda a ordenar elementos en un grupo como arreglos o listas ligadas.
Los pasos que sigue son los siguientes:
- Divide recursivamente el grupo a la mitad. Esto continua hasta que los subgrupos tienen tamaño 1 o 0.
- Conquista ordenando estos subgrupos.
- Combina los subgrupos ya ordenados.
No quiero meterme mucho en detalles ya que el propósito de este artículo es explicar cómo funcionan estos algoritmos en general y no para este caso particular. Posteriormente les explicare cómo funcionan los algoritmos de ordenamiento más populares como bublesort, mergesort y quicksort.
Pero si quieren adelantarse un poco aquí les dejo un video de youtube que me parece particularmente bueno.
En conclusión…
Divide y vencerás es una estrategia ampliamente utilizada para resolver problemas computacionales que utilizan recursivad. Saber cómo funciona es esencial para crecer como desarrolladores.
Vimos también como las cosas que aprendemos sobre algoritmos no solo se utilizan frente a la computadora sino en nuestra vida diaria.
¿Se les ocurre alguna situación cotidiana en la que puedan usar la estrategia divide y vencerás?
Si te gusto este articulo compártelo con tus amigos y considera suscribirte a mi lista. Un escritor no es nada sin sus lectores :D
