Algoritmo De Divide Y Vencer S Y Relaciones De Recurrencia

Algoritmo de divide y vencerás y relaciones de recurrencia
Muchos algoritmos recursivos resuelven un problema con unos datos determinados dividiéndolos en uno o varios problemas más pequeños. Esta reducción se aplica de manera sucesiva, hasta que las soluciones de los problemas pequeños se pueden calcular de forma sencilla. Por ejemplo, la búsqueda binaria consiste en reducir la búsqueda de unelemento en una lista a la búsqueda de dicho elemento en una lista con la mitad de elementos que la original. Esta reducción se aplica de forma sucesiva hasta que queda un único elemento. Cuando se ordena un conjunto de enteros cada una y se ordenación por mezcla, la lista original se divide en dos listas con la mitad de elementos cada una y se ordena cada una de ellas por separado para.Finalmente, mezclar las dos listas ordenadas. Otro ejemplo de este tipo de algoritmos recursivos es el procedimiento para multiplicar enteros que reduce el problema de multiplicar dos enteros a tres multiplicaciones de pares de enteros con la mitad de bits que los originales. Esta reducción se aplica de forma sucesiva hasta que se obtienen enteros de un bit. Estos procedimientos se denominan algoritmos dedivide y vencerás por que dividen un problema en uno o más problemas del mismo tipo, pero de tamaño menor, y vencen al problema utilizando las soluciones de los problemas de tamaño menor para determinar la solución del problema quizá con un cierto trabajo adicional
Relaciones de recurrencia de divide y vencerás
Supongamos que un algoritmo recursivo divide un problema de tamaño n en a subproblemasy que cada sud problema tiene tamaño n/b ( por simplicidad, supondremos que n es un múltiplo de b: en la práctica, los problemas más pequeños son normalmente de tamaño igual al entero más próximo entre los que son bien menores o iguales o bien mayores o iguales que n/b). supongamos también que se requieren un total de g (n) operaciones en lo que podríamos llamar la etapa de conquista delalgoritmo, esto es, para combinar las soluciones de los subproblemas y obtener la solución del problema n, entonces se tiene que f satisface la relación de recurrencia.
f(n) = af(n/b) + g(n),
que se denomina relación de recurrencia de divide y vencerás.
Mostraremos en primer lugar las relaciones de recurrencia de divide y vencerás que se pueden utilizar para estudiar la complejidad de varios algoritmosimportantes. Posteriormente, veremos cómo se pueden utilizar dichas relaciones de recurrencia para determinar la complejidad de esos algoritmos.
Ejemplo 1
Búsqueda binaria. Ya hemos descrito el algoritmo de búsqueda binaria en la sección 2.1. este algoritmo reduce la búsqueda de un elemento en una lista ordenada de tamaño n a la búsqueda binaria de este elemento en una lista ordenada de tamañon/2, cuando n es par.(Por tanto, el problema de tamaño n se ha transformado en un solo problema de tamaño n/2). Para realizar esta reducción el problema y otra para determinar si quedan elementos en dicha lista. Por tanto, si denotamos por f(n) el número de comparaciones realizadas para buscar un elemento en una lista ordenada de tamaño n, entonces
f(n)=f(n/2) +2,
cuando n es par.
Ejemplo 2
Máximo ymínimo de una lista. Consideraremos el siguiente algoritmo para encontrar los valores máximos y mínimo de una sucesión a1,a2…an. Si n = 1, entonces a1 es el máximo y el mínimo. Si n>1, se divide la sucesión en dos sudsuceciones, de forma que las dos tenga el mismo número de elementos o una de ellas tenga un elemento más que la otra. El problema se ha reducido a determinar el máximo y el mínimo decada una de las dos subsucesiones. La solución del problema original se obtiene comparando los máximos y mínimos de las dos subsuceciones. La solución del problema original se obtiene comparando los máximos y mínimos de las subsucesiones para obtener el máximo y el mínimo de la sucesión original.
Sea f(n)el número total de comparaciones realizadas para encontrar el máximo y el mínimo de una...