"¡Divide y vencerás!" es una expresión tan mundana como cierta. Cuando no podemos abordar un problema sin más porque el volumen de datos es demasiado elevado o el proceso demasiado complejo, siempre podemos recurrir a la estrategia de subdividirlo en problemas menores, más manejables e independientes, para finalmente integrarlos y conformar la solución final.
En el mundo de la algoritmia, Divide y Vencerás (Divide and Conquer, en inglés) es un esquema al que se ajustan multitud de problemas, algunos bien conocidos como la ordenación por mezcla (mergesort) o la ordenación rápida (quicksort). Por regla general, los algoritmos Divide y Vencerás pueden ser implementados cómodamente mediante recursividad aunque, como ya sabréis, cualquier algoritmo recursivo puede ser transformado a iterativo si fuese necesario. En cualquier caso, Divide y Vencerás se utiliza en muchas ocasiones para mejorar en cuanto a complejidad algorítmica problemas para los que ya existe una solución evidente utilizando otros esquemas. Por desgracia, casi siempre que buscamos eficiencia acabamos pagando el precio de la pérdida de claridad y simplicidad. Queda en nuestras manos determinar cuándo merece la pena y cuándo no.
Hoy os traigo unas diapositivas y apuntes introductorios, no demasiado avanzados, para introduciros en el tema. Como siempre, espero que os resulten de utilidad. Para descargarlos tenéis que entrar en SlideShare haciendo clic en el icono de los "muñecos" en la parte inferior derecha de cada panel.
En el mundo de la algoritmia, Divide y Vencerás (Divide and Conquer, en inglés) es un esquema al que se ajustan multitud de problemas, algunos bien conocidos como la ordenación por mezcla (mergesort) o la ordenación rápida (quicksort). Por regla general, los algoritmos Divide y Vencerás pueden ser implementados cómodamente mediante recursividad aunque, como ya sabréis, cualquier algoritmo recursivo puede ser transformado a iterativo si fuese necesario. En cualquier caso, Divide y Vencerás se utiliza en muchas ocasiones para mejorar en cuanto a complejidad algorítmica problemas para los que ya existe una solución evidente utilizando otros esquemas. Por desgracia, casi siempre que buscamos eficiencia acabamos pagando el precio de la pérdida de claridad y simplicidad. Queda en nuestras manos determinar cuándo merece la pena y cuándo no.
Hoy os traigo unas diapositivas y apuntes introductorios, no demasiado avanzados, para introduciros en el tema. Como siempre, espero que os resulten de utilidad. Para descargarlos tenéis que entrar en SlideShare haciendo clic en el icono de los "muñecos" en la parte inferior derecha de cada panel.
No hay comentarios:
Publicar un comentario