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 divide 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 botánicas, 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 dividir 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 el 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 siguen son los siguientes:
Divide recursivamente el grupo a la mitad. Esto continúa hasta que los subgrupos tienen tamaño 1 o 0.
- Conquista ordenando estos subgrupos.
- Combina los subgrupos ya ordenados.
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.
Fuente: Divide y vencerás
No hay comentarios.:
Publicar un comentario