TechCodeview

Divide and Conquer es un patrón algorítmico. En los métodos algorítmicos, el diseño consiste en disputar una entrada enorme, dividir la entrada en partes menores, decidir el problema en cada una de las partes pequeñas y luego fusionar las soluciones por partes en una solución global. Este mecanismo de solución del problema se llama estrategia Divide & Conquer.

El algoritmo Divide and Conquer consiste en una disputa mediante los siguientes tres pasos.

Dividirel problema original en un conjunto de subproblemas.Conquistar:Resuelva cada subproblema de forma individual y recursiva.Combinar:Reúna las soluciones de los subproblemas para obtener la solución al problema completo.

Generalmente podemos seguir el divide y conquistaras enfoque en un proceso de tres pasos.

Ejemplos: Los algoritmos informáticos específicos se basan en el enfoque Divide & Conquer:

1. Problema máximo y mínimo
2. Búsqueda binaria
3. Clasificación (clasificación por combinación, clasificación rápida)
4. Torre de Hanoi.

Fundamentos de la estrategia Divide & Conquer:

Hay dos fundamentos de la estrategia Divide & Conquer:

1. Fórmula relacional
2. Condición de parada

1. Fórmula relacional: Es la fórmula que generamos a partir de la técnica dada. Después de generar la Fórmula, aplicamos la Estrategia D&C, es decir, dividimos el problema de forma recursiva y resolvemos los subproblemas rotos.

2. Condición de parada: Cuando solucionamos el problema usando la estrategia Divide & Conquer, entonces necesitamos saber durante cuánto tiempo debemos aplicar Divide & Conquer. Entonces, la condición en la que es necesario detener nuestros pasos recursivos de D&C se denomina condición de detención.

Aplicaciones del enfoque divide y vencerás:

Los siguientes algoritmos se basan en el concepto de la técnica divide y vencerás:

Búsqueda binaria:El algoritmo de búsqueda binaria es un algoritmo de búsqueda, que también se denomina búsqueda de medio intervalo o búsqueda logarítmica. Funciona comparando el valor objetivo con el elemento medio existente en una matriz ordenada. Después de hacer la comparación, si el valor difiere, entonces la mitad que no puede contener el objetivo eventualmente se eliminará, y luego se continuará la búsqueda en la otra mitad. Consideraremos nuevamente el elemento medio y lo compararemos con el valor objetivo. El proceso continúa repitiéndose hasta que se alcanza el valor objetivo. Si encontramos que la otra mitad está vacía después de finalizar la búsqueda, entonces se puede concluir que el objetivo no está presente en la matriz.Ordenación rápida:Es el algoritmo de clasificación más eficiente, también conocido como clasificación por intercambio de particiones. Comienza seleccionando un valor de pivote de una matriz y luego dividiendo el resto de los elementos de la matriz en dos submatrices. La partición se realiza comparando cada uno de los elementos con el valor de pivote. Compara si el elemento tiene un valor mayor o menor que el pivote y luego ordena las matrices de forma recursiva.Combinar orden:Es un algoritmo de clasificación que clasifica una matriz mediante comparaciones. Comienza dividiendo una matriz en submatriz y luego ordena recursivamente cada una de ellas. Una vez realizada la clasificación, los vuelve a fusionar.Par de puntos más cercano:Es un problema de geometría computacional. Este algoritmo enfatiza encontrar el par de puntos más cercano en un espacio métrico, dados n puntos, de modo que la distancia entre el par de puntos debe ser mínima.Algoritmo de Strassen:Es un algoritmo para la multiplicación de matrices, que lleva el nombre de Volker Strassen. Ha demostrado ser mucho más rápido que el algoritmo tradicional cuando trabaja con matrices grandes.Algoritmo de transformada rápida de Fourier (FFT) de Cooley-Tukey:El algoritmo de Transformada Rápida de Fourier lleva el nombre de J. W. Cooley y John Turkey. Sigue el enfoque divide y vencerás e impone una complejidad de O(nlogn).Algoritmo de Karatsuba para multiplicación rápida:Es uno de los algoritmos de multiplicación más rápidos de la época tradicional, inventado por Anatoly Karatsuba a finales de 1960 y publicado en 1962. Multiplica dos números de n dígitos de tal manera que los reduce a un solo dígito como máximo.

Ventajas de divide y vencerás

• Divide y Conquistarás suelen resolver con éxito uno de los mayores problemas, como es el de la Torre de Hanoi, un rompecabezas matemático. Es un desafío resolver problemas complicados para los cuales no tienes una idea básica, pero con la ayuda del enfoque de divide y vencerás, se ha reducido el esfuerzo ya que se trabaja para dividir el problema principal en dos mitades y luego resolverlas de forma recursiva. Este algoritmo es mucho más rápido que otros algoritmos.
• Utiliza eficientemente la memoria caché sin ocupar mucho espacio porque resuelve subproblemas simples dentro de la memoria caché en lugar de acceder a la memoria principal más lenta.
• Es más competente que su contraparte, la técnica Brute Force.
• Dado que estos algoritmos inhiben el paralelismo, éste no implica ninguna modificación y es manejado por sistemas que incorporan procesamiento paralelo.

Desventajas de divide y vencerás

• Dado que la mayoría de sus algoritmos están diseñados incorporando recursividad, requiere una alta gestión de la memoria.
• Una pila explícita puede abusar del espacio.
• Incluso podría bloquear el sistema si la recursividad se realiza con mayor precisión que la pila presente en la CPU.