Algoritmo divide y vencerás
En informática , divide y vencerás es un paradigma de diseño de algoritmos . Un algoritmo de divide y vencerás descompone recursivamente un problema en dos o más subproblemas del mismo tipo o relacionados, hasta que se vuelven lo suficientemente simples como para resolverlos directamente. Las soluciones a los subproblemas luego se combinan para dar una solución al problema original.
La técnica divide y vencerás es la base de algoritmos eficientes para muchos problemas, como clasificación (p. ej., ordenación rápida , ordenación por fusión ), multiplicación de números grandes (p. ej., el algoritmo de Karatsuba ), búsqueda del par de puntos más cercano , análisis sintáctico ( por ejemplo, analizadores de arriba hacia abajo ), y calcular la transformada discreta de Fourier ( FFT ). [1]
Diseñar algoritmos eficientes de divide y vencerás puede ser difícil. Como en la inducción matemática , a menudo es necesario generalizar el problema para que sea susceptible de una solución recursiva. La corrección de un algoritmo divide y vencerás generalmente se prueba mediante inducción matemática, y su costo computacional a menudo se determina resolviendo relaciones de recurrencia .
El paradigma divide y vencerás se utiliza a menudo para encontrar una solución óptima de un problema. Su idea básica es descomponer un problema dado en dos o más subproblemas similares, pero más simples, para resolverlos a su vez y componer sus soluciones para resolver el problema dado. Los problemas de suficiente sencillez se resuelven directamente. Por ejemplo, para ordenar una lista dada de n números naturales, divídala en dos listas de alrededor de n /2 números cada una, ordene cada uno de ellos por turno e intercale ambos resultados apropiadamente para obtener la versión ordenada de la lista dada (vea la imagen). Este enfoque se conoce como el algoritmo de clasificación por fusión .
El nombre "divide y vencerás" a veces se aplica a los algoritmos que reducen cada problema a un solo subproblema, como el algoritmo de búsqueda binaria para encontrar un registro en una lista ordenada (o su análogo en computación numérica , el algoritmo de bisección para raíz ). encontrar ). [2] Estos algoritmos se pueden implementar de manera más eficiente que los algoritmos generales de divide y vencerás; en particular, si usan recursión de cola , se pueden convertir en bucles simples. Sin embargo, según esta definición amplia, todo algoritmo que utilice recursividad o bucles podría considerarse como un "algoritmo de divide y vencerás". Por ello, algunos autores consideran que la denominación "divide y vencerás" debe utilizarse sólo cuando cada problema pueda generar dos o más subproblemas. [3] En cambio, se ha propuesto el nombre disminuir y conquistar para la clase de un solo subproblema. [4]
Una aplicación importante de divide y vencerás está en la optimización, [ ejemplo necesario ] donde si el espacio de búsqueda se reduce ("poda") por un factor constante en cada paso, el algoritmo general tiene la misma complejidad asintótica que el paso de poda, con el constante en función del factor de poda (sumando la serie geométrica ); esto se conoce como podar y buscar .
