¿Qué son los algoritmos de divide y vencerás? (Y no, no es "Divide y conviene")
Divide and Conquer es un paradigma algorítmico (a veces llamado erróneamente "Divide and Concur", un nombre divertido y apropiado), similar a la programación codiciosa y dinámica. Un algoritmo típico de Divide and Conquer resuelve un problema mediante los siguientes tres pasos.
- Dividir : Divida el problema dado en subproblemas del mismo tipo. Este paso implica dividir el problema en subproblemas más pequeños. Los subproblemas deben representar una parte del problema original. Este paso generalmente toma un enfoque recursivo para dividir el problema hasta que ningún subproblema sea más divisible. En esta etapa, los subproblemas se vuelven de naturaleza atómica pero aún representan una parte del problema real.
- Conquistar : resuelve estos subproblemas de forma recursiva. Este paso recibe muchos subproblemas más pequeños que deben resolverse. Generalmente, en este nivel, los problemas se consideran "resueltos" por sí mismos.
- Combinar : combine adecuadamente las respuestas. Cuando se resuelven los subproblemas más pequeños, esta etapa los combina recursivamente hasta que formulan una solución del problema original. Este enfoque algorítmico funciona de forma recursiva y los pasos de conquistar y fusionar funcionan tan cerca que parecen uno solo.
Este método suele permitirnos reducir en gran medida la complejidad del tiempo.
Por ejemplo, Bubble Sort usa una complejidad de O(n^2), mientras que quicksort (una aplicación de Divide And Conquer) reduce la complejidad de tiempo a O(nlog(n)). La búsqueda lineal tiene complejidad temporal O(n), mientras que la búsqueda binaria (una aplicación de Divide And Conquer) reduce la complejidad temporal a O(log(n)).
A continuación se muestran algunos algoritmos estándar que pertenecen a la variedad de algoritmos Divide and Conquer.
La búsqueda binaria es un algoritmo de búsqueda. En cada paso, el algoritmo compara el elemento de entrada (x) con el valor del elemento intermedio en la matriz. Si los valores coinciden, devuelve el índice del medio. De lo contrario, si x es menor que el elemento del medio, entonces el algoritmo se repite en el lado izquierdo del elemento del medio, de lo contrario, se repite en el lado derecho del elemento del medio.
Quicksort es un algoritmo de clasificación. El algoritmo elige un elemento pivote, reorganiza los elementos de la matriz de tal manera que todos los elementos más pequeños que el elemento pivote seleccionado se mueven hacia el lado izquierdo del pivote y todos los elementos mayores se mueven hacia el lado derecho. Finalmente, el algoritmo ordena recursivamente los subarreglos a la izquierda y a la derecha del elemento pivote.
Merge Sort es también un algoritmo de clasificación. El algoritmo divide la matriz en dos mitades, las ordena de forma recursiva y finalmente fusiona las dos mitades ordenadas. La complejidad temporal de este algoritmo es O(nLogn), en el mejor de los casos, en el caso medio o en el peor de los casos. Es tiempo de complejidad puede entenderse fácilmente a partir de las equipara recurrencia a: T(n) = 2T(n/2) + n.
El par de puntos más cercano El problema es encontrar el par de puntos más cercano en un conjunto de puntos en el plano xy. El problema se puede resolver a O(n^2)tiempo calculando las distancias de cada par de puntos y comparando las distancias para encontrar el mínimo. El algoritmo Divide and Conquer resuelve el problema a O(nLogn)tiempo.
El algoritmo de Strassen es un algoritmo eficiente para multiplicar dos matrices. Un método simple para multiplicar dos matrices necesita 3 bucles anidados y es O(n^3). El algoritmo de Strassen multiplica dos matrices en el O(n^2.8974)tiempo.
El algoritmo de Transformada Rápida de Fourier (FFT) de Cooley-Tukey es el algoritmo más común para FFT. Es un algoritmo de divide y vencerás que funciona en el O(nlogn)tiempo.
El algoritmo de Karatsuba fue el primer algoritmo de multiplicación asintóticamente más rápido que el algoritmo cuadrático de "escuela primaria". Reduce la multiplicación de dos números de n dígitos a un máximo de n ^ 1.585 (que es una aproximación del log de 3 en base 2) productos de un solo dígito. Por tanto, es más rápido que el algoritmo clásico, que requiere n ^ 2 productos de un solo dígito.
Dividir y conquistar (D & C) frente a programación dinámica (DP)
Ambos paradigmas (D & C y DP) dividen el problema dado en subproblemas y resuelven subproblemas. ¿Cómo elegir uno de ellos para un problema determinado? Se debe utilizar Divide and Conquer cuando los mismos subproblemas no se evalúan muchas veces. De lo contrario, se debe utilizar la programación dinámica o la memorización.
Por ejemplo, la búsqueda binaria es un algoritmo de dividir y conquistar, nunca volvemos a evaluar los mismos subproblemas. Por otro lado, para calcular el n-ésimo número de Fibonacci, debería preferirse la programación dinámica.