En la cultura popular, divide y vencerás (del inglés: divide and conquer) hace referencia a un refrán que implica resolver un problema difícil, dividiéndolo en partes más simples tantas veces como sea necesario, hasta que la resolución de las partes se torna obvia.Por otra parte, analizar y diseñar algoritmos de DyV son tareas que lleva tiempo dominar.Al igual que en la inducción, a veces es necesario sustituir el problema original por uno más complejo para conseguir realizar la recursión, y no hay un método sistemático de generalización.El nombre divide y vencerás también se aplica a veces a algoritmos que reducen cada problema a un único subproblema, como la búsqueda binaria para encontrar un elemento en una lista ordenada (o su equivalente en computación numérica, el algoritmo de bisección para búsqueda de raíces).Estos algoritmos pueden ser implementados más eficientemente que los algoritmos generales de “divide y vencerás”; en particular, si es usando una serie de recursiones que lo convierten en simples bucles.El nombre decrementa y vencerás ha sido propuesta para la subclase simple de problemas.El principio de Rubik indica que “un problema complejo se resuelve más fácil fragmentando en problemas cada vez más pequeños y por consiguiente más simples.” De manera que cada incidencia o tarea conlleva a una sola responsabilidad y a la vez sencilla de explicar.La búsqueda binaria, un algoritmo de divide y vencerás en el que el problema original es partido sucesivamente en subproblemas simples de más o menos la mitad del tamaño, tiene una larga historia.Otro ejemplo notable es el algoritmo inventado por A. Karatsuba en 1960 que puede multiplicar dos números de n dígitos enEl algoritmo refutó la conjetura de Andréi Kolmogórov en 1956 que esa tarea requería Ω(n2) operaciones.La resolución de un problema mediante esta técnica consta fundamentalmente de los siguientes pasos: Los algoritmos divide y vencerás (o divide and conquer, en inglés), se diseñan como procedimientos generalmente recursivos.Los algoritmos de “divide y vencerás” están naturalmente implementados, como procesos recursivos.Este enfoque es también la solución estándar en lenguajes de programación que no permiten procedimientos recursivos.Afortunadamente, los algoritmos DyV que son eficientes temporalmente tienen una profundidad recursiva relativamente pequeña.Los compiladores pueden también asignar más información en la pila de recursión que la estrictamente necesaria, tales como la dirección de retorno, parámetros invariables, y las variables internas del procedimiento.Por ejemplo, un algoritmo FFT podría parar la recursión cuando la entrada es una muestra simple, y el algoritmo quicksort de ordenación podría parar cuando la entrada es una lista vacía.Por otra parte, la eficiencia normalmente mejora si la recursión se para en casos relativamente grandes, y estos son resueltos no recursivamente.Véase que estas consideraciones no dependen de si la recursión está implementada por compilador o por pila explícita.Para algunos problemas, la recursión ramificada podría acabar evaluando el mismo subproblema muchas veces.En tales casos valdría la pena identificar y guardar las soluciones de estos subproblemas solapados, una técnica comúnmente conocida como memoización.Cómo dividir los problemas es, a menudo, la parte más compleja del algoritmo.Por eso, en muchos problemas, el modelo sólo ofrece la solución más sencilla, no la mejor.Normalmente, esta técnica proporciona una forma natural de diseñar algoritmos eficientes.Por ejemplo, si el trabajo de dividir el problema y de combinar las soluciones parciales es proporcional al tamaño del problema (n); además, hay un número limitado p de subproblemas de tamaño aproximadamente igual a n/p en cada etapa; y por último, los casos base requieren un tiempo constante (O(1)); entonces el algoritmo divide y vencerás tiene por cota superior asintótica a O(nlogn).Según la relación entre c y p se obtiene diferentes 'órdenes' para el algoritmo: Caso p < c: Es decir, si el problema se divide en pocas partes de gran tamaño cada una, entonces la sumatoria (4) es O(1) dado que se puede aplicar directamente la fórmulaEn efecto, los algoritmos de tipo Divide y Vencerás están acotados porLos algoritmos que siguen el paradigma Divide y vencerás, tienden naturalmente a hacer un uso eficiente de las memorias cachés.Un algoritmo diseñado para aprovechar la memoria caché de esta manera se llama modelo caché-olvidadiza, olvidadiza porque no contiene el tamaño de la memoria como parámetro explícito.Sin embargo, la clase de optimalidad asintótica descrita aquí, análoga a notación O mayúscula, no hace caso de factores constantes, y el añadir mejoras adicionales específicas de la máquina y caché no es un requerimiento para alcanzar el óptimo en un sentido absoluto.En computaciones con aritmética redondeada, por ejemplo con los números en aritmética flotante, un algoritmo de divide y vencerás podría dar resultados más exactos que un problema iterativo equivalente superficialmente.
Visualización del cálculo de la sublista contigua más grande con la suma más grande de una lista de 4 elementos por divide y vencerás.
