En este tutorial, aprenderá cómo funciona el algoritmo divide y vencerás. También compararemos el enfoque de divide y vencerás con otros enfoques para resolver un problema recursivo.
Un algoritmo de divide y vencerás es una estrategia para resolver un gran problema mediante
- dividir el problema en subproblemas más pequeños
- resolver los subproblemas, y
- combinándolos para obtener el resultado deseado.
Para usar el algoritmo divide y vencerás, se usa la recursividad . Aprenda sobre la recursividad en diferentes lenguajes de programación:
- Recursión en Java
- Recursión en Python
- Recursión en C ++
¿Cómo funcionan los algoritmos de dividir y conquistar?
Estos son los pasos involucrados:
- Dividir : divide el problema dado en subproblemas utilizando la recursividad.
- Conquista : resuelve los subproblemas más pequeños de forma recursiva. Si el subproblema es lo suficientemente pequeño, resuélvalo directamente.
- Combinar: Combine las soluciones de los subproblemas que son parte del proceso recursivo para resolver el problema real.
Entendamos este concepto con la ayuda de un ejemplo.
Aquí, ordenaremos una matriz usando el enfoque de dividir y conquistar (es decir, ordenar por fusión).
- Deje que el arreglo dado sea:
Array for merge sort - Divida la matriz en dos mitades.
Divida la matriz en dos subpartes
Nuevamente, divida cada subparte recursivamente en dos mitades hasta que obtenga elementos individuales.
Divida la matriz en subpartes más pequeñas - Ahora, combine los elementos individuales de manera ordenada. Aquí, conquistar y combinar pasos van uno al lado del otro.
Combinar las subpartes
Complejidad del tiempo
La complejidad del algoritmo de divide y vencerás se calcula utilizando el teorema maestro.
T (n) = aT (n / b) + f (n), donde, n = tamaño de la entrada a = número de subproblemas en la recursividad n / b = tamaño de cada subproblema. Se supone que todos los subproblemas tienen el mismo tamaño. f (n) = costo del trabajo realizado fuera de la llamada recursiva, que incluye el costo de dividir el problema y el costo de fusionar las soluciones
Tomemos un ejemplo para encontrar la complejidad temporal de un problema recursivo.
Para una ordenación por combinación, la ecuación se puede escribir como:
T (n) = aT (n / b) + f (n) = 2T (n / 2) + O (n) Donde, a = 2 (cada vez, un problema se divide en 2 subproblemas) n / b = n / 2 (el tamaño de cada subproblema es la mitad de la entrada) f (n) = tiempo necesario para dividir el problema y fusionar los subproblemas T (n / 2) = O (n log n) (Para comprender esto, consulte el teorema maestro.) Ahora, T (n) = 2T (n log n) + O (n) ≈ O (n log n)
Dividir y conquistar Vs enfoque dinámico
El enfoque de divide y vencerás divide un problema en subproblemas más pequeños; estos subproblemas se resuelven además de forma recursiva. El resultado de cada subproblema no se almacena para referencia futura, mientras que, en un enfoque dinámico, el resultado de cada subproblema se almacena para referencia futura.
Utilice el método de dividir y conquistar cuando el mismo subproblema no se resuelva varias veces. Utilice el enfoque dinámico cuando el resultado de un subproblema se vaya a utilizar varias veces en el futuro.
Entendamos esto con un ejemplo. Suponga que estamos tratando de encontrar la serie de Fibonacci. Entonces,
Enfoque Dividir y conquistar:
fib (n) Si n <2, devuelve 1 Else, devuelve f (n - 1) + f (n -2)
Enfoque dinámico:
mem = () fib (n) If n in mem: return mem (n) else, If n <2, f = 1 else, f = f (n - 1) + f (n -2) mem (n) = f volver f
En un enfoque dinámico, mem almacena el resultado de cada subproblema.
Ventajas del algoritmo divide y vencerás
- La complejidad para la multiplicación de dos matrices usando el método ingenuo es O (n 3 ), mientras que usando el método de dividir y conquistar (es decir, la multiplicación de matrices de Strassen) es O (n 2.8074 ). Este enfoque también simplifica otros problemas, como la Torre de Hanoi.
- Este enfoque es adecuado para sistemas de multiprocesamiento.
- Hace un uso eficiente de las memorias caché.
Dividir y conquistar aplicaciones
- Búsqueda binaria
- Combinar ordenar
- Ordenación rápida
- Multiplicación de matrices de Strassen
- Algoritmo de Karatsuba
