¿Qué son los algoritmos "divide y vencerás"? (Y no, no es divide y concurrir)
Divide y vencerás es un paradigma algorítmico (a veces llamado por error Divide y Concurrir - una adaptación en broma), similar a los paradigmas de programación Dinámica y Algoritmos ávidos o glotones. Un algoritmo Divide y Vencerás típico resuelve un problema siguiendo estos 3 pasos.
- Dividir: Descomponer el problema en sub-problemas del mismo tipo. Este paso involucra descomponer el problema original en pequeños sub-problemas. Cada sub-problema debe representar una parte del problema original. Por lo general, este paso emplea un enfoque recursivo para dividir el problema hasta que no es posible crear un sub-problema más.
- Vencer: Resolver los sub-problemas recursivamente. Este paso recibe un gran conjunto de sub-problemas a ser resueltos. Generalmente a este nivel, los problemas se resuelven por sí solos.
- Combinar: Combinar las respuestas apropiadamente. Cuando los sub-problemas son resueltos, esta fase los combina recursivamente hasta que estos formulan la solución al problema original. Este enfoque algorítmico trabaja recursivamente y los pasos de conquista y fusión trabajan tan a la par que parece un sólo paso.
Usualmente este método nos permite hacer una reducción bastante significativa en la complejidad tiempo del algoritmo a emplear.
Por ejemplo, el método de la burbuja conlleva una complejidad de O(n^2), mientras que el quicksort (una aplicación de Dividir y Vencer) reduce la complejidad a O(nlog(n)). La búsqueda linear tiene una complejidad de O(n), mientras que la búsqueda binaria(otra aplicación de dividir y vencer) reduce la complejidad a O(log(n)).
A continuación algunos de los algoritmos estándar de la variedad dividir y vencer
Búsqueda Binaria, es un algoritmo de búsqueda. En cada paso, el algoritmo compara el parámetro de entrada (x) con el valor del elemento en la mitad del arreglo. Si los valores coinciden, retorna el índice del elemento medio. De lo contrario, si x es mejor al elemento medio, el algoritmo recurre a la mitad izquierda del elemento medio, de lo contrario retorna la mitad a la derecha del elemento medio.
Quicksort, es un algoritmo de ordenamiento. El algoritmo elige un elemento pivote, reordena los elementos del arreglo de forma que todos los elementos de menor valor al del elemento pivote se mueven hacia su izquierda y los elementos de mayor valor hacia su derecha. Finalmente, el algoritmo ordena los sub-arreglos recursivamente hacia la izquierda y derecha del elemento pivote.
Merge Sort, es también un algoritmo de ordenamiento. Este algoritmo divide el arreglo en dos partes, ordenada cada una de ellas recursivamente, y finalmente une las dos partes ya ordenadas. El tiempo de complejidad de este algoritmo es de O(nLogn), en el mejor caso, caso medio y en el peor de los casos. La complejidad de tiempo puede ser entendida fácilmente recurriendo a la ecuación: T(n) = 2T(n/2) + n.
Par de puntos más cercanos, El problema es encontrar el par de puntos más cercano a otra par dado en el plano XY. Este problema puede ser resuelto en un tiempo O(n^2) calculando la distancia de cada par de puntos y comparando las distancias hasta encontrar la menor. El algoritmo de tipo Dividir y Vencer resuelve este problema en un tiempo O(nLogn).
Algoritmo de Strassen es un algoritmo eficiente para multiplicar dos matrices. Un método simple para multiplicar dos matrices requiere 3 bucles anidados lo que nos da una complejidad de O(n^3). El algoritmo de Strassen multiplica dos matrices en un tiempo de O(n^2.8974).
El Algoritmo Cooley–Tukey de Transformación Rápida de Fourier (FFT) es el algoritmo más común de FFT (Transformación Rápida de Fourier en inglés). Es un algoritmo de tipo Dividir y Vencer que opera en un tiempo de O(nlogn).
El algortimo de Karatsuba, este fue el primer algoritmo de multiplicación más rápido asintóticamente que el algoritmo cuadrático clásico de multiplicación. Este algoritmo consigue reducir la multiplicación de dos números de n dígitos a como máximo de n^1.585( que es la aproximación del logaritmo de 3 en base 2) multiplicaciones de un dígito. Por lo tanto es más rápido que el algoritmo clásico que requiere el producto de n^2 de números de un dígito.
Dividir y vencer (D & V) vs programación dinámica (DP)
Ambos paradigmas (D & V y PD) dividen un problema cualquiera en sub problema y resuelve cada uno de ellos. ¿Cómo elegir uno de ellos para un problema? Dividir y Vencer debe ser empleado cuando los sub problemas no son evaluados muchas veces. De lo contrario programación dinámica o memoización debería emplearse en su lugar.
Por ejemplo, la Búsqueda Binaria es un algoritmo Dividir y Vencer, nunca evaluaremos los sub problema más de una vez. Por otro lado, el cálculo del Número Fibonacci se debe preferir la aplicación de Programación Dinámica.
Traducción del Artículo - Divide and Conquer Algorithm Meaning: Explained with Examples