Page 57 - INTRODUCCIÓN AL ANÁLISIS DE ALGORITMOS

INTRODUCCIÓN AL ANÁLISIS DE ALGORITMOS

Divide y conquistarás (divide and conquer DANDC).

INtroduccIóN

Dada una función para computar n entradas, la estrategia divide y conquistarás sugiere dividir la
entrada en k subconjuntos, 1 ≤ k ≤ n, lo que genera k subproblemas, los cuales deben ser resueltos
mediante un método que debe ser hallado para combinar las subsoluciones en una solución gene-
ral. Si el subproblema sigue siendo demasiado grande, entonces puede ser reaplicada la estrategia.
Frecuentemente, los subproblemas resultantes de un diseño divide y conquistarás son del mismo
tipo que el problema original. Este principio se expresa de forma natural por un procedimiento re-
cursivo, de ahí que se obtengan subproblemas de menor dimensión aunque de la misma clase; de
hecho, eventualmente se producen subproblemas que son lo suficientemente pequeños como para
ser resueltos sin la necesidad de dividirlos. Una forma general de ver este modelo se observa en el
algoritmo 2.1.

Algoritmo 2.1. Forma general de la estrategia divide y conquistarás (Horowitz y Sahni, 1978)

En este caso, la función pequeño determina si se cumple una condición específica para que el al-
goritmo se detenga; si no es así, se crean dos subespacios en los cuales se subdivide el espacio en
dos más pequeños. DANDC se puede describir por esta relación recurrente:

51