En este artículo, vamos a discutir cómo la técnica Divide and Conquer es útil y cómo podemos resolver el problema con el enfoque de la técnica DAC. En esta sección, discutiremos los siguientes temas.
1. Introduction to DAC. 2. Algorithms under DAC techniques. 3. Recurrence Relation for DAC algorithm. 4. Problems using DAC technique.
Divide y vencerás
Esta técnica se puede dividir en las siguientes tres partes:
- Dividir: Esto implica dividir el problema en subproblemas más pequeños.
- Conquistar: resuelve subproblemas llamando recursivamente hasta que se resuelva.
- Combinar: combine los subproblemas para obtener la solución final de todo el problema.
Los siguientes son algunos algoritmos estándar que siguen el algoritmo Divide and Conquer.
- Quicksort es un algoritmo de clasificación. El algoritmo elige un elemento pivote y reorganiza los elementos de la array para que todos los elementos más pequeños que el elemento pivote elegido se muevan hacia el lado izquierdo del pivote y todos los elementos más grandes se muevan hacia el lado derecho. Finalmente, el algoritmo ordena recursivamente los subarreglos a la izquierda y derecha del elemento pivote.
- Merge Sort es también un algoritmo de clasificación. El algoritmo divide la array en dos mitades, las ordena recursivamente y finalmente fusiona las dos mitades ordenadas.
- 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 en tiempo O(n^2) 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 en tiempo O(N log N).
- El Algoritmo de Strassen es un algoritmo eficiente para multiplicar dos arrays. Un método simple para multiplicar dos arrays necesita 3 ciclos anidados y es O(n^3). El algoritmo de Strassen multiplica dos arrays en O(n^2.8974) tiempo.
- El algoritmo Cooley-Tukey Fast Fourier Transform (FFT) es el algoritmo más común para FFT. Es un algoritmo de divide y vencerás que funciona en tiempo O(N log N).
- El algoritmo de Karatsuba para la multiplicación rápida realiza la multiplicación de dos números de n dígitos como máximo
multiplicaciones de un solo dígito en general (y exactamente 
cuando n es una potencia de 2). Es, por tanto, más rápido que el algoritmo clásico , que requiere n 2 productos de un solo dígito. Si n = 2 10 = 1024, en particular, las cuentas exactas son 3 10 = 59, 049 y (2 10 ) 2 = 1, 048, 576, respectivamente.
Lo que no califica como Divide y vencerás:
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 central en la array. 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 para el lado izquierdo del elemento del medio, de lo contrario se repite para el lado derecho del elemento del medio. Contrariamente a la creencia popular, este no es un ejemplo de Divide y vencerás porque solo hay un subproblema en cada paso (Divide y vencerás requiere que haya dos o más subproblemas) y, por lo tanto, este es un caso de Reducir y vencer. Conquistar.
Algoritmo divide y vencerás:
DAC(a, i, j)
{
if(small(a, i, j))
return(Solution(a, i, j))
else
m = divide(a, i, j) // f1(n)
b = DAC(a, i, mid) // T(n/2)
c = DAC(a, mid+1, j) // T(n/2)
d = combine(b, c) // f2(n)
return(d)
}
Relación de recurrencia para el algoritmo DAC:
esta es una relación de recurrencia para el programa anterior.
O(1) if n is small T(n) = f1(n) + 2T(n/2) + f2(n)
Ejemplo:
Para encontrar el elemento máximo y mínimo en una array dada.
Input: { 70, 250, 50, 80, 140, 12, 14 }
Output: The minimum number in a given array is : 12
The maximum number in a given array is : 250
Enfoque: encontrar el elemento máximo y mínimo de una array dada es una aplicación para dividir y vencer. En este problema, encontraremos los elementos máximo y mínimo en una array dada. En este problema, estamos utilizando un enfoque de divide y vencerás (DAC) que consta de tres pasos: divide, vencerás y combinarás.
Para Máximo:
en este problema, estamos usando el enfoque recursivo para encontrar el máximo donde veremos que solo quedan dos elementos y luego podemos usar fácilmente la condición, es decir, si (a [índice]> a [índice + 1].)
En una línea de programa, una condición [índice] y [índice + 1]) garantizará solo dos elementos a la izquierda.
if(index >= l-2)
{
if(a[index]>a[index+1])
{
// (a[index]
// Ahora, podemos decir que el último elemento será máximo en una array dada .
}
else
{
//(a[index+1]
// Ahora, podemos decir que el último elemento será máximo en una array dada.
}
}
En la condición anterior, hemos verificado la condición del lado izquierdo para encontrar el máximo. Ahora, veremos la condición del lado derecho para encontrar el máximo.
Función recursiva para verificar el lado derecho en el índice actual de una array.
máx = DAC_Max(a, índice+1, l);
// llamada recursiva
Ahora, compararemos la condición y verificaremos el lado derecho en el índice actual de una array dada.
En el programa dado, vamos a implementar esta lógica para verificar la condición en el lado derecho en el índice actual.
// El elemento derecho será máximo.
if(a[índice]>max)
devuelve a[índice];
// max será el elemento máximo en una array dada.
si no
devuelve max;
}
Para Mínimo:
En este problema, vamos a implementar el enfoque recursivo para encontrar el número mínimo. en una array dada.
int DAC_Min(int a[], int index, int l)
//Función de llamada recursiva para encontrar el número mínimo. en una array dada.
if(index >= l-2)
// para verificar la condición de que habrá dos elementos a la izquierda
, entonces podemos encontrar fácilmente el elemento mínimo en una array dada.
{
// aquí comprobaremos la condición
if(a[index]<a[index+1])
return a[index];
de lo contrario,
devuelve un [índice + 1];
}
Ahora, verificaremos la condición en el lado derecho en una array dada.
// Llamada recursiva para el lado derecho en la array dada.
min = DAC_Min(a, índice+1, l);
Ahora, verificaremos la condición para encontrar el mínimo en el lado derecho.
// El elemento derecho será mínimo
if(a[index]<min)
return a[index];
// Aquí min será mínimo en una array dada.
de lo contrario,
devuelve min;
Implementación:
C++
// C++ code to demonstrate Divide and
// Conquer Algorithm#include<iostream>
# include<iostream>
using namespace std;
// function to find the maximum no.
// in a given array.
int DAC_Max(int arr[], int index, int l)
{
int max;
if(index >= l - 2)
{
if(arr[index] > arr[index + 1])
return arr[index];
else
return arr[index + 1];
}
max = DAC_Max(arr, index + 1, l);
if(arr[index] > max)
return arr[index];
else
return max;
}
// Function to find the minimum no.
// in a given array
int DAC_Min(int arr[], int index, int l)
{
int min;
if(index >= l - 2)
{
if(arr[index] < arr[index + 1])
return arr[index];
else
return arr[index + 1];
}
min = DAC_Min(arr, index + 1, l);
if(arr[index] < min)
return arr[index];
else
return min;
}
// Driver code
int main()
{
int arr[] = {120, 34, 54, 32, 58, 11, 90};
int n = sizeof(arr) / sizeof(arr[0]);
int max, min;
max = DAC_Max(arr, 0, n);
min = DAC_Min(arr, 0, n);
cout << "Maximum: " << max << endl;
cout << "Minimum: " << min << endl;
return 0;
}
// This code is contributed by probinsah.
C
// C code to demonstrate Divide and
// Conquer Algorithm
#include <stdio.h>
int DAC_Max(int a[], int index, int l);
int DAC_Min(int a[], int index, int l);
// function to find the maximum no.
// in a given array.
int DAC_Max(int a[], int index, int l)
{
int max;
if (index >= l - 2) {
if (a[index] > a[index + 1])
return a[index];
else
return a[index + 1];
}
// logic to find the Maximum element
// in the given array.
max = DAC_Max(a, index + 1, l);
if (a[index] > max)
return a[index];
else
return max;
}
// Function to find the minimum no.
// in a given array.
int DAC_Min(int a[], int index, int l)
{
int min;
if (index >= l - 2) {
if (a[index] < a[index + 1])
return a[index];
else
return a[index + 1];
}
// Logic to find the Minimum element
// in the given array.
min = DAC_Min(a, index + 1, l);
if (a[index] < min)
return a[index];
else
return min;
}
// Driver Code
int main()
{
// Defining the variables
int min, max, N;
// Initializing the array
int a[7] = { 70, 250, 50, 80, 140, 12, 14 };
// recursion - DAC_Max function called
max = DAC_Max(a, 0, 7);
// recursion - DAC_Max function called
min = DAC_Min(a, 0, 7);
printf("The minimum number in a given array is : %d\n", min);
printf("The maximum number in a given array is : %d", max);
return 0;
}
// This code is contributed by Ashish Rana (GFG Team)
Java
// Java code to demonstrate Divide and
// Conquer Algorithm
class GFG{
// Function to find the maximum no.
// in a given array.
static int DAC_Max(int a[], int index, int l)
{
int max;
if (index >= l - 2)
{
if (a[index] > a[index + 1])
return a[index];
else
return a[index + 1];
}
// Logic to find the Maximum element
// in the given array.
max = DAC_Max(a, index + 1, l);
if (a[index] > max)
return a[index];
else
return max;
}
// Function to find the minimum no.
// in a given array.
static int DAC_Min(int a[], int index, int l)
{
int min;
if (index >= l - 2)
{
if (a[index] < a[index + 1])
return a[index];
else
return a[index + 1];
}
// Logic to find the Minimum element
// in the given array.
min = DAC_Min(a, index + 1, l);
if (a[index] < min)
return a[index];
else
return min;
}
// Driver Code
public static void main(String[] args)
{
// Defining the variables
int min, max;
// Initializing the array
int a[] = { 70, 250, 50, 80, 140, 12, 14 };
// Recursion - DAC_Max function called
max = DAC_Max(a, 0, 7);
// Recursion - DAC_Max function called
min = DAC_Min(a, 0, 7);
System.out.printf("The minimum number in " +
"a given array is : %d\n", min);
System.out.printf("The maximum number in " +
"a given array is : %d", max);
}
}
// This code is contributed by Princi Singh
C#
// C# code to demonstrate Divide and
// Conquer Algorithm
using System;
class GFG
{
// Function to find the maximum no.
// in a given array.
static int DAC_Max(int []a, int index, int l)
{
int max;
if (index >= l - 2)
{
if (a[index] > a[index + 1])
return a[index];
else
return a[index + 1];
}
// Logic to find the Maximum element
// in the given array.
max = DAC_Max(a, index + 1, l);
if (a[index] > max)
return a[index];
else
return max;
}
// Function to find the minimum no.
// in a given array.
static int DAC_Min(int []a, int index, int l)
{
int min;
if (index >= l - 2)
{
if (a[index] < a[index + 1])
return a[index];
else
return a[index + 1];
}
// Logic to find the Minimum element
// in the given array.
min = DAC_Min(a, index + 1, l);
if (a[index] < min)
return a[index];
else
return min;
}
// Driver Code
public static void Main(String[] args)
{
// Defining the variables
int min, max;
// Initializing the array
int []a = {70, 250, 50, 80, 140, 12, 14};
// Recursion - DAC_Max function called
max = DAC_Max(a, 0, 7);
// Recursion - DAC_Max function called
min = DAC_Min(a, 0, 7);
Console.Write("The minimum number in " +
"a given array is : {0}\n", min);
Console.Write("The maximum number in " +
"a given array is : {0}", max);
}
}
// This code contributed by shikhasingrajput
Python3
# Python3 code to demonstrate Divide and
# Conquer Algorithm
# Function to find the maximum no.
# in a given array.
def DAC_Max(a, index, l):
max = -1;
if (index >= l - 2):
if (a[index] > a[index + 1]):
return a[index];
else:
return a[index + 1];
# Logic to find the Maximum element
# in the given array.
max = DAC_Max(a, index + 1, l);
if (a[index] > max):
return a[index];
else:
return max;
# Function to find the minimum no.
# in a given array.
def DAC_Min(a, index, l):
min = 0;
if (index >= l - 2):
if (a[index] < a[index + 1]):
return a[index];
else:
return a[index + 1];
# Logic to find the Minimum element
# in the given array.
min = DAC_Min(a, index + 1, l);
if (a[index] < min):
return a[index];
else:
return min;
# Driver Code
if __name__ == '__main__':
# Defining the variables
min, max = 0, -1;
# Initializing the array
a = [70, 250, 50, 80, 140, 12, 14];
# Recursion - DAC_Max function called
max = DAC_Max(a, 0, 7);
# Recursion - DAC_Max function called
min = DAC_Min(a, 0, 7);
print("The minimum number in a given array is : ", min);
print("The maximum number in a given array is : ", max);
# This code is contributed by 29AjayKumar
Javascript
<script>
// Javascript code to demonstrate Divide and
// Conquer Algorithm
// Function to find the maximum no.
// in a given array.
function DAC_Max(a,index,l)
{
let max;
if (index >= l - 2)
{
if (a[index] > a[index + 1])
return a[index];
else
return a[index + 1];
}
// Logic to find the Maximum element
// in the given array.
max = DAC_Max(a, index + 1, l);
if (a[index] > max)
return a[index];
else
return max;
}
// Function to find the minimum no.
// in a given array.
function DAC_Min(a,index,l)
{
let min;
if (index >= l - 2)
{
if (a[index] < a[index + 1])
return a[index];
else
return a[index + 1];
}
// Logic to find the Minimum element
// in the given array.
min = DAC_Min(a, index + 1, l);
if (a[index] < min)
return a[index];
else
return min;
}
// Driver Code
let min, max;
let a=[70, 250, 50, 80, 140, 12, 14];
// Recursion - DAC_Max function called
max = DAC_Max(a, 0, 7);
// Recursion - DAC_Max function called
min = DAC_Min(a, 0, 7);
document.write("The minimum number in " +
"a given array is : ", min+"<br>");
document.write("The maximum number in " +
"a given array is : "+ max+"<br>");
// This code is contributed by rag2127
</script>
Maximum: 120 Minimum: 11
Divide y vencerás (D & C) vs 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 dado? Divide and Conquer debe usarse cuando los mismos subproblemas no se evalúan muchas veces. De lo contrario, se debe utilizar Programación Dinámica o Memoización. Por ejemplo, Quicksort es un algoritmo Divide and Conquer, nunca volvemos a evaluar los mismos subproblemas. Por otro lado, para calcular el n-ésimo número de Fibonacci, se debe preferir la Programación Dinámica (Ver esto para más detalles).
Complejidad temporal del algoritmo divide y vencerás:
T(n) = aT(n/b) + f(n),
where,
n = size of input
a = number of subproblems in the recursion
n/b = size of each subproblem. All subproblems are assumed to have the same size.
f(n) = cost of the work done outside the recursive call, which includes the cost of dividing the problem and cost of merging the solutions
Ventajas del algoritmo divide y vencerás:
- El problema difícil se puede resolver fácilmente.
- Divide todo el problema en subproblemas, por lo que se puede resolver en paralelo asegurando el multiprocesamiento.
- Utiliza eficientemente la memoria caché sin ocupar mucho espacio
- Reduce el tiempo de complejidad del problema.
Desventajas del algoritmo divide y vencerás:
- Implica recursividad, que a veces es lenta.
- La eficiencia depende de la implementación de la lógica.
- Puede bloquear el sistema si la recursividad se realiza rigurosamente.
Referencias
Algoritmos por Sanjoy Dasgupta, Christos Papadimitriou, Umesh Vazirani
Introducción a los algoritmos por Clifford Stein, Thomas H. Cormen, Charles E. Leiserson, Ronald L.
http://en.wikipedia.org/wiki/Karatsuba_algorithm
Escriba comentarios si encuentra algo incorrecto, o desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA