análisis de algoritmos



Análisis de Algoritmos y Computabilidad

REPORTE DE PRÁCTICA DEL ALGORITMO DIVIDE Y VENCERAS

Alumno
Maestro: Ricardo Magallanes Gómez

La práctica de divide yvencerás consiste en entender como resolver un gran problema en varios sub-problemas de menor complejidad haciendo así que sea más fácil su entendimiento y facilidad paracorregir cualquier error que surja además que el algoritmo se hace más efectivo en cuanto a tiempos de ejecución. A continuación hablaremos un poco sobre lo que es el “Dividey Vencerás” y los beneficios que este aporta.

La técnica de diseño de algoritmos llamada "divide y vencerás" (divide and conquer) consiste en descomponer el problemaoriginal en varios sub-problemas más sencillos, para luego resolver éstos mediante un cálculo sencillo. Por último, se combinan los resultados de cada sub-problema para obtenerla solución del problema original. El pseudocódigo sería:
funcion divide_y_venceras_1(problema)
{
descomponer el problema en n subproblemas más pequeños;
para i=1hasta n hacer
resolver el subproblema k;
combinar las n soluciones;
}

Tiempo de ejecución
El tiempo de ejecución de un algoritmo de divide y vencerás, T(n),viene dado por la suma de dos elementos:
El tiempo que tarda en resolver los A subproblemas en los que se divide el original, A·T(n/B), donde n/B es el tamaño de cadasub-problema. El tiempo necesario para combinar las soluciones de los sub-problemas para hallar la solución del original; normalmente es O(nk)
Por tanto, el tiempo total es:T(n) = A·T(n/B) + O(nk). La solución de esta ecuación, si A es mayor o igual que 1 y B es mayor que 1, es:
si A>Bk, T(n) = O(nlogBA)
si A=Bk, T(n) = O(nk·log n)
si A