divide y venceras

Análisis de algoritmos


Introducción
Divide y vencerás es considerada una filosofía
general para resolver problemas y se usa en
muchos ámbitos.

Introducción
En el contexto de computaciónes una técnica de
diseño de algoritmos que consiste en resolver un
problema a partir de la solución de subproblemas
del mismo tipo, pero de menor tamaño

Introducción
Si los subproblemas sontodavía grandes se
aplicará de nuevo esta misma técnica hasta
alcanzar subproblemas lo suficientemente
pequeños para ser solucionados directamente

Elementos de la estrategia D y V
1.

Dividirel problema en subproblemas.

2. Resolver de manera independiente todos los

subproblemas. Si el subproblema es sencillo de resolver
(caso base) se resolverá directamente, en caso contrario seresolverá recursivamente.
3. Combinar las subsoluciones para construir la solución

general del problema.

Forma general de los algoritmos diseñados con la
estrategia de Divide y VencerásSolucion

DyV (Problema

p){

int i;
Solucion s;
Problema
subproblemas[10];
Solucion
subsoluciones[10];
if(EsCasoBase(p))
s=ResuelveDeFormaDirecta(p);
else{
Divide(p, subproblemas);
for(i=0 ; i < 10 ; i++)
subsoluciones[i]=DyV(subproblemas[i])
s=Combina(subsoluciones)
}
return s;
}

Tiempo de ejecución de algoritmos DyV
‫)݊(ܥ‬
ܶ(݊) =

‫ܾ < ݊ ≤ 1 ݅ݏ‬

݊
ܽܶ ቀ ቁ + ‫)݊(ܥ‬ܾ

‫ܾ ≥ ݊ ݅ݏ‬

ܽ = número de subproblemas o llamandas recursivas

݊ = tamaño de cada subproblema
ܾ

‫ = )݊(ܥ‬coste por descomponer el problema inicial en a subproblemas y combinar lassubsoluciones.

Eficiencia de los algoritmos DyV
La eficiencia depende de tres factores:
1.

El número de subproblemas. El cuál deberá ser
pequeño e independiente de una entrada determinada.

2.El tamaño de los subproblemas.

3.

Repartir la carga entre los subproblemas, lo más
equilibradamente posible

Ventajas de los algoritmos diseñados con
Divide y Vencerás
Dividir el un...