GEMA "Divide Y Vencerás"
3er Semestre
Divide y vencerás
Tanto el ordenamiento por mezcla como el ordenamiento rápido
emplean un paradigma algorítmico común que se basa en la recursividad. Este
paradigma, divide y vencerás, separa un problema en subproblemas que se parecen
al problema original, de manera recursiva resuelve los subproblemas y, por
último, combina las soluciones de los subproblemas para resolver el problema
original. Como divide y vencerás resuelve subproblemas de manera recursiva,
cada subproblema debe ser más pequeño que el problema original, y debe haber un
caso base para los subproblemas. Debes pensar que los algoritmos de divide y
vencerás tienen tres partes:
1.
Divide el problema en un número de
subproblemas que son instancias más pequeñas del mismo problema.
2.
Vence los subproblemas al resolverlos
de manera recursiva. Si son los suficientemente pequeños, resuelve los
subproblemas como casos base.
3.
Combina las soluciones de los
subproblemas en la solución para el problema original.
En esta página podrás encontrar que esn
y algunos ejemplos hacer a del tema
https://study.com/academy/lesson/solving-divide-and-conquer-recurrences.html
Comentarios
Publicar un comentario