¿Por qué los algoritmos de división y conquista a menudo se ejecutan más rápido que la fuerza bruta?

Question

¿Por qué los algoritmos de división y conquista a menudo corren más rápido que la fuerza bruta? Por ejemplo, para encontrar el par de puntos más cercano. Sé que puedes mostrarme la prueba matemática. Pero intuitivamente, ¿por qué sucede esto? ¿Magia?

Teóricamente, ¿es verdad que "dividir y conquistar siempre es mejor que la fuerza bruta"? Si no es así, ¿hay algún contraejemplo?

Answer 1

Para su primera pregunta, la intuición detrás de divide y vencerás es que en muchos problemas la cantidad de trabajo que se tiene que hacer se basa en alguna propiedad combinatoria de la entrada que se escala más que linealmente.

Por ejemplo, en el par más cercano de problema de puntos, el tiempo de ejecución de la respuesta de fuerza bruta se determina por el hecho de que usted tiene que mirar en absoluto O (n 2 ) los posibles pares de puntos.

Si toma algo que crece de forma cuadrática y lo corta en dos piezas, cada una de las cuales tiene la mitad del tamaño anterior, se necesita un cuarto del tiempo inicial para resolver el problema en cada mitad, por lo que se resuelve el problema en ambos las mitades toman tiempo aproximadamente la mitad del tiempo requerido para la solución de fuerza bruta. Cortarlo en cuatro pedazos tomaría un cuarto del tiempo, cortándolo en ocho pedazos una octava vez, etc.

La versión recursiva termina siendo más rápida en este caso porque en cada paso, evitamos hacer mucho trabaje al tratar con pares de elementos asegurándose de que no haya demasiados pares que realmente necesitemos verificar. La mayoría de los algoritmos que tienen una solución de dividir y conquistar terminan siendo más rápidos por una razón similar.

Para su segunda pregunta, no, los algoritmos de división y conquista no son necesariamente más rápidos que los algoritmos de fuerza bruta. Considere el problema de encontrar el valor máximo en una matriz. El algoritmo de fuerza bruta toma O (n) tiempo y usa O (1) espacio como lo hace un escaneo lineal sobre los datos. El algoritmo de dividir y vencer se da aquí:

• Si la matriz tiene solo un elemento, ese es el máximo.
• De lo contrario:
  • Corte la matriz por la mitad.
  • Encuentra el máximo en cada mitad.
  • Calcule el máximo de estos dos valores.

Esto toma tiempo O (n) también, pero utiliza O (log n) de memoria para el espacio de pila. En realidad es peor que el algoritmo lineal simple.

Como otro ejemplo, el maximum single-sell profit problem tiene una solución de divide y vencerás, pero la solución de programación dinámica optimizada es más rápida tanto en tiempo como en memoria.

Espero que esto ayude!

Answer 2

Te recomiendo que leas el capítulo 5 de Algorithm Design, explica divide y vencerás muy bien.

Intuitivamente, para un problema, si puede dividirlo en dos sub-problemas con el mismo patrón que el de origen, y la complejidad de tiempo para fusionar los resultados de los dos sub-problemas en el resultado final es de alguna manera pequeña , entonces es más rápido que resolver el problema completo de orignal por fuerza bruta.

Como se ha dicho en Diseño de Algoritmos, que en realidad no se puede ganar mucho de divide y vencerás en términos de tiempo, en general sólo se puede reducir la complejidad del tiempo de una mayor polinómica para bajar polinómica (por ejemplo, de O (n^3) a O (n^2)), pero apenas de exponencial a polinomio (por ejemplo, de O (2^n) a O (n^3)).

Creo que lo máximo que puede ganar de dividir y vencer es la mentalidad para la resolución de problemas. Siempre es un buen intento de dividir el gran problema original en subproblemas más pequeños y más fáciles. Incluso si no obtiene un mejor tiempo de ejecución, aún así le ayuda a pensar en el problema.