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 de puntos que caen en esa franja es sqrt(n), así que con una búsqueda exhaustiva el tiempo de ejecución sería de O(n), y tendríamos el problema resuelto. El tiempo de ejecución sería, según lo dicho en el otro apartado, O(n•log n).

Pero si los puntos no están uniformemente distribuidos, la cosa cambia. En el peor de los casos, todos los puntos están en la franja, así que la fuerza bruta no siempre funciona en tiempo lineal. Para ello, se puede recurrir a ordenar los puntos de la franja según la coordenada y, lo que supone un tiempo de ejecución de O(n•log n). Si la coordenada y difiere en más de dmin, se puede pasar al siguiente punto. El tiempo de

...