Algoritmo divide y vencerás Es una estrategia de resolución de problemas que implica dividir un problema complejo en partes más pequeñas y manejables, resolver cada parte individualmente y luego combinar las soluciones para resolver el problema original. Es una técnica algorítmica ampliamente utilizada en informática y matemáticas.

Ejemplo: En el Combinar ordenar algoritmo, el Divide y conquistaras La estrategia se utiliza para ordenar una lista de elementos. La imagen a continuación ilustra los estados de división y fusión para ordenar la matriz usando Combinar ordenar .

cuantos millones hay en mil millones

Tabla de contenidos

• ¿Qué es divide y vencerás?
• Etapas de divide y vencerás
• Aplicaciones de divide y vencerás
• Conceptos básicos de divide y vencerás
• Algoritmos estándar sobre divide y vencerás
• Problemas basados ​​en búsqueda binaria
• Practicar problemas de Divide y Conquistarás

¿Qué es el algoritmo divide y vencerás?

Divide y vencerás es una técnica de resolución de problemas que implica dividir un problema mayor en subproblemas, resolver los subproblemas de forma independiente y combinar las soluciones de esos subproblemas para obtener la solución del problema mayor.

cómo emparejar auriculares beats

Etapas del algoritmo divide y vencerás:

El algoritmo divide y vencerás se puede dividir en tres etapas: Dividir , Conquistar y Unir .

1. Dividir:

• Divida el problema original en subproblemas más pequeños.
• Cada subproblema debe representar una parte del problema general.
• El objetivo es dividir el problema hasta que ya no sea posible realizar más divisiones.

2. Conquistar:

• Resuelva cada uno de los subproblemas más pequeños individualmente.
• Si un subproblema es lo suficientemente pequeño (a menudo denominado caso base), lo resolvemos directamente sin más recursividad.
• El objetivo es encontrar soluciones a estos subproblemas de forma independiente.

3. Fusionar:

• Combine los subproblemas para obtener la solución final de todo el problema.
• Una vez que se resuelven los subproblemas más pequeños, combinamos recursivamente sus soluciones para obtener la solución del problema mayor.
• El objetivo es formular una solución para el problema original fusionando los resultados de los subproblemas.

Aplicaciones del algoritmo divide y vencerás:

• Combinar orden: La ordenación por combinación es un ejemplo clásico de un algoritmo de ordenación divide y vencerás. Divide la matriz en submatrices más pequeñas, las clasifica individualmente y luego las combina para obtener la matriz ordenada.
• Hallazgo mediano: La mediana de un conjunto de números se puede encontrar mediante el método de divide y vencerás. Al dividir recursivamente el conjunto en subconjuntos más pequeños, la mediana se puede determinar de manera eficiente.
• Hallazgo mínimo y máximo: El algoritmo Divide and Conquer se puede utilizar para encontrar los elementos mínimo y máximo en una matriz simultáneamente. Al dividir la matriz en mitades y comparar los pares mínimo-máximo de cada mitad, el mínimo y el máximo generales se pueden identificar en complejidad de tiempo logarítmico.
• Multiplicación de matrices: El algoritmo de Strassen para la multiplicación de matrices es una técnica de divide y vencerás que reduce el número de multiplicaciones necesarias para matrices grandes al dividir las matrices en submatrices más pequeñas y combinar sus productos.
• Problema de par más cercano: El problema del par más cercano implica encontrar los dos puntos más cercanos en un conjunto de puntos en un espacio multidimensional. Un algoritmo de divide y vencerás, como el algoritmo de divide y vencerás del par más cercano, puede resolver eficientemente este problema dividiendo recursivamente los puntos y fusionando las soluciones de los subproblemas.

Conceptos básicos del algoritmo divide y vencerás:

• Introducción a Divide y vencerás
• Programación dinámica versus divide y vencerás
• Disminuir y conquistar
• Teorema maestro avanzado para las recurrencias de divide y vencerás

Algoritmos estándar en Algoritmo divide y vencerás :

• Búsqueda binaria
• Combinar ordenar
• Ordenación rápida
• Calcular potencia(x,n)
• Algoritmo de Karatsuba para multiplicación rápida
• Multiplicación de matrices de Strassen
• Casco convexo (algoritmo simple de divide y vencerás)
• Algoritmo Quickhull para casco convexo

Problemas basados ​​en la búsqueda binaria:

• Encuentra un elemento pico en una matriz determinada
• Verifique el elemento mayoritario en una matriz ordenada
• K-ésimo elemento de dos matrices ordenadas
• Encuentra el número de ceros
• Encuentre el recuento de rotación en una matriz ordenada rotada
• Encuentre el punto donde una función monótonamente creciente se vuelve positiva por primera vez
• Mediana de dos matrices ordenadas
• Mediana de dos matrices ordenadas de diferentes tamaños
• El problema de la partición del pintor usando la búsqueda binaria

Practicar problemas en Algoritmo divide y vencerás :

• Raíz cuadrada de un número entero
• Máximo y mínimo de una matriz utilizando un número mínimo de comparaciones
• Encuentre la frecuencia de cada elemento en una matriz de rango limitado en menos de O (n) tiempo
• Problema de mosaico
• Contar inversiones
• El problema del horizonte
• Buscar en una matriz 2D ordenada por filas y columnas
• Asignar un número mínimo de páginas
• Exponenciación modular (potencia en aritmética modular)

Enlaces rápidos :

• Aprenda la estructura de datos y los algoritmos | Tutorial de DSA
• 'Problemas de práctica' sobre divide y vencerás
• 'Cuestionarios' sobre divide y vencerás