Divide y venceras

Cap´ ıtulo 6

Divide y vencer´s a
La estrategia ((divide y vencer´ s)) es una t´ cnica de naturaleza recursiva. Consiste en dividir el problema a e planteado en un cierto n´ mero de problemas de menor entidad a los que denominamos subproblemas y u solucionar (vencer) independientemente esos subproblemas para, finalmente, combinar las soluciones de cada subproblema y formar con ellas la soluci´n del problema original. Quiz´ ser´a m´ s apropiado denomio a ı a ´ nar a la estrategia ((divide, resuelve y combina)), pues son estos sus tres elementos fundamentales (aunque estudiaremos una variante de la estrategia a la que convendr´a llamar ((divide, escoge y resuelve))). ı ´ Al dividir el problema en subproblemas, estos pueden ser de talla tan grande que resulte conveniente aplicarnuevamente la t´ cnica de ((divide y vencer´ s)) (o sea, dividir-resolver-combinar) para resolverlos. La e a recursi´ n finaliza cuando el problema al que nos enfrentamos es de talla tan reducida que puede resolverse o por alg´ n procedimiento alternativo (y, frecuentemente, trivial). u Un ejemplo paradigm´ tico de algoritmo que sigue una estrategia ((divide y vencer´ s)) es la ordenaci´ n a a o por fusi´n. Empezaremos nuestra exposici´ n, pues, presentando este algoritmo. Una vez hayamos presentao o do y analizado el algoritmo, introduciremos el esquema algor´tmico ((divide y vencer´ s)) y nos detendremos ı a a reflexionar acerca de las condiciones que debe satisfacer cada elemento del esquema para conducir a algoritmos eficientes. El denominado ((teorema maestro)), que presentaremos entonces,permite dar soluci´ n a las ecuaciones recursivas con las que se expresa el coste temporal de muchos algoritmos ((divide y o vencer´ s)). a Estudiaremos otros problemas que siguen una estrategia ((divide y vencer´ s)): a Determinaci´ n de pertenencia de un elemento a un vector por b´ squeda dicot´ mica, que ilustra la o u o variante que hemos denominado informalmente ((divide, escoge y resuelve)). C´lculo de la potencia entera de un n´ mero. a u B´ squeda de los elementos m´nimo y m´ ximo de un vector. u ı a B´ squeda del valor m´nimo en un vector convexo (o del valor m´ ximo de un vector c´ ncavo). u ı a o Ordenaci´ n por quicksort. o Selecci´ n del k-´ simo menor elemento de un vector. o e C´ lculo del par de puntos m´ s pr´ ximos en el plano. a a o C´ lculo de la envolvente convexa de unconjunto de puntos en el plano. a C´ lculo del producto de enteros grandes. a C´ lculo del producto de matrices cuadradas. a En algunos casos es posible transformar el algoritmo recursivo en otro iterativo, lo que puede permitir un ahorro espacial al eliminar la necesidad de gestionar una pila de llamadas a funci´ n. Estudiaremos el o tipo de recursi´ n que permite efectuar esta transformaci´ nrecursivo-iterativa: la denominada ((recursi´ n o o o por cola)). Presentaremos esta t´ cnica en el marco de la resoluci´ n del problema de la b´ squeda dicot´ mica. e o u o
Apuntes de Algor´ ıtmica
Divide y vencer´ s: a Divide and conquer. La expresi´ n ( o (divide y vencer´ s) tiene origen en a ) la estrategia seguida por Napole´ n en Austerlitz en o 1805. El ej´ rcito formado e por austriacos yrusos superaba en 15 000 soldados a las tropas francesas. Napole´ n se anticip´ al atao o que con una ofensiva al centro de las tropas enemigas que las dividi´ en dos o bandos a los que pudo vencer por separado.

Recursi´ n por cola: Tail o recursion.

6-1

6.1 Ordenaci´n por fusi´n (mergesort) o o

2005/01/10-12:35

6.1.
6.1.1.

Ordenaci´n por fusi´n (mergesort) o o
El problema deordenaci´n de los elementos de un vector o

Formalicemos el problema de la ordenaci´ n, que ya es bien conocido por el lector. o Dado un vector a de talla n entre cuyos elementos existe una relaci´ n de orden total ((es menor o igual o que)), que denotamos con ((≤)), deseamos ordenar el vector en orden no decreciente, es decir, a[i] ≤ a[i+1] para 0 ≤ i < n − 1.

6.1.2.
Ordenaci´ n por fusi´...