Analisis De Algoritmos

La práctica de divide y vencerá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 para corregir 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 “Divide y 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 problema original 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 obtener la 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=1 hasta 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 cada sub-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<Bk, T(n) = O(nk)

Determinación del umbral

Uno de los aspectos que hay que tener en cuenta en los algoritmos de divide y vencerás es dónde colocar el umbral, esto es, cuándo se considera que un sub-problema es suficientemente pequeño como para no tener que dividirlo para resolverlo. Normalmente esto es lo que hace que un algoritmo de divide y vencerás sea efectivo o no. Por ejemplo, en el algoritmo de ordenación quicksort, cuando se tiene un array de longitud 3, es mejor ordenarlo utilizando otro algoritmo de ordenación (con 6 comparaciones se puede ordenar), ya que el quicksort debe dividirlo en dos sub-arrays y ordenar cada uno de ellos, para lo que utiliza más de 6 comparaciones.

Problema de los puntos más cercanos

El problema es: "dado un conjunto de puntos P, hallar el par de puntos más cercanos". La distancia entre dos puntos i y j es sqrt[(xi-xj)2+(yi-yj)2]. Una primera solución podría ser mirar todos los pares de puntos y quedarse con el más pequeño; al haber n•(n-1)/2 pares de puntos, el tiempo de ejecución es de O(n2). El programa resultante es muy corto, y rápido para casos pequeños, pero al ser este procedimiento una búsqueda exhaustiva, debería haber un algoritmo más rápido.

Supongamos que ordenamos los puntos según la coordenada x; esto supondría un tiempo de O(n•log n), lo que es una cota inferior para el algoritmo completo. Ahora que se tiene el conjunto ordenado, se puede trazar una línea vertical, x = xm, que divida al conjunto de puntos en dos: Pi y Pd. Ahora, o el par más cercano está en Pi, o está en Pd, o un punto está en Pi y el otro en Pd. Si los dos estuvieran en Pi o en Pd, se hallaría recursivamente, subdividiendo más el problema, por lo que ahora el problema se reduce al tercer caso, un punto en cada zona.

Llamemos di, dd y dc a las mínimas distancias en el primer caso, en el segundo, y en el tercero, respectivamente, y dmin al menor de di y dd. Para resolver el tercer caso, sólo hace falta mirar los puntos cuya coordenada x esté entre xm-dmin y xm+dmin. Para grandes conjuntos de puntos distribuidos uniformemente, el número

...