Ventajas

Resolución de problemas complejos
Este modelo algorítmico es una herramienta potente para solucionar problemas complejos, tales como el clásico juego de las torres de Hanói. Todo lo que necesita este algoritmo es dividir el problema en subproblemas más sencillos, y éstos en otros más sencillos hasta llegar a unos subproblemas sencillos (también llamados casos base). Una vez ahí, se resuelven y se combinan los subproblemas en orden inverso a su inicio. 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.

Eficiencia del algoritmo
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). Esta cota es la que tienen los algoritmos divide y vencerás que solucionan problemas tales como ordenar y la transformada discreta de fourier. Ambos procedimientos reducen su complejidad, anteriormente definida por O(n2). Para terminar, cabe destacar que existen otros enfoques y métodos que mejoran estas cotas.

Al efectuar un análisis de la eficiencia de este método, se encuentra que la decisión de cómo se divida el problema afecta el ‘orden’ O de la implementación. Si se divide un problema de tamaño n en p partes de tamaño n/c cada una y considerando que hay un costo fijo b dependiente de n para procesar al final la unión de soluciones, se tiene que el número de operaciones o tiempo de procesamiento para el algoritmo se puede expresar como p veces el tiempo que toma resolver cada subproblema de tamaño n/c más el correspondiente costo fijo b:

 

 

\begin{array}{l} T(n)=pT(\frac{n}{c})+bn\\T(1)=b\end{array}

se considera un k tal que n=c^k \Rightarrow

(2)T(n)=R(k)\Rightarrow \begin{cases} R(k)=pR(k-1)+bc^k \\ R(0)=b \end{cases}

sustituyendo S(k)= \frac{R(k)}{p^k} se obtiene…

(3)\Rightarrow \begin{cases} S(k)=S(k-1)+b(\frac{c}{p})^k \\ S(0)=b \end{cases}

 S(k)- S(k-1) = b(\frac{c}{p})^k

Aplicando sumatoria de 1 a k en ambos lados…

 \sum_{i=1}^k{ S(i)- S(i-1) } = \sum_{i=1}^k{ b(\frac{c}{p})^i }

 S(k)- S(0) = S(k)- b = \sum_{i=1}^k{ b(\frac{c}{p})^i }

 S(k) = b + \sum_{i=1}^k{ b(\frac{c}{p})^i }

(3.1) S(k)= \sum_{i=0}^k{b(\frac{c}{p})^i} \Rightarrow

 R(k)= p^kb\sum_{i=0}^k{(\frac{c}{p})^i} = \frac{p^k}{c^k}bc^k\sum_{i=0}^k{(\frac{c}{p})^i} = bc^k\sum_{i=0}^k{(\frac{c}{p})^{k-i}} = bc^k\sum_{i=0}^k{(\frac{c}{p})^{i}}

(4) R(k) = bc^k\sum_{i=0}^k{(\frac{c}{p})^{i}}

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 formula \sum_{i=0}^{n-1}{a^i} = \frac{1 - a^n}{1 - a} si a>1.

(5.1) R(k) \approx O(bc^k) \Rightarrow T(n)=O(n)

Caso en que p == c:

(5.2) R(k) = bkc^k \Rightarrow T(n)=O(n\log n)

Caso p > c: En que el problema se divide en muchas partes de tamaño ‘relativamente’ pequeño, implica que la sumatoria (4) es…

 \sum_{i=0}^k{(\frac{c}{p})^{i}} = \frac{{(\frac{p}{c})^{k+1}}-1}{(\frac{p}{c})-1} = O((\frac{p}{c})^k)

 R(k) = \frac{bc^kp^k}{c^k} = bp^k

(5.3) T(n) = bp^{\log_c n} = bn^{\log_c p} \Rightarrow T(n)=O(n)

En efecto, los algoritmos de tipo Divide y Vencerás están acotados por O(n\log n) para casos muy particulares en que p y c son similares, mientras que en general se puede considerar que son O(n)

 

Paralelismo

Este tipo de algoritmos se adapta de forma natural a la ejecución en entornos multiprocesador, especialmente en sistemas de memoria compartida donde la comunicación de datos entre los procesadores no necesita ser planeada por adelantado, por lo que subproblemas distintos se pueden ejecutar en procesadores distintos.

Acceso a memoria
Los algoritmos que siguen el paradigma Divide y vencerás, tienden naturalmente a hacer un uso eficiente de las memorias cachés. La razón es que una vez que un subproblema es lo suficientemente pequeño, él y todos sus subproblemas se pueden, en principio, solucionar dentro de esa caché, sin tener acceso a la memoria principal, que es del orden de decenas de veces más lenta. 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. Por otra parte, estos algoritmos se pueden diseñar para muchos problemas importantes, tales como ordenación, la multiplicación de matrices, de manera que se haga un uso óptimo de la caché. En contraste, el acercamiento tradicional para explotar la caché es hacer bloques, de esta forma, el problema se divide explícitamente en las partes de tamaños apropiados para que se pueda utilizar al caché de forma óptima, pero solamente cuando el algoritmo es mejorado para el tamaño específico de la caché de una máquina particular. La misma ventaja existe en lo que respecta a otros sistemas jerárquicos de memoria, por ejemplo NUMA o memoria virtual, así como para niveles múltiples de caché: una vez que un subproblema es suficientemente pequeño, puede ser solucionado dentro de un nivel dado de la jerarquía, sin tener que acceder al más alto (más lento).

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.

Control del redondeo
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. Por ejemplo, se pueden sumar N números tanto como con un bucle simple que suma cada dato a una variable simple, o mediante un algoritmo de DyV que rompe el conjunto de datos en dos mitades, recursivamente computa cada suma y luego une las 2 sumas. Mientras que el segundo método realiza las mismas sumas que el primero, y cuesta más por las llamadas recursivas, normalmente es más exacto.

Fuente:
Colaboradores de Wikipedia. Algoritmo divide y vencerás [en línea]. Wikipedia, La enciclopedia libre. Disponible en <https://es.wikipedia.org/w/index.php?title=Algoritmo_divide_y_vencer>.