Diseño recursivo y eficiente (2013)

Apunte Español
Universidad Universidad Politécnica de Valencia (UPV)
Grado Ingeniería Informática - 2º curso
Asignatura Estructura de Datos y Algoritmos
Año del apunte 2013
Páginas 52
Fecha de subida 27/11/2014
Descargas 1
Subido por

Descripción

Diseño recursivo y eficiente: soluciones Divide y Vencerás para la Ordenación y la Selección

Vista previa del texto

Estructuras de Datos y Algoritmos.
Unidad Did´actica I: Conceptos de Java para Estructuras de Datos.
Tema 5. Dise˜ no recursivo y eficiente: soluciones Divide y Vencer´ as para la Ordenaci´ on y la Selecci´ on Mabel Galiano Natividad Prieto Departamento de Sistemas Inform´aticos y Computaci´on Escuela T´ecnica Superior de Ingenier´ıa Inform´atica ´Indice 1. Razonamiento y Dise˜ no recursivos: revisi´ on de conceptos 1.1. Aplicaci´on del razonamiento Inductivo a la Programaci´on . . . . . . . . . . . . .
1.1.1. Esquema general recursivo . . . . . . . . . . . . . . . . . . . . . . . . . .
1.1.2. Taxonom´ıa de la Recursi´on . . . . . . . . . . . . . . . . . . . . . . . . . .
1.1.3. Ejecuci´on de un m´etodo recursivo: la Pila de la Recursi´on . . . . . . . .
1.1.4. Iteraci´on VS Recursi´on . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.2. Etapas del dise˜ no recursivo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.2.1. Esquema recursivo de Recorrido de un array . . . . . . . . . . . . . . . .
1.2.2. Esquema recursivo de B´ usqueda de un Dato b en un array . . . . . . . .
1.3. Coste Espacial y Temporal de un m´etodo y su an´alisis . . . . . . . . . . . . . . .
1.3.1. Revisi´on de conceptos y notaci´on . . . . . . . . . . . . . . . . . . . . . .
1.3.2. Expresi´on de la Complejidad Temporal de un m´etodo recursivo: Ecuaciones o Relaciones de Recurrencia . . . . . . . . . . . . . . . . . . . . .
2. El coste como criterio de dise˜ no: teoremas de coste y su aplicaci´ on al desarrollo de estrategias recursivas eficientes 2.1. Reducci´on Aritm´etica VS Geom´etrica de la talla para la Recursi´on Lineal: la estrategia de Reducci´on Logar´ıtmica y algunos ejemplos de su aplicaci´on . . . .
2.2. Recursi´on M´ ultiple VS Recursi´on Lineal: la estrategia Divide y Vencer´as (DyV) y su aplicaci´on al problema de la Ordenaci´on . . . . . . . . . . . . . . . . . . . .
2.2.1. Ordenaci´on por Fusi´on o Merge: m´etodos mergeSort y fusionDyV . . . .
2.2.2. Quick Sort: m´etodos quickSort y particion . . . . . . . . . . . . . . .
2.3. Una soluci´on eficiente al problema de la Selecci´on: m´etodo seleccionRapida . .
1 3 7 8 11 13 15 17 19 21 24 24 29 31 32 37 42 45 51 ´INDICE Objetivos y Bibliograf´ıa El objetivo principal de este tema es mostrar que la incorporaci´on del criterio de eficiencia al proceso de dise˜ no recursivo permite el desarrollo de estrategias eficientes y generales de resoluci´on de problemas complejos y/o de gran peso espec´ıfico en la Programaci´on; la estrategia paradigma elegida para ilustrarlo es Divide y Vencer´as por dos motivos: su instancia para el caso de Recursi´on Lineal es la estrategia de Reducci´on Logar´ıtmica y permite resolver recursiva y eficientemente los problemas de Ordenaci´on y Selecci´on o B´ usqueda del k-´esimo m´ınimo de una Colecci´on de Datos.
Para conseguir el objetivo enunciado en este tema se ampl´ıan los conceptos sobre dise˜ no recursivo estudiados en la asignatura Programaci´on de primer curso. En concreto, tras haber revisado detenidamente en su primer apartado los principios del dise˜ no recursivo y del uso del coste como criterio efectivo de comparaci´on entre los distintos m´etodos que resuelven un mismo problema, en el segundo apartado del tema se presentan los (cuatro) Teoremas que establecen el coste Temporal Asint´otico de un m´etodo recursivo sin necesidad de resolver y acotar la soluci´on de las Relaciones de Recurrencia que expresan su Complejidad, el elemento imprescindible para aplicar el criterio de eficiencia ya en los primeros pasos del proceso de dise˜ no recursivo y no tras su conclusi´on. Como resultado directo del an´alisis y confrontaci´on de tales teoremas se deducir´an las estrategias de Reducci´on Logar´ıtmica para Recursi´on Lineal y la de Divide y Vencer´as para Recursi´on M´ ultiple; ´esta u ´ ltima se aplicar´a al dise˜ no de m´etodos eficientes para la Selecci´on (seleccionRapida) y Ordenaci´on de un array gen´erico (m´etodos mergeSort y quickSort).
Como bibliograf´ıa b´asica del tema se proponen los siguientes apartados de los Cap´ıtulos 7 y 8 del libro de Weiss M.A. Estructuras de datos en Java (Adisson-Wesley, 2000): del 7.1 al 7.4 y del 8.5 al 8.7. Tambi´en se recomienda consultar para la parte de Divide y Vencer´as el Cap´ıtulo 19 del libro de Sahni, S. Data Structures, Algorithms, and Applications in Java (McGraw-Hill, 2000).
En cuanto a bibliograf´ıa adicional se pueden consultar los Cap´ıtulos 4 y 7 del libro de Brassard G. y Bratley P. Fundamentos de Algoritmia (Prentice Hall, 1997) y el Cap´ıtulo 3 del texto de Ferri, F.J., Albert J.V. y Mart´ın G. Introducci´ o a l’an` alisi i disseny d’algorismes (Universitat de Val`encia, 1998); asimismo resultan de inter´es las siguientes referencias electr´onicas: la tabla de material did´ actico del ´ıtem 5 de los Contenidos del tema en la PoliformaT EDA, donde figuran diversas clases Java que se pueden usar para profundizar en el estudio de la estructura e implementaci´on recursiva de un m´etodo, y la p´agina http://www.cs.ubc.ca/spider/harrison/Java/sorting-demo.html, que contiene distintas demostraciones gr´aficas y m´etodos de Ordenaci´on de un array en Java desarrollados por James Gosling y Jason Harrison.
NOTA. Los m´etodos mergeSort y quickSort se a˜ nadir´an a la clase Ordenacion del paquete librerias.util.operacionesArray del proyecto BlueJ eda y el m´etodo seleccionRapida a la clase Operaciones del mismo paquete. Los restantes m´etodos recursivos que aparecen en los ejemplos y ejercicios propuestos de este tema formar´an parte de las distintas clases que componen el (nuevo) paquete tema5 de ejemplos de eda.
2 1. Razonamiento y Dise˜ no recursivos: revisi´on de conceptos 1.
Razonamiento y Dise˜ no recursivos: revisi´ on de conceptos Los t´erminos Inducci´on, Recursi´on o Inferencia se utilizan indistintamente y en diversos ´ambitos, desde el cotidiano al cient´ıfico, para denominar una misma estrategia de resoluci´on de problemas: a partir de un conjunto finito de ejemplos o casos sencillos de un problema para los que se conoce la soluci´on, por trivial o sencilla, se realiza una hip´otesis de cu´al es la soluci´on general de dicho problema, i.e. la soluci´on aplicable a cualquiera de sus casos o caso general.
Para poner de manifiesto la naturalidad con la que el ser humano aplica la estrategia inductiva, a sabiendas o no, se enuncian a continuaci´on algunos problemas espec´ıficos que se resuelven aplic´andola y que, m´as que ajenos o novedosos, deben resultar familiares: un test psicot´ecnico, en el que se pide establecer el siguiente de una serie de elementos dada, n´ umeros o figuras t´ıpicamente, el aprendizaje de la lengua materna que realizan los beb´es y en Matem´aticas la definici´on de muchas funciones, entre otras factorial y fibonacci, conjuntos como los Naturales y la Prueba por Inducci´on de una propiedad dada. Estos ejemplos ayudan a perfilar a´ un m´as las caracter´ısticas del razonamiento inductivo: 1. La hip´otesis de soluci´on del problema para el caso general se expresa expl´ıcitamente en t´erminos de la(s) soluci´on(es) del mismo problema para un caso(s) m´as sencillo(s).
2. La hip´otesis de soluci´on del problema para el caso general debe ser validada o demostrada mediante un proceso de prueba, sin el cual no deja de ser m´as que eso, una hip´otesis. Es precisamente por esta caracter´ıstica que, en muchas ocasiones, se denomina Prueba por Inducci´on al razonamiento inductivo.
3. Se reconoce como recursivo a cualquier ente (definici´on, proceso, estructura, etc.) que se define en funci´on de s´ı mismo.
4. A´ un de manera inconsciente, el ser humano lo aplica en un gran n´ umero de procesos de Aprendizaje.
Finalmente, y antes de indicar su papel en la Programaci´on, se debe presentar la ventaja m´as clara que tiene el razonamiento inductivo frente al deductivo: cuando un problema es lo suficientemente complejo, resulta m´as f´acil expresar su soluci´on inductiva que deductivamente, i.e. en t´erminos de la soluci´on del mismo problema para casos m´as sencillos que por enumeraci´on de los pasos a seguir para obtenerla. Para ilustrar este hecho se propone resolver el problema de las Torres de Hanoi, cuyo enunciado es el siguiente: Se dispone de tres torres (origen, destino y auxiliar) y un cierto n´ umero de discos de diferentes tama˜ nos. Inicialmente, todos los discos se encuentran en la torre origen apilados en forma decreciente seg´ un su di´ametro. El problema consiste en desplazarlos a la torre destino utilizando la torre auxiliar y siguiendo las siguientes reglas: los discos se deben desplazar uno a uno y en ning´ un momento puede haber un disco de mayor di´ametro situado sobre uno m´as peque˜ no.
Como se puede comprobar f´acilmente, abordar la resoluci´on general del problema tal como se ha enunciado, por ejemplo para N = 30 discos, resulta imposible. Un primer paso plausible ser´ıa mover el disco m´as peque˜ no de la torre origen a cualquier torre que no sea la torre destino. Pero inmediatamente se plantean las siguientes cuestiones: suponiendo situado en la torre auxiliar el disco m´as peque˜ no, ¿c´omo situar cada uno de los 29 discos restantes en cada una de las tres torres disponibles?; es m´as, en el momento en que se intente mover el m´as M.Galiano,N.Prieto 3 1. Razonamiento y Dise˜ no recursivos: revisi´on de conceptos peque˜ no de los 29 discos restantes la elecci´on de la torre auxiliar para situar el disco m´as peque˜ no empieza a ser dudosa pero, si no se pone en ella ¿d´onde se pone entonces el disco m´as peque˜ no? En resumen, describir paso a paso la soluci´on de las Torres de Hanoi es demasiado complejo, no resulta posible si se afronta globalmente siguiendo las reglas establecidas.
Dicho lo anterior, resulta bastante natural pensar en intentar resolver el mismo problema pero con menos discos, poco a poco, para ver si as´ı se puede entender mejor el problema y darle una soluci´on. Sup´ongase entonces que se empieza estudiando la soluci´on al caso m´as f´acil posible de Hanoi, esto es aquel en el que hay s´olo un disco que mover, N = 1. Para este caso trivial, la soluci´on es obvia y se ilustra gr´aficamente en la siguiente figura: mover el disco de la torre origen a la torre destino, operaci´on b´asica que a partir de ahora se denotar´a como moverDisco(origen, destino).
origen auxiliar destino moverDisco(origen, destino) origen auxiliar destino Para N = 1, la soluci´on de Hanoi se puede expresar entonces como sigue: hanoi(1, origen, auxiliar, destino) moverDisco(origen, destino) Si se afronta ahora la resoluci´on de Hanoi para el siguiente caso m´as f´acil, ´este s´olo puede ser Hanoi con N = 2; a estas alturas ya se debe haber ca´ıdo en la cuenta de que la talla del problema Hanoi es el n´ umero de discos a mover, N > 0. Como muestra la siguiente figura, la soluci´on a este caso sencillo es realizar tres operaciones b´asicas moverDisco: origen auxiliar moverDisco(origen,auxiliar) destino origen auxiliar moverDisco(origen, destino) destino origen auxiliar moverDisco(auxiliar, destino) destino origen 4 auxiliar destino 1. Razonamiento y Dise˜ no recursivos: revisi´on de conceptos M´as que la descripci´on paso a paso de la soluci´on obtenida lo que interesa aprender de este caso es que su soluci´on se expresa, al igual que la de Hanoi con N = 1 disco, en t´erminos de la operaci´on b´asica moverDisco y, a diferencia de la de Hanoi con N = 1 disco, usando la torre auxiliar como destino del primer disco que se mueve y como origen del u ´ ltimo disco que se mueve; s´olo en el segundo movimiento auxiliar juega el mismo papel que en Hanoi con N=1, esto es ninguno. As´ı, la soluci´on de Hanoi con N = 2 se puede expresar como sigue: hanoi(2, origen, auxiliar, destino) hanoi(1, origen, destino, auxiliar) moverDisco(origen, destino) hanoi(1, auxiliar, origen, destino) A partir de ´esta, la hip´otesis de soluci´on de Hanoi con N = 3 discos ser´ıa: hanoi(3, origen, auxiliar, destino) hanoi(2, origen, destino, auxiliar) moverDisco(origen, destino) hanoi(2, auxiliar, origen, destino) Para comprobar su validez, en la siguiente figura se muestra la soluci´on de Hanoi con N=3 discos pero enmarcando el conjunto de estados y movimientos que se pueden describir en t´erminos de Hanoi con N = 2 discos: origen auxiliar hanoi(2, origen, destino, auxiliar) moverDisco(origen,destino) destino origen auxiliar moverDisco(origen, auxiliar) destino origen auxiliar moverDisco(destino, auxiliar) destino origen auxiliar destino moverDisco(origen,destino) origen auxiliar destino hanoi(2, auxiliar, origen, destino) moverDisco(auxiliar, origen) origen auxiliar moverDisco(auxiliar, destino) destino origen auxiliar moverDisco(origen, destino) destino origen auxiliar destino M.Galiano,N.Prieto 5 1. Razonamiento y Dise˜ no recursivos: revisi´on de conceptos De la figura anterior resulta inmediato comprobar que, en efecto, la hip´otesis realizada es v´alida. Por ello, generaliz´andola para cualquier n´ umero de discos N>0, la Hip´ otesis de Inducci´ on sobre la soluci´on general de Hanoi que se obtiene es la siguiente: hanoi(N, origen, auxiliar, destino) si N = 1 moverDisco(origen, destino) sino hacer: hanoi(N-1, origen, destino, auxiliar) moverDisco(origen, destino) hanoi(N-1, auxiliar, origen, destino) Lo que expresa esta hip´otesis es algo razonable: para mover N discos de la torre origen a la torre destino, utilizando en ese proceso la torre auxiliar, hacer: si N = 1 moverDisco(origen, destino) sino hacer: 1. siguiendo las reglas establecidas, mover los N-1 primeros discos de la torre origen a la torre auxiliar, utilizando en ese proceso como torre auxiliar destino; formalmente: hanoi(N-1, origen, destino, auxiliar); 2. como tras realizar el paso 1 en la torre origen s´olo queda el disco m´as grande, moverlo a la torre destino mediante moverDisco(origen, destino); 3. tras realizar el paso 2, mover los N-1 discos de la torre auxiliar, donde se dejaron en el paso 1, a la torre destino, utilizando como torre auxiliar origen; formalmente: hanoi(N-1, auxiliar, origen, destino).
Tras realizar este u ´ ltimo paso, como en la torre destino ya estaba el m´as grande de todos los discos, la resoluci´on del problema concluye.
Al leer el algoritmo establecido, habituado como se est´a al razonamiento deductivo, es f´acil pensar que no dice nada de c´omo mover los N-1 > 1 discos restantes en los pasos 1 y 3, pero recu´erdese que se est´a realizando una definici´on recursiva y, por tanto, si se pregunta c´omo solucionar el movimiento de N-1 discos la respuesta s´olo puede ser ✭✭pues haciendo para los N-2 restantes lo mismo que se hac´ıa antes para los N-1✮✮ o, en otras palabras, seguir el algoritmo que se acaba de presentar hasta que s´olo quede un disco que mover.
Una vez formulada la Hip´ otesis de Inducci´ on se debe realizar la demostraci´ on de su correcci´ on, lo que conlleva las siguientes pruebas: la prueba de Terminaci´ on: independientemente de cu´anto tarde en hacerlo, si N>0 hanoi(N,origen,auxiliar,destino) termina o resuelve el problema en un tiempo finito; una vez demostrado que termina, se realiza la prueba de la Hip´ otesis de Inducci´ on.
Una de las herramientas m´as eficaces para realizar ambas pruebas es, precisamente, la Prueba por Inducci´on. As´ı, para demostrar que si N>0 hanoi(N,origen,auxiliar,destino) termina en un tiempo finito, basta con aplicar el siguiente razonamiento inductivo: si N = 1, como moverDisco(origen,destino) es una acci´on que se realiza en un tiempo finito, hanoi(N,origen,auxiliar,destino) termina en un tiempo finito y sino, como el n´ umero de discos es finito y para resolver Hanoi con N > 1 se debe resolver Hanoi con N-1, tras un tiempo finito se alcanzar´a la resoluci´on de Hanoi con N = 1. As´ı, la resoluci´on de Hanoi con N > 1 termina en un tiempo finito.
6 1.
Para intuir cu´anto tarda Hanoi con N > 1 en resolverse, se propone la siguiente cuesti´ on: Cuenta la leyenda que en el templo de Brahma en Benares exist´ıan tres agujas de diamantes que serv´ıan para apilar 64 discos de oro puro. Incansablemente, los sacerdotes transfer´ıan discos de una aguja a otra obedeciendo siempre la ley de Brahma: ning´ un disco se puede situar encima de uno menor.
Al inicio del mundo los 64 discos se dispusieron sobre la primera aguja, formando una torre de Brahma; seg´ un la leyenda, en el momento en que el m´as peque˜ no de los discos se colocara y se tuviera una nueva torre de Brahma llegar´ıa el fin del mundo.
Seg´ un la profec´ıa de los brahmanes, suponiendo que los monjes emplearan 20 mseg.
en mover un disco, ¿cu´ ando llegar´ a el fin del mundo? Una vez demostrada por Inducci´on la terminaci´on de Hanoi, utilizando de nuevo la Prueba por Inducci´on se realizar´a la Prueba de la Hip´ otesis de Inducci´ on. As´ı, si N = 1, obviamente, moverDisco(origen,destino) es la soluci´on correcta y sino, suponiendo que tanto hanoi(N-1, origen, destino, auxiliar) como hanoi(N-1, auxiliar, origen, destino) son las soluciones correctas para los respectivos problemas de Hanoi con N-1 discos, como moverDisco(origen, destino) es correcta y N>N-1 entonces, por construcci´on, hanoi(N,origen,destino,auxiliar) es tambi´en correcta.
1.1.
Aplicaci´ on del razonamiento Inductivo a la Programaci´ on De la introducci´on realizada y recordando que la Programaci´on no es m´as que la actividad de resoluci´on de problemas por ordenador se pueden deducir los siguientes hechos: el instrumento necesario y suficiente que debe proporcionar cualquier lenguaje de programaci´on para implementar un razonamiento inductivo (recursivo) es el m´etodo, bien sea funci´on o procedimiento; un m´etodo que resuelve un problema de talla dada es recursivo si se define invoc´andose a s´ı mismo, para resolver el mismo problema pero de talla menor. En otras palabras, recordando que la petici´on de ejecuci´on de cualquier m´etodo, recursivo o no que sea, se denomina invocaci´on (o llamada) al mismo, un m´etodo es recursivo si su ejecuci´on requiere la ejecuci´on previa del mismo m´etodo para una talla menor.
As´ı por ejemplo, un m´etodo Java para resolver el problema de Hanoi puede ser el siguiente: static void hanoi(int n, String origen, String auxiliar, String destino){ if ( n == 1 ) moverDisco(origen, destino); else { hanoi(n-1, origen, destino, auxiliar); moverDisco(origen, destino); hanoi(n-1, auxiliar, origen, destino); } } static void moverDisco(String desde, String hasta){ System.out.println("Moviendo disco de torre "+desde+" a torre "+hasta); } Para ser ejecutado ´este m´etodo se debe invocar desde otro, como por ejemplo el que sigue: M.Galiano,N.Prieto 7 1.
package ejemplos.tema5; import java.util.*; public class TestHanoi { public static void main(String args[]){ Scanner teclado = new Scanner(System.in); System.out.println("Introduzca el n´ umero de discos en la torre origen:"); int N = teclado.nextInt(); if ( N > 0 ) hanoi(N, "origen", "auxiliar", "destino"); else System.out.println("El n´ umero de discos debe ser mayor que cero"); } private static void hanoi(int n, String origen, String auxiliar, String destino){...} private static void moverDisco(String desde, String hasta){...} } Como se observa en el c´odigo de hanoi, los cambios introducidos para traducir una soluci´on recursiva de un problema a un m´etodo Java se deben al cambio de procesador que ejecutar´a la soluci´on, el cerebro humano VS la m´aquina (Java) del ordenador. Aunque mayor que la del ser humano, la potencia de un ordenador radica u ´ nica y exclusivamente en la rapidez con la que es capaz de ejecutar c´alculos incansablemente y sin posibilidad de error; esto es, carece de la flexibilidad y conocimiento propios de la mente humana, por lo que realizar una buena labor de programaci´on supone respetar muchas restricciones y un alto grado de formalizaci´on.
Quiz´as los exponentes m´as claros de este encorsetamiento del razonamiento son el cambio de lenguaje en la expresi´on de la soluci´on, que pasa del lenguaje natural (pseudoc´odigo) al m´as restrictivo lenguaje de programaci´on, y la demostraci´on de que los c´alculos realizados son correctos, terminan en un tiempo finito y consumen el m´ınimo de recursos posibles. En los siguientes apartados se detallan y formalizan todos estos cambios, avanzando as´ı en la descripci´on y caracter´ısticas del razonamiento inductivo aplicado al dise˜ no de programas.
1.1.1.
Esquema general recursivo El m´etodo hanoi que se acaba de presentar no es m´as que una instancia del esquema general de m´etodo recursivo que se presenta a continuaci´on y que plasma en Java la estructura esencial que debe tener cualquier m´etodo que se defina para formalizar una estrategia inductiva de resoluci´on de un problema cuyos Datos representa x: /** Dominio(x) == true */ public static TipoResultado metodoRecursivo( TipoDatos x ){ TipoResultado resMetodo, resLlamada1, resLlamada2,..., resLlamadaK; if ( casoBase(x) ) resMetodo = solucionBase(x); else{ resLlamada1 = metodoRecursivo( anterior1(x) ); resLlamada2 = metodoRecursivo( anterior2(x) ); ...
resLlamadaK = metodoRecursivo( anteriorK(x) ); resMetodo = combinar( x, resLlamada1, ..., resLlamadaK ); } return resMetodo; } // metodoRecursivo devuelve la soluci´ on correcta del problema para x Para poder valorar la forma en que este esquema general transcribe a un lenguaje de programaci´on un razonamiento inductivo conviene antes aclarar las siguientes cuestiones.
8 1.
Sobre la representaci´ on de los Datos del problema y su talla: par´ ametros formales del m´ etodo, sus tipos y posibles restricciones Determinar la soluci´on de un problema requiere, impl´ıcita o expl´ıcitamente, determinar la talla del problema o magnitud de sus Datos; a´ un m´as cuando la soluci´on es recursiva, pues se expresa expl´ıcitamente en t´erminos de la(s) soluci´on(es) del mismo problema para talla(s) menor(es). As´ı, la cabecera de metodoRecursivo debe contener al menos un par´ametro formal, x, para representar los Datos o talla del problema. Obviamente, el tipo de x, TipoDatos, debe representar el conjunto o dominio de los Datos del problema.
Ahora bien, no todos los dominios tienen un tipo equivalente en el lenguaje de programaci´on; en hanoi por ejemplo la talla es el n´ umero de discos a mover y pertenece al dominio de los Naturales estrictamente positivos pero el par´ametro formal x = n que la representa es de tipo int. Por tanto, cualquier discordancia entre el dominio de los Datos del problema y el tipo del par´ametro formal que los representa debe ser corregida, pues la soluci´on del problema s´olo es v´alida para Datos que son del dominio; imag´ınese por ejemplo el resultado que obtendr´ıa el m´etodo hanoi cuando n ≤ 0.
El primer paso para llevar a cabo esta correcci´on es advertir que la ejecuci´on del m´etodo metodoRecursivo exige como condici´on previa (o Precondici´on) la comprobaci´on de que el valor de x es, adem´as de un valor posible de TipoDatos x, un valor del dominio de los Datos del problema; es por ello que se ha incluido como comentario previo a la cabecera de metodoRecursivo la expresi´on l´ogica Dominio(x) == true, que por ejemplo para hanoi ser´ıa n ≥ 0. El segundo paso a dar es bastante obvio: antes de invocar a metodoRecursivo desde otro m´etodo, programar su Precondici´on. Recu´erdese por ejemplo que en el main de TestHanoi se comprueba mediante un if el valor de la variable N, el par´ametro actual con el que se pretende invocar a hanoi: si es estrictamente positivo, entonces se ejecuta hanoi(N) y sino se muestra por pantalla un mensaje en el que se recuerda al usuario que el n´ umero de discos de la torre origen debe ser positivo; con este simple test el programador consigue hacer coincidir el dominio Natural de Hanoi con el dominio int de hanoi.
Sobre la evaluaci´ on y soluci´ on de los casos del problema: variables locales y cuerpo del m´ etodo La instrucci´on fundamental de un m´etodo recursivo es una condicional simple if mediante la cual, tras comprobar si el caso actual del problema es el base (casoBase(x)) o el general (!casoBase(x)), se expresa la soluci´on asociada a ´este. As´ı, si casoBase(x) == true, si el valor de x es el de la talla del problema en su caso base, entonces metodoRecursivo devuelve en resMetodo la soluci´on correcta del problema para el caso base, la que denota en el esquema solucionBase(x) y sino, al cumplirse la Precondici´on metodoRecursivo devuelve en resMetodo la ✭✭adecuada✮✮ combinaci´ on de x con los resultados de metodoRecursivo para tallas del problema estrictamente menores que la que representa x, la que denota en el esquema combinar(x, resLlamada1, ..., resLlamadaK); M.Galiano,N.Prieto 9 1.
Una u ´ ltima observaci´on: para evitar que en metodoRecursivo se confundan el resultado del m´etodo recursivo y el de cada una de las llamadas recursivas se han utilizado distintas variables de TipoResultado: resMetodo representa la soluci´on del problema de talla x y resLlamada1, resLlamada2, ..., resLlamadaK, representan la soluci´on del mismo problema pero para tallas menores que x, respectivamente anterior1(x), anterior2(x), ..., anteriorK(x).
Sobre la correcci´ on de la soluci´ on: coherencia de las llamadas, terminaci´ on y correcci´ on En principio, al igual que para cualquier otro tipo de definici´on recursiva, la demostraci´on de la correcci´on de metodoRecursivo supone probar que tras finalizar su ejecuci´on al cabo de un tiempo finito, el resultado que obtiene representa la soluci´on correcta del problema; i.e.
probar, por ejemplo por Inducci´on, que metodoRecursivo termina y es correcto. Sin embargo y a´ un as´ı la compilaci´on y ejecuci´on de un m´etodo recursivo puede provocar errores si previamente no se ha comprobado la coherencia de sus llamadas. A saber, como en su caso general metodoRecursivo se invoca a s´ı mismo para las tallas menores anterior1(x)), ..., anteriorK(x), se tendr´an que realizar las siguientes comprobaciones: 1. Cualquier par´ametro actual o valores de x en cada llamada a metodoRecursivo es del dominio del problema. Lo que se puede denotar formalmente como sigue: sea x tal que Dominio(x) == true AND !casoBase(x), entonces AND AND AND Dominio(anterior1(x)) == true Dominio(anterior2(x)) == true ...
Dominio(anteriorK(x)) == true A modo de ejemplo, se comprueba ahora esta restricci´on para el par´ametro formal int n de hanoi, el u ´ nico que representa la talla del problema e interviene en la demostraci´on: sea x = n > 0 por Precondici´on; como en el caso general de hanoi n > 1 entonces anterior(x) = n-1 ≥ 1 y, por tanto, x = n > 0 como se quer´ıa demostrar.
2. Las llamadas de talla menor que x obtienen resultados del mismo tipo que el definido en la cabecera de metodoRecursivo a partir del mismo n´ umero de par´ametros, en el mismo orden y del mismo tipo que los definidos en la cabecera de metodoRecursivo.
Por ejemplo, el m´etodo hanoi propuesto cumple claramente esta restricci´on: cada una de las dos llamadas de talla menor que n, hanoi(n-1, origen, destino, auxiliar) y hanoi(n-1, auxiliar, origen, destino), retorna el mismo tipo de resultado que el definido en su cabecera, void, a partir del mismo n´ umero de par´ametros, cuatro, en el mismo orden y del mismo tipo que los definidos en su cabecera.
Por motivos que se evidenciar´an m´as tarde, resulta de inter´es presentar ahora dos pruebas de terminaci´on de un m´etodo recursivo alternativas a la ya conocida Prueba de Inducci´on. La primera consiste en enumerar las llamadas que origina la llamada principal o m´as alta desde otro m´etodo; por ejemplo, el n´ umero de llamadas que se realizan al invocar hanoi con n == N viene dado por la siguiente Ecuaci´on de Recurrencia: numLlamadas( N ) = 10 2 * numLlamadas( N - 1 ) si N > 1 0 si N = 1 1.
Resolviendo y acotando esta ecuaci´on se obtiene que numLLamadas( N ) ≃ 2N -1, un n´ umero finito a pesar de ser muy grande; por tanto, el n´ umero de llamadas es finito, lo que asegura la terminaci´on de la ejecuci´on de hanoi(N).
Ejercicio propuesto: para darse cuenta de la enorme cantidad de tiempo que puede llegar a consumir la ejecuci´on del m´etodo hanoi, o de por qu´e el fin del mundo llegar´a cuando los sacerdotes del templo de Brahma construyan una nueva torre, basta realizar un peque˜ no experimento: observar qu´e ocurre cuando se ejecuta el programa TestHanoi sucesivamente para N = 5, N = 10, N = 15 y N = 20.
**TestHanoi figura en la tabla de material did´ actico de los Contenidos PoliformaT del tema.
La segunda prueba consiste en demostrar que los valores de los par´ametros de las sucesivas llamadas conforman una sucesi´on ordenada decrecientemente que converge al valor para el que casoBase(x) == true; equivalentemente, si la talla del problema expresada por x decrece al menos una unidad en cada llamada recursiva, al cabo de un tiempo finito se debe alcanzar la talla del caso base. Formalmente, si xbase denota el valor para el que casoBase(x) == true, se debe demostrar que xbase ≤ anterior1(x) < x AND xbase ≤ anterior2(x) < x AND . . .
AND xbase ≤ anteriorK(x) < x 1.1.2.
Taxonom´ıa de la Recursi´ on Para plasmar cualquier estrategia inductiva de dise˜ no basta con instanciar el esquema general recursivo presentado. Es m´as, en funci´on del n´ umero de llamadas que se realicen en el caso general y de si el m´etodo combinar(x, resLlamada1, ..., resLlamadaK) se utiliza o no, cualquier instancia del esquema general se puede clasificar en base a la siguiente taxonom´ıa: Recursi´ on Lineal: cuando en su caso general un m´etodo recursivo genera una u ´nica llamada. Adem´as, en funci´on de si el resultado de esta llamada se combina o no para obtener el resultado del m´etodo, se distinguen los siguientes subtipos de Recursi´on Lineal: 1. Final: cuando el resultado de la llamada recursiva es el resultado del m´etodo recursivo, i.e. resMetodo = resLlamada = metodoRecursivo(anterior(x)); al no utilizarse el m´etodo combinar, la llamada recursiva es la u ´ ltima operaci´on que se realiza en cada invocaci´on de un m´etodo recursivo Lineal Final. Por ejemplo, el siguiente m´etodo recursivo es Lineal Final: /** n > 0 AND m > 0 */ static int maximoComunDivisor(int n, int m){ int resMetodo, resLlamada; if ( n == m ) resMetodo = n; else{ if ( n > m ) resLlamada = maximoComunDivisor(n-m, m); else resLlamada = maximoComunDivisor(n, m-n); resMetodo = resLlamada; } return resMetodo; } // maximoComunDivisor(n,m) calcula el mayor entero que divide a n y m M.Galiano,N.Prieto 11 1.
2. No Final: cuando el resultado de la llamada recursiva no es el resultado del m´etodo recursivo sino que debe combinarse de alguna forma con x para obtenerlo, i.e.
resMetodo = combinar(x, resLlamada). Por ejemplo, el siguiente m´etodo recursivo es Lineal No Final: /** n >= 0 */ static int factorial(int n){ int resMetodo, resLlamada; if ( n == 0 ) resMetodo = 1; else{ resLlamada = factorial(n-1); resMetodo = n * resLlamada; } return resMetodo; } // factorial(n) calcula n! Recursi´ on M´ ultiple: cuando en su caso general un m´etodo recursivo genera m´ as de una llamada en secuencia, como el m´etodo hanoi ya presentado o el que figura a continuaci´on: /** n >= 0 */ static int fibonacci(int n){ int resMetodo, resLlamada1, resLlamada2; if ( n <= 1 ) resMetodo = n; else { resLlamada1 = fibonacci(n-1); resLlamada2 = fibonacci(n-2); resMetodo = resLlamada1 + resLlamada2; } return resMetodo; } // fibonacci(n) calcula el t´ ermino n-´ esimo de la serie de Fibonacci Ejercicio propuesto: los m´etodos maximoComunDivisor, factorial y fibonacci que se acaban de presentar han sido dise˜ nados instanciando textualmente el esquema recursivo general.
En el programa RecursionNumerica que los contiene, modif´ıquense sus c´odigos para que no usen ninguna variable local y, por tanto, sean m´as compactos y efectivos.
**RecursionNumerica figura en la tabla de material did´ actico de los Contenidos PoliformaT del tema.
El tipo de Recursi´on de un m´etodo determina la estructura del conjunto de llamadas que origina su llamada principal desde otro m´etodo. As´ı, como la Recursi´on Lineal se caracteriza porque por cada llamada al m´etodo origina s´olo otra, la llamada m´as alta a un m´etodo recursivo lineal origina una Secuencia de Llamadas, cuyo primer elemento es la llamada m´as alta y cuyo u ´ ltimo elemento es la llamada para resolver el caso base. Por ejemplo, al invocar maximoComunDivisor(10,15) se origina la siguiente Secuencia de Llamadas: maximoComunDivisor(10, 15)→maximoComunDivisor(10, 5)→maximoComunDivisor(5, 5) Al igual que maximoComunDivisor(10, 15), cualquier m´etodo Lineal Final calcula el resultado demandado tras generar el u ´ ltimo elemento de su Secuencia de Llamadas, lo que concuerda con su definici´on de m´etodo Final: aquel cuyo resultado coincide con el de la u ´ nica llamada que origina. Para maximoComunDivisor, tras resolver maximoComunDivisor(n-m, m) o maximoComunDivisor(n, m-n) no es necesario ning´ un c´alculo adicional.
12 1.
Sin embargo, si el m´etodo recursivo es No Final, por definici´on, el resultado de la u ´ ltima llamada no es el resultado del m´etodo, que deber´a obtenerse recorriendo en sentido inverso hasta su primer elemento, la llamada m´as alta; en cada paso de este Recorrido el resultado de la llamada actual se obtiene combinando sus Datos con el resultado de la llamada anterior. Por ejemplo, al invocar factorial(4) se origina la siguiente Secuencia de Llamadas: factorial( 4 ) → factorial( 3 ) → factorial( 2 ) → factorial( 1 ) → factorial( 0 ) Cuando se genera el u ´ ltimo elemento de esta Secuencia, la llamada a factorial(0), su resultado es 1 y para obtener el resultado demandado se recorrer´a en sentido inverso la Secuencia y el resultado para cada llamada se calcula multiplicando su Dato por el resultado de la llamada anterior, ∀1 ≤ i ≤ 4: factorial(n) = n * factorial(n-1).
factorial( 4 ) → factorial( 3 ) → factorial( 2 ) → factorial( 1 ) → factorial( 0 ) 4 * 6 ← 3 * 2 ← 2 * 1 ← 1 * 1 ← 1 Finalmente, si un m´etodo es recursivo M´ ultiple, en lugar de una Secuencia tiene asociado ´ un Arbol de Llamadas; cada invocaci´on a un m´etodo de este tipo origina en su caso general ´ K>1 llamadas, lo que se puede representar jer´arquicamente mediante un Arbol donde cada uno de sus Nodos tiene tantos sucesores, Hijos, como n´ umero de llamadas en secuencia origina el ´ m´etodo en su caso general. As´ı, el Nodo Ra´ız del Arbol ser´a la llamada m´as alta y sus Hojas las llamadas para resolver el caso base. Por ejemplo, si se realiza la invocaci´on fibonacci(4) se ´ origina el Arbol Binario que se muestra en la siguiente figura, y en cuyos Nodos se ha indicado dentro de un c´ırculo el orden de generaci´on y dentro de un cuadrado el de terminaci´on: 9 5 3 3 2 1 8 fibonacci(3) fibonacci(2) fibonacci(1) 4 fibonacci(1) 1 1.1.3.
4 fibonacci(4) 6 7 fibonacci(2) fibonacci(1) 6 8 fibonacci(0) 7 9 fibonacci(0) 2 5 Ejecuci´ on de un m´ etodo recursivo: la Pila de la Recursi´ on En esta secci´on se estudia c´omo implementa la m´aquina Java la ejecuci´on de un m´etodo, recursivo o no, y qu´e recursos utiliza para ello. Como se ver´a pronto, conocer estos aspectos permite confrontar en t´erminos de eficiencia los m´etodos iterativos y sus equivalentes recursivos.
En primer lugar se recordar´a que para poder ejecutar cualquier m´etodo, por ejemplo el m´etodo main de una aplicaci´on, ´este debe ocupar una zona establecida de la memoria RAM del ordenador. Dicha zona consta principalmente de tres partes: 1. la zona reservada al c´odigo de la JVM, o Zona 1; 2. la zona reservada para las variables globales o de clase, o Zona 2; 3. la zona denominada Heap o memoria din´amica, subdividida a su vez en dos: la reservada a los objetos que se crean v´ıa new y el Stack o Pila.
M.Galiano,N.Prieto 13 1.
Cada vez que el interprete Java ejecuta la invocaci´on a un m´etodo (siguiendo el c´odigo situado en la Zona 1) se crea una estructura de Datos en el Heap que recibe el nombre de Registro de Activaci´ on y contiene toda la informaci´on local asociada a dicha ejecuci´on; b´asicamente, una copia de todos los par´ametros y variables locales presentes en la definici´on del m´etodo invocado y la direcci´on de la Zona 1 donde debe continuar el int´erprete Java al finalizar la ejecuci´on del m´etodo invocado. L´ogicamente, el Registro de Activaci´on desaparece del Heap, se borra, al finalizar la ejecuci´on del m´etodo invocado, cuando se liberan los recursos que ´esta consum´ıa.
Como es f´acil deducir, la ejecuci´on de un m´etodo recursivo es similar a la de un m´etodo no recursivo, pero por cada invocaci´on a s´ı mismo que realice se crea un nuevo Registro de Activaci´on, propio de esa llamada, sobre el u ´ltimo registro asociado al mismo m´etodo, cuya ejecuci´on queda pendiente. Y as´ı sucesivamente hasta que se termina de ejecutar la invocaci´on al mismo m´etodo en su caso base, momento en el cual se borra su registro asociado y se puede reanudar la ejecuci´on de la llamada inmediatamente anterior del mismo m´etodo que qued´o pendiente. As´ı, la u ´ ltima llamada pendiente ser´a la primera en seguir ejecut´andose. Esta mec´anica LIFO (Last In First Out) con la que se crean y borran los Registros de Activaci´on hace que la subarea del Heap donde se almacenan se denomine Pila de la Recursi´ on o Stack .
Asimismo, se dice que los Registros no se crean sino que se apilan, no se borran sino que se desapilan y en cada momento s´olo puede haber uno activo, el u ´ ltimo que entr´o.
Adem´as de su mec´anica, es importante resaltar que el uso del Registro de Activaci´on permite implementar cada llamada a un m´etodo recursivo como un clon de ´este, es decir una copia exacta pero distinta de la definici´on del m´etodo: los valores de sus par´ametros formales y variables locales var´ıan durante su ejecuci´on, sin que por ello quede alterada la de otras llamadas pendientes; la comunicaci´on entre llamadas queda garantizada perfectamente gracias al paso de par´ametros cuando se efect´ ua la llamada y a la devoluci´on de resultados cuando se efect´ ua el retorno.
Para ilustrar la implementaci´on de la ejecuci´on de un m´etodo recursivo que realiza la m´aquina Java consid´erese el m´etodo recursivo factorial; como muestra la siguiente figura para la invocaci´on factorial(4), cualquier Registro de Activaci´on asociado a cualquier llamada a factorial contiene una copia del par´ametro formal n, cuyo valor es el del par´ametro actual de la llamada y que a todos los efectos se considera como una variable local, y las variables locales resMetodo y resLlamada (resM y resLl en la figura por abreviar), que se siguen utilizando en este ejemplo con el u ´ nico prop´osito de facilitar la discusi´on: n=4 resM = ?? resLl = ?? As´ı los distintos estados de la Pila de la Recursi´on al ejecutar factorial(4) ser´ıan los que se ilustran en las siguientes figuras, en la primera los correspondientes a la inserci´on de Registros en la Pila y en la segunda los correspondientes a los borrados de su u ´ ltimo Registro.
14 1.
n=0 resM = ?? resLl = ?? n=4 resM = ?? resLl = ?? n=1 resM = ?? resLl = ?? n=1 resM = ?? resLl = ?? n=2 resM = ?? resLl = ?? n=2 resM = ?? resLl = ?? n=2 resM = ?? resLl = ?? n=3 resM = ?? resLl = ?? n=3 resM = ?? resLl = ?? n=3 resM = ?? resLl = ?? n=3 resM = ?? resLl = ?? n=4 resM = ?? resLl = ?? n=4 resM = ?? resLl = ?? n=4 resM = ?? resLl = ?? n=4 resM = ?? resLl = ?? ———————————————————————— n=0 resM = ?? resLl = ?? 1.1.4.
n=1 resM = ?? resLl = ?? n=1 resM = ?? resLl = ?? n=2 resM = ?? resLl = ?? n=2 resM = ?? resLl = ?? n=2 resM = ?? resLl = ?? n=3 resM = ?? resLl = ?? n=3 resM = ?? resLl = ?? n=3 resM = ?? resLl = ?? n=3 resM = ?? resLl = ?? n=4 resM = ?? resLl = ?? n=4 resM = ?? resLl = ?? n=4 resM = ?? resLl = ?? n=4 resM = ?? resLl = ?? n=4 resM = ?? resLl = ?? Iteraci´ on VS Recursi´ on Como se ha visto en el apartado anterior, un m´etodo recursivo es una forma alternativa de expresar un c´alculo repetitivo que podr´ıa describirse mediante un m´etodo iterativo. De hecho, se puede demostrar que a partir de un m´etodo recursivo dado se puede obtener su equivalente iterativo mediante la denominada Transformaci´on Recursivo-Iterativa. Aunque su forma general queda fuera del alcance de esta asignatura, es muy f´acil obtenerla para un m´etodo recursivo Lineal Final: el c´alculo generado por la llamada a un m´etodo de este tipo se puede interpretar como el tratamiento iterativo de su Secuencia de Llamadas asociada. As´ı, a cada llamada generada le corresponde un elemento de dicha Secuencia; la informaci´on asociada a cada elemento de dicha Secuencia est´a constituida por los valores de los par´ametros actuales de la llamada; el primer elemento de esta Secuencia corresponde a la llamada principal y el u ´ ltimo a la llamada para el caso base; el elemento siguiente a uno dado es el correspondiente a la llamada que ´este origina.
Por ejemplo, la versi´on iterativa de maximoComunDivisor(N,M) se obtiene como sigue: cada elemento de la Secuencia de Llamadas asociada a maximoComunDivisor(N,M) se caracteriza por los dos valores Naturales que corresponden a los par´ametros formales n y m de maximoComunDivisor; M.Galiano,N.Prieto 15 1.
el primer elemento de dicha Secuencia queda caracterizado por los valores de la llamada principal: n = N; m = M; el u ´ ltimo elemento de dicha Secuencia queda caracterizado por los valores de la llamada para el caso base, n == m; la llamada maximoComunDivisor(n,m) genera maximoComunDivisor(n-m,m) si (n > m); sino, maximoComunDivisor(n,m-n). As´ı el siguiente elemento de la Secuencia queda caracterizado por los valores n-m y m si (n > m); sino, los valores son n y m-n.
De esta forma, /** N > 0 AND M > 0 */ static int maximoComunDivisorIterativo(int N, int M) { int n = N, m = M; while ( n != m ) if ( n > m ) n = n - m; else m = m - n; return n; } Sin embargo, si la Recursi´on es No Final, en muchos casos es necesario utilizar como Estructura de Datos auxiliar una Pila; ´esta almacena los Datos de las llamadas anteriores y los mantiene accesibles para la correcta aplicaci´on del m´etodo combinar. M´as dif´ıcil a´ un resulta la Transformaci´on Recursivo-Iterativa en el caso de Recursi´on M´ ultiple, pues requiere el ´ tratamiento del Arbol de Llamadas asociado.
A pesar de las dificultades que puede entra˜ nar la Transformaci´on Recursivo-Iterativa, resulta necesaria siempre que la ejecuci´on del m´etodo recursivo suponga, frente a la del iterativo, un mayor consumo de espacio y/o tiempo. Por ejemplo, frente al coste Espacial del m´etodo recursivo factorial propuesto su versi´on iterativa requiere una reserva de memoria para s´olo un par de variables enteras y, lo que es m´as importante, esta necesidad de espacio es independiente del valor de n para el que se calcula el factorial; n´otese que la cantidad de espacio requerido por la versi´on recursiva es proporcional al n´ umero de Registros de Activaci´on que se almacenan en la Pila, esto es, es proporcional al valor de n para el que se calcule el factorial.
Otro ejemplo que demuestra lo inapropiada que puede resultar una versi´on recursiva de un m´etodo es fibonacci; n´otese la gran cantidad de c´alculos que se repiten al realizar una invocaci´on a fibonacci para un n´ umero mayor o igual que tres. Una versi´on iterativa que evita todas estas repeticiones es la siguiente, mucho m´as eficiente que la recursiva pero sin su claridad de dise˜ no: /** n >= 0 */ static int fibonacciIterativo(int n){ int f1 = 0, f0 = 1; while ( f1 < n ){ f1 = f0 + f1; f0 = f1 - f0; } return f1; } Un u ´ ltimo ejemplo significativo sobre el uso o no de la Recursi´on lo ofrece la soluci´on del problema de las Torres de Hanoi, de la que se presenta ahora una posible implementaci´on iterativa, para confrontarla con la recursiva hanoi ya estudiada: 16 1.
/** n > 0 */ static void hanoiIterativo(int n, String origen, String auxiliar, String destino){ int h = n; String a = origen, c = destino, b = auxiliar; String k; int no = 1; while ( no != 0 ){ while ( h != 2 ){ h--; k = b; b = c; c = k; no = 2 * no; } moverDisco(a,b); moverDisco(a,c); moverDisco(b,c); while ( (no % 2) != 0 ){ h++; k = a; a = b; b = k; no = no/2; } if ( no != 0 ){ moverDisco(a, b); k = a; a = c; c = b; b = k; no++; } } } Como es evidente, la versi´on iterativa de Hanoi, a´ un tendiendo la misma Complejidad Temporal que la recursiva, ni es clara ni parece la soluci´on natural que se obtiene tras la lectura del enunciado del problema. Pues bien, al igual que Hanoi, existen otros muchos problemas complejos que no se pueden abordar m´as que utilizando una estrategia de dise˜ no recursiva, aunque m´as tarde, v´ıa Transformaci´on Recursivo-Iterativa, se implementen iterativamente.
Ya para finalizar la secci´on y a modo de conclusi´on se ofrece la siguiente regla general: apl´ıquese la estrategia Inductiva u ´nicamente a la resoluci´ on de aquellos problemas lo suficientemente complejos como para merecerlo En base a ella, un problema que se puede solucionar mediante un sencillo bucle no lo merece; si es algo m´as complicado, una vez obtenido un primer dise˜ no recursivo y tras analizar su coste Espacial y Temporal, dec´ıdase si se obtiene su versi´on iterativa equivalente.
1.2.
Etapas del dise˜ no recursivo A la hora de realizar el dise˜ no de un m´etodo recursivo con cierta garant´ıa de ´exito, conviene considerar a modo de gu´ıa las siguientes etapas: 1. Definici´ on de la cabecera del m´ etodo: determinar su nombre, sus par´ametros formales y el tipo de ´estos, el tipo de su resultado y sus posibles Excepciones; adem´as, tal como indica el esquema general recursivo, se debe especificar su Precondici´on pues representa las restricciones sobre el dominio de sus Datos.
Esta primera etapa de definici´on es muy importante ya que en ella se pone de relieve la estructura recursiva del dominio de definici´on, talla del problema incluida, lo que facilita sobremanera la estrategia inductiva a seguir.
2. An´ alisis de Casos: hacer expl´ıcitos los casos base y general de la Recursi´on y establecer para cada uno de ellos las instrucciones pertinentes que los resuelven; en particular, hay que comprobar que cualquier elemento del dominio pertenece a uno u otro de los dos casos determinados.
3. Transcripci´ on del An´ alisis de Casos: codificaci´on en Java de la soluci´on propuesta en la etapa anterior.
4. Validaci´ on del dise˜ no: comprobar la coherencia y terminaci´on de sus llamadas; se sugiere probar la terminaci´on demostrando que la talla del problema decrece al menos una unidad en cada una de las llamadas del caso general y que alcanza la del caso base.
M.Galiano,N.Prieto 17 1.
A continuaci´on se ejemplifican estas etapas para el dise˜ no de m´etodos recursivos de Recorrido y B´ usqueda sobre un array gen´erico, que servir´a de dominio de definici´on de tales m´etodos y cuya naturaleza recursiva se pone de manifiesto en la siguiente definici´on: Sea T v[] un array gen´erico que representa una Secuencia de v.length Datos de Tipo T, denotada como v[0 ... v.length-1]. Se puede definir recursivamente v como la Secuencia formada por la primera componente de v, v[0], y la subSecuencia definida por el resto de v, i.e. el array v menos su primer componente o subarray v[1 ... v.length-1]. N´otese que, a su vez, el subarray v[1 ... v.length-1] puede definirse recursivamente del mismo modo y as´ı, sucesivamente, hasta que en una u ´ ltima descomposici´on factible el subarray correspondiente est´e vac´ıo, sin componentes.
An´alogamente, el array v se puede definir de forma recursiva y Descendente considerando el subarray v[0 ... v.length-2] y su u ´ ltima componente v[v.length-1]; en la siguiente figura se ilustra gr´aficamente esta descomposici´on, a la derecha de la Ascendente: 0 v.length−1 v 0 ...
1 v 0 v.length−1 ...
1 v.length−2v.length−1 v 1 v.length−1 ...
0 v.length−3v.length−2 ...
...
...
...
...
...
...
...
pos v.length−1 0 ...
pos ...
...
...
...
...
...
...
v.length−1 0 Naturalmente, para poder dise˜ nar un m´etodo recursivo que realice un Recorrido o B´ usqueda sobre un (sub)array v se debe disponer de tres Datos o par´ametros formales del m´etodo: el propio (sub)array v y las posiciones que marcan el inicio y el fin del Recorrido o la B´ usqueda a realizar sobre ´el en cada llamada. Estos tres par´ametros definen en cada llamada la talla del problema o n´ umero de componentes del (sub)array v[inicio...fin] sobre las que se realiza el Recorrido o la B´ usqueda, que viene dada por la expresi´on x = fin-inicio+1; por ejemplo, si en la llamada m´as alta a un m´etodo recursivo inicio = 0 y fin = v.length-1 entonces se explora todo el array v, pero si inicio = (v.length-1)/2 y fin = v.length-1 entonces el subarray de v a explorar es su u ´ ltima mitad.
Adem´as de los tres par´ametros mencionados, el dise˜ no de un m´etodo recursivo exige determinar el tipo de descomposici´on recursiva que se realiza, Ascendente o Descendente, pues tanto el caso base como la forma de progresar hacia ´este en el caso general var´ıan seg´ un se elija uno u otro. Espec´ıficamente, en una descomposici´on Ascendente de un array v el caso base se alcanza cuando inicio = fin+1, i.e. para una talla x = 0, y la forma de progresar hacia ´el en cada llamada es incrementar el valor de inicio, con lo que la talla x decrece en una 18 1.
unidad; as´ı, el rango de variaci´on de inicio ser´a 0 ≤ inicio ≤ v.length, mientras que fin mantiene constante su valor en la llamada m´as alta, fin = v.length-1. Sin embargo, en una descomposici´on Descendente el caso base se alcanza cuando fin = inicio-1 y la forma de progresar hacia ´el en cada llamada ser´a decrementar el valor de fin; as´ı, el rango de variaci´on de fin ser´a -1 ≤ fin ≤ v.length-1, mientras que inicio mantiene constante su valor en la llamada m´as alta, inicio = 0.
Como aplicaci´on de lo visto, se presentan e instancian en lo que sigue los esquemas recursivos de Recorrido y B´ usqueda sobre un array.
1.2.1.
Esquema recursivo de Recorrido de un array En base a la definici´on de Recorrido de un array v y la descomposici´on recursiva Ascendente de v, el esquema recursivo de Recorrido Ascendente es el siguiente: public static <T> void recorrer(T v[]){ recorrer(v, 0, v.length-1); } /** 0 <= inicio <= v.length AND fin = v.length-1 **/ private static <T> void recorrer(T v[], int inicio, int fin){ if ( inicio > fin ) visitarVacio(); else{ visitar(v[inicio]); recorrer(v, inicio+1, fin); } } N´otese que el m´etodo p´ ublico recorrer, el que se suele denominar gu´ıa, se define para ocultar la estructura recursiva del array v que muestran los par´ametros inicio y fin de la cabecera del m´etodo hom´onimo pero recursivo y privado. Con ello no se hace m´as que definir la soluci´on del problema de Recorrido de un array v de v.length componentes en t´erminos del Recorrido recursivo Ascendente del subarray v[inicio...fin] de talla x = fin-inicio+1 componentes; para hacer coincidir sus soluciones el m´etodo gu´ıa lanza o invoca al recursivo con los valores de inicio = 0 y fin = v.length-1, i.e. para una talla inicial X = v.length.
Obs´ervese tambi´en que el esquema presentado se puede simplificar substituyendo cualquier referencia al par´ametro formal fin por su valor en la llamada m´as alta v.length-1, pues como se expresa en la Precondici´on fin = v.length-1 en cualquier llamada recursiva a recorrer: public static <T> void recorrer(T v[]){ recorrer(v, 0); } /** 0 <= inicio <= v.length **/ private static <T> void recorrer(T v[], int inicio){ if ( inicio == v.length ) visitarVacio(); else{ visitar(v[inicio]); recorrer(v, inicio+1); } } Ahora bien, la simplificaci´on realizada conduce a plantear un mismo problema, el del Recorrido de un array v de v.length componentes, en t´erminos de un m´etodo recursivo menos general: eliminar el par´ ametro fin supone que el m´ etodo privado s´ olo represente la soluci´ on al problema para un tipo particular de subarray v, aquel en el que forzosamente la u ´ ltima posici´on a visitar es v.length-1. Esta p´erdida de generalidad no resulta significativa en un gran n´ umero de problemas, pero no se puede obviar a la hora de realizar dise˜ nos recursivos correctos.
M.Galiano,N.Prieto 19 1.
Ejercicio propuesto: en el programa TestRecorrido se ha definido una instancia del esquema recursivo de Recorrido Ascendente en la que el m´etodo visitar s´olo contiene la instrucci´on ✭✭System.out.println(v[inicio]);✮✮ y visitarVacio() no hace nada; adem´as, el m´etodo gu´ıa recorrer se invoca sobre un array de String v={"hoy","no","hace","sol"}.
Ejec´ utese dicho programa y obs´ervese su resultado. Modif´ıquese entonces su m´etodo recursivo as recorrer de forma que la instrucci´on ✭✭System.out.println(v[inicio]));✮✮ aparezca detr´ de la llamada recorrer(v,inicio+1, fin) y no antes ¿Qu´e resultado se obtiene? ¿Por qu´e? **TestRecorrido figura en la tabla de material did´ actico de los Contenidos PoliformaT del tema.
Tras resolver el ejercicio anterior es f´acil plantear el siguiente Esquema recursivo de Recorrido Descendente: public static <T> void recorrer(T v[]){ recorrer(v, 0, v.length-1); } /** inicio = 0 AND -1 <= fin < v.length */ private static <T> void recorrer (T v[], int inicio, int fin){ if ( fin < inicio ) visitarVacio(); else{ visitar(v[fin]); recorrer(v, inicio, fin - 1); } } Para simplificar este esquema, n´otese, basta con eliminar de su c´odigo el par´ametro inicio: public static <T> void recorrer(T v[]){ recorrer(v, v.length-1); } /** -1 <= fin < v.length */ private static <T> void recorrer (T v[], int fin){ if ( fin == -1 ) visitarVacio(); else{ visitar(v[fin]); recorrer(v, fin-1); } } Cuesti´ on: presentados los esquemas recursivos de Recorrido, ¿cu´al de ellos resulta m´as natural elegir para imprimir en orden inverso las componentes de un array? Ya en general, la elecci´on del esquema Ascendente o Descendente de Recorrido de un array para cada problema particular que se plantee, o la descomposici´on recursiva subyacente a realizar, debe ser aquella que permita resolverlo de la manera m´as natural y eficaz posible; el ejemplo que se plantea ahora servir´a para terminar de ilustrar este punto.
Ejemplo: suma recursiva de las componentes de un array de Integer 1. Definici´ on de la cabecera del m´ etodo: por el enunciado del ejemplo, podr´ıa ser: /** 0 <= inicio <= v.length AND fin = v.length-1 */ private static int sumar(Integer v[], int inicio, int fin){ int resMetodo, resLlamada; ...
return resMetodo; } // sumar(v, inicio, fin) == i = inicio, ..., fin v[i].intValue() Entonces, el m´etodo gu´ıa (p´ ublico) desde el que se lanza sumar ser´ıa: public static int sumar(Integer v[]){ return sumar(v, 0, v.length-1); } 20 1.
2. An´ alisis de Casos: como la suma de cero elementos es cero, si el array v est´a vac´ıo o su talla es 0, casoBase(x) == ( inicio > fin ) y visitarVacio() == resMetodo = 0; sino, !casoBase(x), cuando inicio ≤ fin, la suma de las componentes del subarray v[inicio...fin] se puede expresar como la suma de su primera componente v[inicio] y la de las componentes del subarray v[inicio+1...fin]. Equivalentemente, resLlamada = sumar(v, inicio+1, fin); resMetodo = v[inicio] + resLlamada; 3. Transcripci´ on del An´ alisis de Casos a Java, sin usar fin pues siempre vale v.length-1: /** 0 <= inicio <= v.length */ private static int sumar(Integer v[], int inicio){ int resMetodo, resLlamada; if ( inicio == v.length ) resMetodo = 0; else{ resLlamada = sumar(v, inicio+1); resMetodo = v[inicio] + resLlamada; } return resMetodo; } // sumar(v, inicio) == i = inicio, ..., v.length-1 v[i].intValue() Alternativamente, escrito de forma m´as compacta se tendr´ıa: private static int sumar(Integer v[], int inicio){ if ( inicio == v.length ) return 0; return v[inicio] + sumar(v, inicio+1) } y su m´etodo gu´ıa, p´ ublico, ser´ıa el siguiente: public static int sumar(Integer v[]){ return sumar(v, 0); } 4. Validaci´ on del dise˜ no. Al examinar el c´odigo se observa lo siguiente: en el caso general, en cada llamada la talla del problema decrece una unidad porque inicio se incrementa en una unidad; por tanto, como antes de efectuarse la llamada inicio < v.length, tras incrementarse puede llegar a alcanzar el valor v.length; en cualquiera de los dos casos establecidos, los valores de los par´ametros formales siempre cumplen la Precondici´on: v porque permanece inalterado en cualquier llamada y en cuanto a inicio, toma valores en el rango [0 ... v.length] porque su valor en la llamada m´as alta, sumar(v, 0), se incrementa siempre en uno hasta llegar en el caso base a v.length.
1.2.2.
Esquema recursivo de B´ usqueda de un Dato b en un array Para obtener un esquema recursivo de B´ usqueda se puede plantear el siguiente An´alisis de Casos: sea v[inicio...fin], 0 ≤ inicio ≤ v.length AND -1 ≤ fin < v.length, el subarray de talla x = fin-inicio+1 donde se busca el Dato b; si x = 0, i.e. el subarray est´a vac´ıo, obviamente b no est´a en ´el y el resultado de buscar en su caso base es -1, el habitual en casos de B´ usqueda fallida cuando no se lanza Excepci´on; si por el contrario x > 0, i.e. el subarray contiene al menos una componente, en base a una descomposici´on Ascendente de ´este, bien v[inicio].equals(b) y el resultado de buscar es inicio o bien !v[inicio].equals(b) y se deber´a continuar buscando en el subarray v[inicio+1...fin]. En base a este an´alisis, se propone el siguiente esquema recursiva de B´ usqueda Ascendente de b en un array v: M.Galiano,N.Prieto 21 1.
public static <T> int buscar(T v[], T b){ return buscar(v, b, 0, v.length-1); } /** 0 <= inicio <= v.length AND fin = v.length-1 */ private static <T> int buscar(T v[], T b, int inicio, int resMetodo = -1; if ( inicio <= fin ) if ( v[inicio].equals(b) ) resMetodo=inicio; else return resMetodo; } //buscar(v,b,inicio,fin) == -1 AND ∀i: inicio≤i≤fin: //buscar(v,b,inicio,fin) == i: inicio≤i≤fin: v[i]=b int fin){ resMetodo=buscar(v,b,inicio+1,fin); v[i]!=b OR AND ∀j:inicio≤j<i: v[j]!=b Obs´ervese que, al igual que para el Recorrido recursivo y por los mismos motivos, el m´etodo recursivo y privado buscar es lanzado por el m´etodo gu´ıa hom´onimo y p´ ublico. N´otese adem´as c´omo el An´alisis de Casos realizado se refleja en su dise˜ no: por motivos puramente sint´acticos del lenguaje Java resMetodo se inicializa en cada llamada a -1, el resultado de la B´ usqueda para el caso base; dicho valor s´olo se modifica si el caso que expresan los par´ametros de la llamada es distinto del base, i.e. si se busca b en un subarray donde inicio ≤ fin.
Adem´as, al tratarse de una B´ usqueda tambi´en en el caso general se puede obtener el resultado del m´etodo sin efectuar llamada: como ya se ha indicado, si v[inicio].equals(b) el resultado es inicio; sino, se debe seguir recorriendo v en busca de b -recu´erdese que en el Peor de los Casos, cuando b no est´a en v, cualquier B´ usqueda se transforma en Recorrido.
Ejercicio propuesto: obtener los esquemas recursivos de B´ usqueda Ascendente simplificada, sin par´ametro fin, Descendente y Descendente simplificada.
Para concluir con la presentaci´on de los esquemas recursivos, y para subrayar que la elecci´on de un esquema Ascendente o Descendente no es arbitraria, se aborda el siguiente ejemplo.
Ejemplo: obtenci´ on de la posici´ on de la ´ ultima aparici´ on de un Dato b en un array El problema planteado admite en principio dos soluciones: eligiendo una descomposici´on recursiva Ascendente de v, un Recorrido del subarray v[inicio...fin] en el que se comprueba si cada elemento visitado es igual a b; eligiendo una descomposici´on recursiva Descendente de v, una B´ usqueda de la primera aparici´on de b en el subarray v[inicio...fin].
Aunque ambas son correctas, el criterio de eficiencia conduce a elegir la segunda soluci´on por presentar un caso mejor de coste independiente de la talla. Para obtener entonces el m´etodo Java correspondiente los pasos son: 1. Definici´ on de la cabecera del m´ etodo, y la del m´etodo gu´ıa que lo lanzar´a: /** 0 <= inicio <= v.length AND fin = v.length-1 */ private static <T> int ultimaP(T v[], T b, int inicio, int fin){ int resMetodo; ... return resMetodo; } // ultimaP(v,b,inicio,fin) == -1 AND ∀i: inicio≤i≤fin: v[i] != b OR // ultimaP(v,b,inicio,fin) == i:inicio≤i≤fin: v[i]=b AND ∀j:i<j≤fin: v[j]!=b public static <T> int ultimaP(T v[], T b){ return ultimaP(v, b, 0, v.length-1); } 22 1.
2. An´ alisis de Casos: si v es un array vac´ıo obviamente b no est´a en v. Por tanto, el caso base de ultimaP es aquel en que fin > inicio y tiene como resultado resMetodo = -1; sino, cuando fin ≥ inicio, en base a una descomposici´on Descendente de v, bien v[fin] es la primer aparici´on de b en v -por lo que el resultado de ultimaP es fin -o bien no lo es y se deber´a continuar con su B´ usqueda en v[inicio...fin-1]: if (v[fin].equals(x)) resMetodo = fin; else resMetodo = ultimaP(v, b, inicio, fin-1); 3. Transcripci´ on del An´ alisis de Casos a Java, en la que no tiene sentido usar inicio: private static <T> int ultimaP(T v[], T b, int fin){ int resMetodo = -1; if ( fin > -1 ) if (v[fin].equals(b)) resMetodo = fin; else resMetodo = ultimaP(v, b, fin-1); return resMetodo; } Su m´etodo gu´ıa, p´ ublico, ser´ıa: public static <T> int ultimaP(T v[], T b){ return ultimaP(v, b, v.length-1); } 4. Validaci´ on del dise˜ no. Al examinar el c´odigo se observa que en el caso general, en cada llamada la talla del problema decrece una unidad porque se decrementa fin; por tanto, como antes de producirse la llamada fin > -1, tras decrementarse en uno puede llegar a alcanzar el valor -1; en cualquiera de los dos casos establecidos, los valores de los par´ametros formales siempre cumplen la Precondici´on: v y b porque permanecen inalterados en cualquier llamada y en cuanto a fin, toma valores en el rango [-1 ... v.length-1] porque su valor en la llamada m´as alta, ultimaP(v, b, v.length-1), se decrementa siempre en uno hasta llegar en el caso base al valor -1.
Ejercicios propuestos: el programa RecursionArray contiene los m´etodos recursivos ultimaP y sumar presentados en esta secci´on. Se pide: 1. A˜ nadir a dichos m´etodos las l´ıneas de c´odigo necesarias para poder trazar su ejecuci´on, i.e. para mostrar por pantalla la talla del problema que resuelven en cada llamada que origine su ejecuci´on, los datos de tal llamada y sus resultados. Hecho esto, ejecutar sumar para el array de Integer {1, 2, 3, 4} y ultimaP para el Integer b = 5 y los array {1, 2, 3, 4} y {1, 2, 3, 5}; en base a las trazas obtenidas, contestar para cada uno de los m´etodos las siguientes preguntas: ¿que tipo de Recursi´on presenta? ¿cu´anto y c´omo disminuye la talla en cada una de sus llamadas? ¿cu´antas llamadas genera su invocaci´on m´as alta? 2. Incluir en RecursionArray los dise˜ nos de los m´etodos recursivos que se especifican a continuaci´on, con instrucciones de traza incluidas: invertir, que invierte in-situ las componentes de un array gen´erico dado v; maximo, que obtiene la posici´on del m´aximo de un array gen´erico dado v; minimo, que obtiene la posici´on del m´ınimo de un array gen´erico dado v; esSumaIgualA, que comprueba si un cierto n´ umero Natural b es igual a la suma de todas las componentes de un array de Naturales dado v; capicua, que comprueba si un array gen´erico dado v es capic´ ua.
**RecursionArray figura en la tabla de material did´ actico de los Contenidos PoliformaT del tema.
M.Galiano,N.Prieto 23 1.
1.3.
Coste Espacial y Temporal de un m´ etodo y su an´ alisis En esta u ´ ltima secci´on del apartado se revisan todos los conceptos relacionados con el coste Espacial y Temporal de un m´etodo, el criterio efectivo que permite comparar tal m´etodo con cualquier otro que resuelva el mismo problema y, por tanto, sin cuyo an´alisis o estimaci´on no puede darse por concluido su dise˜ no. Tal revisi´on sirve como imprescindible pre´ambulo al siguiente apartado, en el que el criterio de coste se incorporar´a al proceso de dise˜ no para poder exigir que el m´etodo que de ´el resulte sea no s´olo correcto sino el m´as eficiente de todos los que resuelven un determinado problema.
1.3.1.
Revisi´ on de conceptos y notaci´ on El criterio fundamental que permite comparar los distintos m´etodos que resuelven un mismo problema es su eficiencia, o el consumo de recursos que su ejecuci´on provocar´a: el m´etodo m´as eficiente, el mejor, ser´a aquel que menos recursos requiera para su ejecuci´on. Visto que los recursos b´asicos de un ordenador son la memoria (RAM) y el tiempo de CPU, la eficiencia de un m´etodo se expresa en t´erminos de su coste Espacial o medida del espacio que ocupa en memoria a lo largo de su ejecuci´on y su coste Temporal o medida del tiempo empleado por ´este para ejecutarse y dar un resultado a partir de los Datos de entrada.
En general, el coste de un m´etodo depender´a de dos tipos de factores: los propios del problema que resuelve -su talla e instancias y la estrategia de resoluci´on que implementa- y los dependientes del entorno de Programaci´on donde se ejecutar´a finalmente -tipo de ordenador, carga del sistema, lenguaje y compilador o int´erprete, etc. Por tanto, las dos aproximaciones al estudio de la eficiencia de un m´etodo son: el an´alisis Te´orico o a-priori, consistente en obtener una expresi´on matem´atica (cota) del coste del m´etodo en funci´on de los factores propios del problema que resuelve, y el an´alisis Experimental o a-posteriori, consistente en medir los tiempos de ejecuci´on del m´etodo para diversos casos de prueba (entradas) en un ordenador, lenguaje y compilador concretos. Evidentemente un tipo de an´alisis no excluye al otro, son complementarios, pero s´ı que hay un orden de precedencia entre ellos: si el an´alisis Te´orico ya indica que el coste intr´ınseco del m´etodo es impracticable o peor que el de otro m´etodo existente que resuelve el mismo problema no ser´a necesario implantarlo en sistema alguno, lo que supone un ahorro de tiempo y esfuerzo considerable. Es por ello que en lo que sigue s´olo se tratar´an los aspectos relacionados con el an´alisis Te´orico o a-priori del coste de un m´etodo, dejando para las pr´acticas el an´alisis a-posteriori.
Coste a-priori de un m´ etodo El coste a-priori de un m´etodo es una medida de los recursos (tiempo o memoria) que ´este emplea para ejecutarse independiente del entorno de programaci´ on donde lo haga.
Esta definici´on plantea una pregunta obvia: ¿c´omo medir el tiempo o el espacio que un m´etodo emplea en su ejecuci´on si ´este no se est´a ejecutando en m´aquina alguna? La respuesta es que el coste a-priori de un m´etodo, Temporal o Espacial, no es un valor, sino una funci´on matem´atica que expresa el tiempo o la memoria que su ejecuci´on requiere en funci´on de los factores propios de ´este; a dicha funci´on se le denomina Complejidad, Temporal o Espacial, quedando la sutil diferencia entre los t´erminos Complejidad y coste oculta tras el abuso del lenguaje que se realiza en la pr´actica, donde un t´ermino se utiliza por otro sin m´as.
24 1.
Como en su d´ıa se discuti´o en Programaci´on de primer curso, la unidad de tiempo en la que se expresa el coste Temporal de un m´etodo es el paso de programa y, por tanto, cualquier m´etodo concreto de c´alculo de la funci´on Complejidad consiste en contar los pasos de programa que ´este realiza durante su ejecuci´on. Si se recuerda, para un m´etodo iterativo el c´alculo de su Complejidad Temporal se basa en suponer que su instrucci´ on cr´ıtica, i.e. la que se ejecuta por lo menos con tanta frecuencia como cualquier otra del m´etodo, tarda en ejecutarse un paso de programa; de donde el m´etodo tardar´a tantos pasos de programa como n´ umero de veces se repita su instrucci´ on cr´ıtica. En el caso de un m´etodo recursivo, el planteamiento utilizado ocasionalmente hasta ahora era el siguiente: si una llamada recursiva tarda en ejecutarse un n´ umero dado de pasos de programa, x por ejemplo, el m´etodo tardar´a en ejecutarse x multiplicado por el n´ umero de llamadas que origina su llamada m´as alta (calculable por Inducci´on); como es f´acil deducir, este producto no se precisar´a completamente hasta que no se determine el n´ umero de pasos de programa que tarda una llamada recursiva en ejecutarse, lo que se estudiar´a un poco m´as adelante.
As´ı mismo, y como tambi´en se discuti´o el curso pasado, el coste o n´ umero de pasos de programa que un m´etodo realiza durante su ejecuci´on depende de dos factores: el tama˜ no o talla del problema y, para una talla dada, la instancia del problema.
El primero de ellos, la talla del problema, se define como la cantidad o magnitud de los Datos que se deben procesar y, como su nombre indica, es m´as una caracter´ıstica del problema que se quiere resolver y no tanto del m´etodo que se emplee para ello; por ejemplo e independientemente de la estrategia de resoluci´on, la talla del problema de la Ordenaci´on es el n´ umero de componentes del array que se desea ordenar, la del c´alculo del factorial de un n´ umero es la magnitud de tal n´ umero, etc. Es por ello que la Complejidad Temporal (Espacial) de un m´etodo a se define como una funci´on positiva no decreciente del tiempo (espacio) que a necesita para ejecutarse en base a la talla x del problema, lo que se denota como Ta (x) generalmente.
En cuanto al segundo factor mencionado, una instancia de un problema es aquel conjunto de configuraciones de talla dada de sus Datos para las que el comportamiento del m´etodo que lo resuelve, y por tanto su coste, es el mismo. As´ı por ejemplo el problema de Recorrido de un array de talla dada presenta una u ´ nica instancia, el conjunto de todas y cada una de las posibles presentaciones de las componentes del array, pues el tiempo que se emplea para resolverlo no depende de la presentaci´on particular de las componentes del array sino de lo que se tarda en visitar cada una de ellas; sin embargo, si sobre el mismo array se realiza una B´ usqueda entonces el n´ umero de instancias del problema es la talla del array m´as uno, pues adem´as de aquella en la que el Dato a buscar no est´a en el array existen tantas instancias en las que el Dato que se busca s´ı est´a en el array como posiciones v´alidas tenga ´este (puede ser el primero del array o el segundo o ... o el u ´ ltimo).
En funci´on de lo expuesto, si un m´etodo resuelve un problema que para una talla dada s´olo presenta una instancia entonces su coste Temporal es el n´ umero de pasos de programa que requiere la ejecuci´on de tal instancia, que se calcular´a de una forma u otra seg´ un el m´etodo sea recursivo o iterativo. Si por el contrario se ha detectado m´as de una instancia para una talla dada su coste se establece calculando su Complejidad en los siguientes casos: M.Galiano,N.Prieto 25 1.
En el Peor de los Casos, o para aquella instancia que obliga a que el m´etodo a realice el m´aximo n´ umero de c´alculos, i.e. instancia que da lugar al Peor coste; en este caso la Complejidad Temporal se denota Ta P (x).
A partir de esta definici´on es f´acil deducir que el comportamiento del m´etodo a jam´as puede ser peor que el que presenta en su Peor de los Casos, para ninguna otra instancia; por tanto, y esto es lo realmente importante, Ta P (x) es una cota superior del coste (comportamiento) Temporal general del m´etodo a.
En el Mejor de los Casos, o para aquella instancia que obliga a que el m´etodo en cuesti´on realice el m´ınimo n´ umero de c´alculos, i.e. instancia que da lugar al Mejor coste; en este caso la Complejidad Temporal se denota Ta M (x).
De nuevo es f´acil deducir que el comportamiento del m´etodo a jam´as ser´a mejor que el que presenta en su Mejor de los Casos, para ninguna otra instancia, de donde el coste Ta M (x) es una cota inferior del coste (comportamiento) Temporal general del m´etodo a; n´otese que aunque no es balad´ı, esta informaci´on no resulta tan significativa como la que proporciona Ta P (x).
En Promedio o coste Medio, que se define como la media de la Complejidad del m´etodo a para todas y cada uno de sus instancias. En este caso, la Complejidad Temporal se denotar´a Ta µ (x), y representar´a el comportamiento medio del m´etodo; desgraciadamente, a pesar de que este coste es el que m´as informaci´on proporciona sobre el comportamiento de un m´etodo, su c´alculo es en general dif´ıcil de realizar: no s´olo exige conocer todas las instancias del problema y su Complejidad, sino tambi´en, y aqu´ı reside el problema principal, la probabilidad con la que cada una de ´estas se dan.
Coste Asint´ otico de un m´ etodo y su notaci´ on Como se acaba de enunciar, el coste a-priori de un m´etodo se expresa como una funci´on no decreciente de la talla del problema, de donde se podr´ıa deducir que comparar costes es comparar directamente tales funciones. Sin embargo, si se atiende a las siguientes consideraciones, tal conclusi´on resulta precipitada y se puede mejorar sensiblemente: la determinaci´on de la expresi´on exacta de la funci´on Complejidad, adem´as de una tarea dif´ıcil, no tiene mucho sentido si se considera que distintas decisiones sobre qu´e es un paso de programa conducen a funciones de coste que s´olo difieren en constantes multiplicativas o aditivas. Es m´as, como se argumenta en los dos items siguientes, tales diferencias no resultan significativas a la hora de establecer si, para tallas suficientemente grandes e independientemente del entorno de Programaci´on, un determinado m´etodo se comporta mejor, peor o equivalentemente que otro; para valores suficientemente grandes de la talla, el valor de la funci´on Complejidad est´a completamente determinado por su t´ermino dominante; el valor exacto del coeficiente del t´ermino dominante de la funci´on Complejidad no se conserva al cambiar de entorno de programaci´on.
A partir de lo anterior, es f´acil obtener las siguientes conclusiones: 26 1.
1. Cuando se analiza el coste a-priori de un m´etodo determinado, el objetivo es conocer, m´as que la expresi´on exacta de su funci´on Complejidad, qu´e tipo de dependencia muestra con la talla del problema o su Tasa de Crecimiento. Se habla entonces de coste Asint´ otico o Complejidad Asint´ otica, seg´ un se haga referencia, respectivamente, al comportamiento de un m´etodo o a la expresi´on formal que lo representa; aunque la diferenciaci´on entre ambos t´erminos se debe conocer, como es habitual, en la pr´actica se utilizan indistintamente en un claro abuso del lenguaje.
2. Comparar costes es comparar las Tasas de Crecimiento de las funciones Complejidad involucradas; por ejemplo, si el coste de un m´etodo viene expresado mediante una funci´on Complejidad que es un polinomio, su monomio de mayor grado es el que determina su Tasa de Crecimiento o Complejidad Asint´otica (constante, lineal, cuadr´atica, c´ ubica, etc.) 3. La notaci´ on Asint´ otica es la herramienta formal que permite expresar de forma sencilla y clara el coste Asint´otico de un m´etodo: como, recu´erdese, O(f(x)) define el conjunto de funciones en x que son como m´aximo del orden de f(x), Ω(f(x)) el de las que son como m´ınimo del orden de f(x) y Θ(f(x)) el de las que son exactamente del orden de f(x), entonces, dado un m´etodo a, su coste Asint´otico se puede obtener para cualquiera de sus instancias como sigue: Obt´engase a partir de Ta P (x) una funci´on de cota f(x) que sea exactamente de su mismo orden, que la acote superior e inferiormente, lo que se nota Ta P (x)∈Θ(f(x)); si no fuera posible obtener una cota tan precisa, f(x) ser´a al menos una cota superior de Ta P (x), esto es Ta P (x) ∈ O(f(x)).
Una vez obtenido el coste Asint´otico en el Peor de los Casos, se puede deducir que para cualquier instancia a no se puede comportar peor que en el Peor de los Casos o, lo que es lo mismo, que Ta (x) ∈ O(f(x)).
Obt´engase a partir de Ta M (x) una funci´on de cota f(x) tal que Ta M (x) ∈ Θ(f(x)); si no fuera posible obtener una cota tan precisa, al menos Ta M (x) ∈ Ω(f(x)).
A partir de este resultado, como para cualquier instancia a no se puede comportar mejor que en el Mejor de los Casos, Ta (x) ∈ Ω(f(x)).
En el caso de que el m´etodo a no presente instancias significativas, o que coincidan las cotas para el Peor y Mejor de sus Casos, entonces Ta (x) ∈ Θ(f(x)).
Para terminar, a modo de recordatorio y para su uso posterior, en la siguiente tabla se muestran las funciones de cota m´as frecuentes en el an´alisis del coste Asint´otico de un m´etodo -funci´on, nombre y notaci´on Asint´otica; el hecho de que aparezcan ordenadas ascendentemente facilitar´a la comparaci´on por eficiencia de los diversos m´etodos que resuelven un mismo problema.
Funci´ on c log x log2 x x x ∗ logx x2 x3 2x Nombre constante logar´ıtmica logar´ıtmica al cuadrado lineal x ∗ logx cuadr´ atica c´ ubica exponencial Notaci´ on Asint´ otica Θ(1) Θ(log x) Θ(log2 x) Θ(x) Θ(x ∗ logx) Θ(x2 ) Θ(x3 ) Θ(2x ) M.Galiano,N.Prieto 27 1.
Metodolog´ıa general para el an´ alisis del coste Temporal de un m´ etodo La aplicaci´on ordenada y sistem´atica de los conceptos revisados hasta ahora proporciona una metodolog´ıa general para el an´alisis del coste Temporal de un m´etodo dado. Tal metodolog´ıa se presenta enunciando los pasos que la conforman y aplic´andolos al an´alisis del coste del m´etodo de Fusi´ on o Mezcla Natural, que dados dos array a y b de int ordenados ascendentemente construye uno nuevo tambi´en ordenado: public static int[] fusion(int a[], int b[]){ int max = a.length+b.length; int res[] = new int[max]; int i = 0, j = 0, k = 0; while ( i < a.length ) && ( j < b.length ) ){ if ( a[i] < b[j] ) res[k] = a[i++]; else res[k] = b[j++]; k++; } for ( int r = i; r < a.length; r++ ) res[k++] = a[r]; for ( int r = j; r < b.length; r++ ) res[k++] = b[r]; return res; } El an´alisis del coste Temporal de un m´etodo, y en particular el de fusion, se realiza siguiendo los pasos que se enuncian a continuaci´on: 1. Determinar la talla del problema que resuelve el m´ etodo a analizar y, siempre que sea posible, expresarla en t´erminos de sus par´ametros; para ello se deber´a estudiar, b´asicamente, c´omo y en funci´on de qu´e par´ametros se obtiene el resultado del m´etodo.
As´ı por ejemplo, para determinar la talla del problema que resuelve fusion resulta imprescindible analizar c´omo se construye res, el array resultado de la fusi´on de a y b: en un primer bucle, mientras queden componentes de a o b por visitar, en cada iteraci´on k se deposita en res la k-´esima menor componente de la uni´on de a y b, a[i] o b[j], pues por Precondici´on tanto a como b est´an ordenados ascendentemente; una vez termina el Recorrido de uno de los dos array, las componentes del otro se depositan directamente en res mediante un segundo bucle, pues obviamente s´olo pueden ser mayores que las que ya forman parte de res. Por tanto, la talla del problema que resuelve fusion, o el n´ umero de datos que se deben manipular para construir su resultado, es la de res, la suma de las tallas de a y b dada por la expresi´on x = a.length + b.length.
2. Determinar las posibles instancias significativas del problema: se eval´ ua si la Complejidad del m´etodo var´ıa, para una talla dada del problema, en funci´on de la presentaci´on de los Datos y, si es as´ı, se identifican su Peor y Mejor de los Casos.
En el caso de fusion queda patente de la discusi´on anterior que la construcci´on de res no presenta instancias significativas, pues siempre supone visitar todos y cada uno de los datos que componen a y b, independientemente de su presentaci´on.
3. Determinar el coste Asint´ otico del m´ etodo en dos fases: en la primera, calcular y acotar la Complejidad del m´etodo para cada instancia significativa detectada, Ta (x) si no tiene ninguna y las funciones Ta P (x) y Ta M (x) para el Peor y Mejor de los Casos respectivamente; en la segunda, establecer el coste Asint´otico del m´etodo como sigue: si no existen instancias significativas o bien coinciden sus cotas de Complejidad, entonces Ta (x) ∈ Θ(f(x)); sino, en el caso en que Ta P (x) ∈ Θ(f(x)) y Ta M (x) ∈ Θ(g(x)) se tiene respectivamente que Ta (x) ∈ O(f(x)) y Ta (x) ∈ Ω(g(x)).
28 1.
Para fusion, al no haber instancias significativas el c´alculo de su funci´on Complejidad se realiza como sigue: si se toma como instrucci´on cr´ıtica k++, pues representa la posici´on de la siguiente componente de res a construir, se tiene que Tfusion (x) = Σk=0...x 1 = x-1, un polinomio que se puede acotar tanto superior como inferiormente por x, i.e. por su monomio de mayor grado. Por tanto, Tfusion (x) ∈ Θ(x).
A las etapas que se acaban de presentar cabe a˜ nadir una u ´ ltima en el caso de que se est´e analizando el coste de un m´etodo recursivo: tras haber obtenido su coste a-priori se hace imprescindible valorar detenidamente si la cantidad de recursos extra, sobretodo de memoria RAM, que su ejecuci´on requiere supone un coste extra lo suficientemente elevado, y que claro est´a no tiene su equivalente iterativo, como para desaconsejar su uso.
1.3.2.
Expresi´ on de la Complejidad Temporal de un m´ etodo recursivo: Ecuaciones o Relaciones de Recurrencia Como ya se ha indicado, la expresi´on y c´alculo del coste Espacial y Temporal de un m´etodo recursivo se establece a partir de la expresi´on y c´alculo del coste de una cualquiera de las llamadas que provoca la invocaci´on de su ejecuci´on. Espec´ıficamente, la funci´on Complejidad Espacial de un m´etodo recursivo se expresa como la suma de las Complejidades de cada una de las llamadas recursivas que pueden coexistir en memoria como resultado de su llamada principal. Por ejemplo, sea el m´etodo recursivo factorial como sigue: static int factorial(int n){ if ( n == 0 ) return 1; return n * factorial(n-1); } Como int n es el par´ametro que representa la talla del problema, la magnitud del valor del que se calcula el factorial, suponiendo que el n´ umero de posiciones de memoria que ocupa dicho n es constante e igual al que ocupa un int, k por ejemplo, la Complejidad Espacial Asint´otica de una llamada a factorial ser´a k; por tanto, si n = 0 en la llamada para el caso base y n = N en la llamada principal o m´as alta, la Complejidad Espacial Asint´otica del m´etodo factorial vendr´a dada el sumatorio n=0...N k = k∗(N+1) ∈ Θ(N) o, equivalentemente, ser´a estrictamente del orden de N. N´otese que en una estimaci´on experimental o a-posteriori del coste Espacial del m´etodo factorial N ser´a el valor concreto con el que se realiza su llamada principal, k ser´a el tama˜ no exacto del Registro de Activaci´on que representa cada una de sus llamadas y, por tanto, la multiplicaci´on de ambos valores ser´a su coste Espacial efectivo.
En cuanto a la Complejidad Temporal de un m´etodo recursivo, para establecerla de forma general se utilizar´a el siguiente esquema: public static TipoResultado metodoRecursivo( TipoDatos x ){ TipoResultado resMetodo, resLlamada1, resLlamada2,..., resLlamadaK; if ( casoBase(x) ) resMetodo = solucionBase( x ); else{ resLlamada1 = metodoRecursivo( anterior1( x ) ); ...
resLlamadaK = metodoRecursivo( anteriorK( x ) ); resMetodo = combinar( x, resLlamada1, ..., resLlamadaK ); } return resMetodo; } M.Galiano,N.Prieto 29 1.
N´otese que tal como ha sido definido su cuerpo, la Complejidad Temporal de cualquier llamada a metodoRecursivo s´olo puede ser: bien la de la llamada que origina su caso base, cuando x = xbase ´o casoBase(x), igual a la Complejidad Temporal de solucionBase(x) o n´ umero de pasos de programa que requiere obtener resMetodo if ( casoBase(x) ); utilizando la notaci´on habitual se tendr´ıa que TmetodoRecursivo (xbase ) = TsolucionBase (xbase ); bien la de la llamada que origina su caso general, cuando x > xbase ´o !casoBase(x), que depende de los siguientes factores: el n´ umero de llamadas recursivas a = K ≥ 1 que se realizan para obtener el resultado del m´etodo para una talla x, la talla del problema en cada una de ellas, que si y s´olo si se supone igual para todas se puede denotar como anterior(x) tal que anterior(x) < x, y, finalmente, la denominada sobrecarga o coste de todas las operaciones que, salvo las a = K llamadas, se han de realizar para que metodoRecursivo obtenga resMetodo para la talla x. En lo que sigue, TrestoOps (x) denotar´a la sobrecarga, es decir la suma de los costes de evaluar si !casoBase(x), calcular anterior(x) y combinar el resultado de cada una de las K llamadas realizadas con x para obtener y devolver resMetodo. Espec´ıficamente, la Complejidad de una llamada de talla x > xbase , se puede expresar en base a los factores enunciados como sigue: TmetodoRecursivo (x > xbase ) = a ∗ TmetodoRecursivo (anterior(x)) + TrestoOps (x) Las dos ecuaciones que se acaban de presentar se denominan Relaciones o Ecuaciones de Recurrencia de metodoRecursivo y expresan la Complejidad Temporal de cualquiera de sus llamadas para una talla e instancia dadas. Instanciando metodoRecursivo a un m´etodo concreto se pueden obtener las Ecuaciones de Recurrencia que expresan su Complejidad Temporal; as´ı por ejemplo, para factorial se tendr´ıa que Tfactorial (x=0) = k’; Tfactorial (x>0) = 1 ∗ Tfactorial (x−1) + k donde, la constante k’ ≥ 1 representa el n´ umero de pasos de programa que se realizan para que factorial devuelva 1 cuando x = 0; la constante a = 1 es el n´ umero de llamadas en secuencia que efect´ ua factorial en su caso general, pues presenta un tipo de Recursi´on Lineal; anterior(x) = x−1 < x, pues la talla del problema decrece aritm´eticamente en cada llamada o rest´andole 1 a n; TrestoOps (x) = k ≥ 1 es la sobrecarga constante que resulta de multiplicar por n el resultado de la llamada factorial(n-1) y devolverlo como resultado cuando n > 0.
Para resolver las Relaciones planteadas, o las de cualquier otro m´etodo recursivo que instancie a metodoRecursivo, se pueden aplicar los m´etodos de resoluci´on de recurrencias estudiados en la asignatura An´ alisis Matem´ atico de primer curso, cuando se mostr´o el comportamiento de las sucesiones y se aplicaron sus propiedades a la determinaci´on de ´ordenes de magnitud y a la resoluci´on de recurrencias; acotando su soluci´on se obtendr´a el coste Temporal Asint´otico del m´etodo en cuesti´on para una instancia y talla dadas.
30 2. El coste como criterio de dise˜ no: teoremas de coste y su aplicaci´on al desarrollo de estrategias recursivas eficientes 2.
El coste como criterio de dise˜ no: teoremas de coste y su aplicaci´ on al desarrollo de estrategias recursivas eficientes Hasta ahora el coste de un m´etodo se ha utilizado como criterio de comparaci´on a-posteriori, esto es como un indicador de la bondad de un m´etodo ya dise˜ nado frente a otros que resuelven el mismo problema. Sin embargo es mucho m´as ventajoso utilizarlo para comparar las distintas estrategias de dise˜ no que se pueden emplear para resolver un mismo problema, o como criterio de comparaci´on a-priori, pues con ello se evita el bald´ıo esfuerzo de transcribir y validar una estrategia ineficaz y, m´as importante a´ un, se pueden establecer las caracter´ısticas que debe poseer la m´as eficiente o mejor de todas las estrategias que resuelven un problema dado.
Obviamente, no es posible comparar costes de estrategias recursivas sin incorporar el an´alisis y c´alculo del coste al proceso de dise˜ no o, equivalentemente, hacer del coste o la eficiencia un criterio de dise˜ no. Para lograrlo basta recordar que tras la etapa de An´alisis de Casos de un cierto metodoRecursivo ya se ha establecido una estrategia a partir de, exactamente, los mismos factores que definen las Ecuaciones de Recurrencia que expresan su Complejidad: la talla x e instancias significativas del problema a resolver; el n´ umero a de llamadas en secuencia que se realizan en el caso general, a = 1 si la estrategia recursiva es Lineal o a > 1 si es M´ ultiple; el tipo de reducci´on de la talla en cada llamada, aritm´etica cuando a x se le resta una cierta cantidad constante c ≥ 1 (i.e. anterior(x) = x - c) o geom´etrica si x se divide por c ≥ 2 (i.e. anterior(x) = cx ); la sobrecarga en cada llamada, TrestoOps (x), que puede ser una constante b ≥ 1 independiente de la talla o una funci´on lineal de la talla b ∗ x + d con b ≥ 1 y d ≥ 1.
As´ı, para decidir si vale la pena continuar desarrollando la estrategia recursiva planteada para un cierto metodoRecursivo o es mejor plantear otra alternativa m´as eficiente simplemente hay que plantear, resolver y acotar la soluci´on de las Relaciones de Recurrencia que expresan su Complejidad. Ahora bien, ¿c´omo determinar si es posible aplicar una estrategia alternativa y, en su caso, si dicha estrategia es la ´optima? La respuesta se puede obtener analizando y confrontando los cuatro teoremas de coste que se presentan a continuaci´on, que adem´as permiten obtener el coste Temporal Asint´otico de una estrategia recursiva sin necesidad de resolver y acotar la soluci´on de sus Ecuaciones de Recurrencia asociadas: Teorema 1: sea TmetodoRecursivo (x) = a ∗ TmetodoRecursivo (x-c) + b, entonces x si a = 1 TmetodoRecursivo (x) ∈ Θ(x) y si a > 1 TmetodoRecursivo (x) ∈ Θ(a c ) Teorema 2: sea TmetodoRecursivo (x) = a ∗ TmetodoRecursivo (x-c) + b ∗ x + d, entonces x si a = 1 TmetodoRecursivo (x) ∈ Θ(x2 ) y si a > 1 TmetodoRecursivo (x) ∈ Θ(a c ) Teorema 3: sea TmetodoRecursivo (x) = a ∗ TmetodoRecursivo ( xc ) + b, entonces si a = 1 TmetodoRecursivo (x) ∈ Θ(logc x) y si a > 1 TmetodoRecursivo (x) ∈ Θ(xlogc a ) Teorema 4: sea TmetodoRecursivo (x) = a ∗ TmetodoRecursivo ( xc ) + b ∗ x + d, entonces si a < c, TmetodoRecursivo (x) ∈ Θ(x) , si a = c, TmetodoRecursivo (x) ∈ Θ(x ∗ logc x) y si a > c, TmetodoRecursivo (x) ∈ Θ(xlogc a ) M.Galiano,N.Prieto 31 2.
N´otese ahora que s´olo se pueden aplicar los Teoremas 1 y 3 a Ecuaciones de Recurrencia cuya sobrecarga sea una constante b independiente de la talla y los Teoremas 2 y 4 a las que tengan una sobrecarga lineal con la talla; asimismo, s´olo se pueden aplicar los Teoremas 1 y 2 a Ecuaciones de Recurrencia cuya reducci´on de la talla sea aritm´etica y los Teoremas 3 y 4 a las que la tengan geom´etrica. Por ejemplo, el orden de la Ecuaci´on de Recurrencia asociada con el caso general del m´etodo factorial, Tfactorial (x>0) = 1 ∗ Tfactorial (x-1) + k, ser´ıa Tfactorial (x>0) ∈ Θ(x) por el Teorema 1 con a = c = 1 y sobrecarga b = k ≥ 1 constante.
Ejercicio propuesto: obt´enganse las Ecuaciones de Recurrencia que expresan la Complejidad Temporal de los m´etodos dise˜ nados en RecursionNumerica y RecursionArray y resu´elvanse utilizando alguno de los teoremas anteriores.
Una vez presentados, en las siguientes secciones de este apartado se analizan y confrontan los teoremas de coste para obtener dos estrategias recursivas que permiten resolver de forma ´optima conocidos e importantes tipos de problemas: Reducci´ on Logar´ıtmica para Recursi´on Lineal y Divide y Vencer´ as para Recursi´on M´ ultiple.
2.1.
Reducci´ on Aritm´ etica VS Geom´ etrica de la talla para la Recursi´ on Lineal: la estrategia de Reducci´ on Logar´ıtmica y algunos ejemplos de su aplicaci´ on De la confrontaci´on de los Teoremas 1 y 3 se deduce que la estrategia de dise˜ no ´optima de un m´etodo recursivo Lineal con sobrecarga constante es aquella en la que se hace decrecer la talla del problema geom´etricamente, pues se obtiene una cota logar´ıtmica en lugar de la lineal que proporcionar´ıa una disminuci´on aritm´etica; de ah´ı el nombre de Reducci´on Logar´ıtmica que recibe esta estrategia, que en lo que sigue se utilizar´a para dise˜ nar los m´etodos recursivos m´as eficientes que resuelven una serie de conocidos problemas num´ericos y de B´ usqueda.
B´ usqueda de un Dato b en un array v ordenado Ascendentemente Tras una breve reflexi´on sobre el problema enunciado, la estrategia recursiva que de forma m´as inmediata se puede proponer es la de B´ usqueda Ascendente de la posici´on de la primera componente de v que sea mayor o igual que b; n´otese que esta doble condici´on de B´ usqueda es factible pues v est´a ordenado ascendentemente, lo que para determinadas instancias del problema permite establecer que b no est´a en v, o equivalentemente entregar como resultado de la B´ usqueda el valor -1 antes de alcanzar el caso base de la Recursi´on.
Como es f´acil deducir, el tipo de Recursi´on que establece esta estrategia es Lineal Final: si se busca a b en v[inicio ... v.length-1], de talla x = v.length-inicio > 0, y v[inicio] es menor que b la B´ usqueda deber´a proseguir en el subarray v[inicio+1 ... v.length-1], cuya talla es menor que la del anterior en una unidad, hasta que bien se alcanza el caso base o bien se encuentra la componente buscada. Por tanto, si se busca b en v[0 ... v.length-1] y, adem´as, b es mayor estricto que todas las componentes de v, el coste de la B´ usqueda en el Peor de los Casos Tbuscar P (x) vendr´a dado por el Teorema 1 con a = 1 = c = 1 y ser´a Θ(v.length), por lo que para cualquier otra instancia Tbuscar (v.length) ∈ O(v.length).
32 2.
Ahora bien, el criterio de eficiencia y las condiciones del problema indican que una Reducci´on Logar´ıtmica puede mejorar la estrategia definida; como la opci´on m´as natural y eficiente para que la talla decrezca en cada llamada geom´etricamente es dividirla por c = 2, la estrategia a seguir ser´a la siguiente: sea el subarray de B´ usqueda v[inicio...fin] de (inicio+fin) la que establece una talla x = fin-inicio+1 y sea su posici´on central mitad = 2 descomposici´on recursiva del subarray de B´ usqueda en dos subarray v[inicio...mitad] y v[mitad...fin] de la misma talla, exactamente x2 . A partir de esta descomposici´on recursiva, la B´ usqueda de b en v[inicio...fin] se resolver´a en base al resultado de la comparaci´on entre v[mitad] y b como sigue: si v[mitad].compareTo(b) == 0 termina la B´ usqueda y su resultado es mitad, la posici´on de la primera aparici´on de b en el subarray de B´ usqueda; si v[mitad]).compareTo(b) > 0, como v[inicio...fin] est´a ordenado ascendentemente, la B´ usqueda de b se debe realizar tan s´olo en el subarray v[inicio...mitad-1]; si v[mitad].compareTo(b) < 0 la B´ usqueda de b se debe realizar tan s´olo en el subarray v[mitad+1...fin]; N´otese que los casos expuestos s´olo son admisibles cuando la talla del subarray de B´ usqueda es mayor que cero; obviamente, en un array vac´ıo no se puede encontrar b por lo que el resultado de la B´ usqueda ser´a, sin m´as, -1. De hecho, este es el caso base de la Recursi´on, al que se llegar´a siempre que b no se encuentre en el subarray de B´ usqueda; si es mayor que todas sus componentes no se encontrar´a al buscarlo en v[mitad+1...fin] y si es menor fallar´a la B´ usqueda en v[inicio...mitad-1].
Intuitivamente, el coste de la estrategia de Reducci´on Logar´ıtmica que se acaba de presentar es mejor que el de la B´ usqueda Ascendente porque uno de los dos subproblemas en los que se divide el problema original ... ¡no es tal! Formalmente, aplicando el Teorema 3 con a=1 y c=2 se tiene que TbuscarBin P (x>0)∈Θ(log2 x), de donde para cualquier otra instancia TbuscarBin (x>0) ∈ O(log2 x). Por tanto, siguiendo las etapas del dise˜ no recursivo, cabe refinar esta estrategia hasta convertirla en un m´etodo Java como el siguiente: public static <T extends Comparable<T>> int buscarBin(T v[], T b){ return buscarBin(v, b, 0, v.length-1); } /** ∀ i: inicio≤i<fin: v[i]≤v[i+1] AND 0≤inicio≤v.length AND -1≤fin<v.length **/ private static <T extends Comparable<T>> int buscarBin(T v[], T b, int inicio, int fin){ int resMetodo = -1; if ( inicio <= fin ){ int mitad = (inicio + fin)/2; int comparacion = v[mitad].compareTo(b); if ( comparacion < 0 ) resMetodo = buscarBin(v, b, mitad+1, fin); else if ( comparacion > 0 ) resMetodo = buscarBin(v, b, inicio, mitad-1); else resMetodo = mitad; } return resMetodo; } // buscarBin(v,b,inicio,fin) == -1 AND ∀i: inicio≤i≤fin: v[i] != b OR // buscarBin(v,b,inicio,fin) == i: inicio≤i≤fin: v[i] = b M.Galiano,N.Prieto 33 2.
Ejercicios propuestos: 1. Compru´ebese la terminaci´on y coherencia de las llamadas del m´etodo buscarBin.
2. Anal´ıcese para una talla dada qu´e tipo de presentaciones de las componentes del subarray v[inicio...fin] de buscarBin originan su Peor y Mejor de los Casos. Establ´ezcanse entonces las Ecuaciones de Recurrencia para el Peor de los Casos y determ´ınese el coste Asint´otico a-priori de buscarBin en sus casos Mejor y Peor. En base al resultado obtenido, ¿qu´e se puede decir del comportamiento general de buscarBin? 3. Los m´etodos recursivos buscar y buscarBin se invocan en distintas ocasiones desde el main del programa TestBuscarArrayOrd que los contiene. A˜ n´adanse a dichos m´etodos las l´ıneas de c´odigo necesarias para poder trazar su ejecuci´on, i.e. para mostrar por pantalla la talla del problema que resuelven en cada llamada que origine su ejecuci´on, los datos de tal llamada y sus resultados. Hecho esto, ejecutar el main de TestBuscarArrayOrd y contestar a las siguientes preguntas: en el Peor de los Casos de cada uno de estos m´etodos, ¿que tipo de Recursi´on presenta? ¿cu´anto y c´omo disminuye la talla en cada una de sus llamadas? ¿cu´antas llamadas genera su invocaci´on m´as alta?.
**TestBuscarArrayOrd figura en la tabla de material did´ actico de los Contenidos PoliformaT del tema.
Multiplicaci´ on de dos n´ umeros a y b Naturales La soluci´on recursiva m´as sencilla a este problema se basa en una conocida igualdad matem´atica: si a> 0 entonces a∗b = ((a−1) ∗ b) + b; sino a ∗ b = 0. La transcripci´on de este resultado a Java es directa: /** a >= 0 AND b >= 0 **/ static int multiplicar(int a, int b){ if ( a == 0 ) return 0; return multiplicar(a - 1, b) + b; } Como es f´acil deducir, la talla del problema que resuelve multiplicar es x = a y su coste es siempre lineal con dicha talla; aplicando el Teorema 1 con a = 1 = c = 1 se obtiene el mismo resultado, i.e. Tmultiplicar (x) ∈ Θ(x).
Una primera mejora del coste del m´etodo propuesto, n´otese, consiste en que el par´ametro que representa la talla sea siempre el menor de a y b: static int multiplicarMinimo(int a, int b){ if ( a < b ) return multiplicar(a, b); return multiplicar(b, a); } Pero esta mejora no supone una modificaci´on de la estrategia recursiva que expresa multiplicar; para lograrla, visto que su tipo de Recursi´on es Lineal, que la talla del problema decrece una unidad en cada llamada y que la sobrecarga es constante, se puede intentar su Reducci´on Logar´ıtmica. Para ello, basta recordar la correspondiente igualdad matem´atica para a>0: si a es par, a∗b = ( a2 ∗b)∗2; sino, a∗b = (( a2 ∗b)∗2)+b Transcribi´endola a Java, se obtendr´ıa el siguiente m´etodo: 34 2.
/** 0 <= a <= b **/ static int multiplicarRL(int a, int b){ if ( a == 0) return 0; int resLlamada = multiplicarRL(a/2, b); if ( a%2 == 0 ) return resLlamada * 2; return resLlamada * 2 + b; } Las Ecuaciones de Recurrencia que expresan el coste de multiplicarRL son entonces, para una talla dada x = a y cualquier instancia, las siguientes: TmultiplicarRL (x = 0) = k’; TmultiplicarRL (x > 0) = 1 ∗ TmultiplicarRL ( 2x ) + k Aplicando el Teorema 3 con a=1 y c=2 a la segunda ecuaci´on, TmultiplicarRL (x>0) ∈ Θ(log2 x); como era de esperar, la Reducci´on Logar´ıtmica efectuada mejora el coste Asint´otico, que pasa a ser logar´ıtmico con la talla en lugar de lineal.
Cuesti´ on: disc´ utase si multiplicarRL tiene un coste Espacial menor que el de multiplicar.
El problema de la Exponenciaci´ on Dados dos Naturales a e b, el problema de calcular ab tiene talla x = b y puede resolverse aplicando cualquiera de las estrategias recursivas que definen las siguientes igualdades matem´aticas: 1. si b > 0 entonces ab = (ab−1 ∗ a); sino ab = 1.
b b b b 2. si b > 0 es par, ab = a 2 ∗ a 2 ; sino, si b > 0 es impar, ab = a 2 ∗ a 2 ∗ a Es evidente que la transcripci´on Java de la primera desigualdad origina un m´etodo sencillo cuyo coste espacial y temporal es lineal con la talla x = b; en cuanto a la segunda, donde la talla del problema se divide siempre por dos, en base al criterio de Reducci´on Logar´ıtmica su transcripci´on a m´etodo Java deber´ıa ser m´as eficiente, con un coste espacial y temporal logar´ıtmico con b. Ahora bien, la siguiente transcripci´on directa a Java no lo es: /** a > 0 AND b >= 0 */ static int potencia(int a, int b){ int resMetodo = 1; if ( b > 0 ){ int resLlamada1 = potencia(a, b/2); int resLlamada2 = potencia(a, b/2); resMetodo = resLlamada1 * resLlamada2; if ( b % 2 != 0) resMetodo = resMetodo * a; } return resMetodo; } // potencia(a, b) == ab Obs´ervese que el tipo de Recursi´on que exhibe este m´etodo es M´ ultiple, y no Lineal como la del m´as sencillo. Lo peor es que ello se debe a que en su caso general se realiza dos veces la misma llamada potencia(a, b/2), lo que supone una innecesaria repetici´on de c´alculos y el consiguiente consumo extra de espacio para almacenarlos. As´ı, aunque la talla decrece geom´etricamente y la sobrecarga es constante, el coste de potencia es lineal con la talla; en efecto, si las Ecuaciones de Recurrencia que expresan la Complejidad de potencia para una instancia son M.Galiano,N.Prieto 35 2.
Tpotencia (x=0) = k’; Tpotencia (x>0) = 2 ∗ Tpotencia ( x2 ) + k y se aplica el Teorema 3 con a=c=2 a la segunda de ellas se tiene que Tpotencia (x) ∈ Θ(x), que coincide con la del m´etodo m´as sencillo.
Cuesti´ on: suponiendo que se realiza la invocaci´on potencia(a, 8) y utilizando tan s´olo el ´ Arbol de Llamadas que ´esta genera, raz´onese por qu´e el m´etodo recursivo M´ ultiple y el Lineal consumen la misma cantidad de tiempo y espacio.
La pregunta l´ogica que se plantea al obtener la igualdad de costes presentada es por qu´e o d´onde ha fallado la estrategia de Reducci´on Logar´ıtmica aplicada. De la discusi´on realizada sobre la estructura recursiva de potencia es f´acil deducir que para realizar una Reducci´on Logar´ıtmica, adem´as de que la talla decrezca geom´etricamente y que la sobrecarga sea constante, es imprescindible que el tipo de Recursi´on sea tambi´en Lineal. En el ejemplo de potencia esto se logra, simplemente, realizando una cuidadosa transcripci´on de la estrategia a Java: static int potenciaRL(int a, int b){ int resMetodo = 1; if ( b > 0 ){ int resLlamada = potenciaRL(a, b/2); resMetodo = resLlamada * resLlamada; if ( b % 2 != 0) resMetodo = resMetodo * a; } return resMetodo; } Esto es, se realiza una u ´ nica llamada potenciaRL(a, b/2) y se multiplica por s´ı mismo su resultado resLlamada. Tan sencilla soluci´on evita la repetici´on innecesaria de c´alculos que se realizaba en potencia, lo que conlleva una mejora sustancial del coste. Si se compara entonces potenciaRL con el m´etodo sencillo, la u ´ nica diferencia que existe entre ellos es que la talla decrece m´as r´apidamente en potenciaRL; por tanto, para el mismo n´ umero de llamadas, una, y la misma sobrecarga, constante, potenciaRL es m´as r´apido; formalmente, basta con aplicar el Teorema 3 con a = 1 y c = 2 para resolver la Relaci´on de Recurrencia del caso general TpotenciaRL (x>0) = 1 ∗ TpotenciaRL ( x2 ) + k, de donde TpotenciaRL (x>0) ∈ Θ(log2 x), que tambi´en es su coste Espacial.
Ejercicios propuestos: 1. Dado un array v de componentes Integer, ordenado de forma creciente y sin elementos repetidos, se quiere determinar si existe alguna componente de v que represente el mismo valor que el de su posici´on en v; en el caso que no haya ninguna posici´on para la que se cumpla dicha condici´on el resultado ser´a -1. Se pide: dise˜ nar un m´etodo recursivo de coste m´ınimo que resuelva este problema y analizar su coste Temporal; si el array v tiene elementos repetidos, ¿cu´al es el coste del m´etodo m´as eficiente que resuelve el mismo problema? ¿Por qu´e? ¿Y si v no est´a ordenado? 2. Sea v un array de Integer positivos que se ajustan al perfil de una curva c´oncava, i.e.
existe una u ´ nica posici´on k de v, 0≤k<v.length, tal que ∀j: 0≤ j<k: v[j]>v[j+1] 36 2.
AND ∀j: k<j<v.length: v[j-1]<v[j]. Se pide dise˜ nar el m´etodo recursivo que m´as eficientemente calcule dicha posici´on k y analizar su coste.
3. Sea m una Matriz cuadrada de n x n componentes Comparable, tal que para cada una de sus filas se cumplen las dos condiciones siguientes: sus componentes est´an ordenadas de forma estrictamente creciente y todas ellas son menores que las de la fila siguiente.
Aprovechando estas propiedades, se pide dise˜ nar un m´etodo recursivo de m´ınimo coste que dada una componente x de m devuelva la posici´on de la Matriz (i.e. fila y columna) donde se encuentra. Anal´ıcese tambi´en su coste y disc´ utase si ser´ıa el mismo que se obtendr´ıa si las componentes de m no cumplieran las propiedades expuestas.
2.2.
Recursi´ on M´ ultiple VS Recursi´ on Lineal: la estrategia Divide y Vencer´ as (DyV) y su aplicaci´ on al problema de la Ordenaci´ on La prevenci´on asociada al uso de la Recursi´on M´ ultiple resulta m´as que natural. Por una parte, intuitivamente, la experiencia adquirida a trav´es de ejemplos como fibonacci o potencia ha permitido comprobar que si el tipo de Recursi´on que presenta un m´etodo es M´ ultiple, i.e. se producen a > 1 llamadas recursivas en su caso general, entonces se debe exigir que los subproblemas que representan dichas llamadas sean, como m´ınimo, disjuntos o m´as exactamente, esencialmente sin superposiciones que obliguen a una costosa y superflua repetici´on de c´alculos y definici´on de memoria para recordarlos. Por otra parte, ya m´as formalmente, si se comparan los resultados que da uno cualquiera de los cuatro teoremas de coste enunciados para a=1 y a>1 se advierte que siempre que a>1, Recursi´on M´ ultiple, el coste es mayor que cuando a=1, Recursi´on Lineal. Sin embargo esta afirmaci´on no se mantiene si se combinan adecuadamente los factores talla y sobrecarga, como demuestra el siguiente ejemplo: la comparaci´on de los resultados de los Teoremas 1 y 3 para una sobrecarga constante indica que si la Recursi´on es M´ ultiple, la talla decrece geom´etricamente y (c = a)≥ 2 se obtiene una cota igual a la que presenta el mismo problema con una reducci´on aritm´etica de la talla y a = 1; obviamente la Recursi´on Lineal es siempre m´as sencilla de implementar que la M´ ultiple, pero lo que se pretende destacar con el ejemplo es que una correcta combinaci´on de los factores talla y sobrecarga puede romper el a-priori establecido peligro de la Recursi´on M´ ultiple e incluso llegar a darle la vuelta. A saber, para una sobrecarga lineal con la talla, los resultados del Teorema 2 con a=1 pueden ser peores que los del Teorema 4 con a≥c; por ejemplo como se demostrar´a a continuaci´on, el conocido problema de la Ordenaci´on gen´erica de las componentes de un array puede ser resuelto m´as eficientemente con Recursi´on M´ ultiple que con Lineal siempre que la talla decrezca geom´etricamente y la sobrecarga sea lineal con la talla.
Cuesti´ on: en funci´on de la discusi´on realizada, raz´onese cu´al de los siguientes m´etodos resuelve con mayor eficiencia el problema de sumar las componentes de un array: static int sumarV1(Integer v[], int inicio){ if ( i > v.length ) return 0; return sumarV1(v, inicio+1, m) + v[inicio].intValue(); } static int sumarV2(Integer v[], int inicio, int fin){ if ( inicio == fin ) return v[inicio].intValue(); int mitad = (inicio + fin) / 2; return sumarV2(v, inicio, mitad) + sumarV2(v, mitad+1, fin); } M.Galiano,N.Prieto 37 2.
A partir de los resultados sobre Recursi´on M´ ultiple que se acaban de presentar se puede establecer una estrategia recursiva y eficiente para la resoluci´on de problemas; tal estrategia se denomina Divide y Vencer´ as (DyV) y consta de los siguientes pasos: 1. DIVIDIR el problema original de talla x en a > 1 subproblemas disjuntos y cuya talla divida la del original de la forma m´as equilibrada posible, i.e. la talla de cada uno de ellos xc ≤ xa . Por ejemplo, si se divide un array v en dos a partir de su posici´on central, se obtienen dos subarray de talla la mitad de la de v; 2. VENCER o resolver los subproblemas definidos de forma recursiva excepto, por supuesto, los que originan el caso base, que se resolver´an de forma trivial o directa; 3. COMBINAR las soluciones de los subproblemas adecuadamente para obtener la soluci´on del problema original.
Un m´etodo que refleja esta estrategia podr´ıa ser el siguiente: public static TipoResultado vencer( TipoDatos x ){ TipoResultado resMetodo, resLlamada1, resLlamada2,..., resLlamadaK; if ( casoBase(x) ) resMetodo = solucionBase(x); else{ int c = dividir(x); resLlamada1 = vencer(x/c); ...
resLlamadaK = vencer(x/c); resMetodo = combinar(x, resLlamada1, ..., resLlamadaK); } return resMetodo; } donde la Relaci´on de Recurrencia que expresa la Complejidad de su caso general ser´ıa: Tvencer (x>xbase ) = a ∗ Tvencer ( cx ) + Tdividir (x) + Tcombinar (x) Como es f´acil deducir, la resoluci´on exacta de esta ecuaci´on depende de los par´ametros a, c y de la sobrecarga Tdividir (x) + Tcombinar (x). Por tanto, suponiendo que en cualquier caso Tdividir (x) + Tcombinar (x) ∈ O(xg ), i.e. que la sobrecarga es como mucho del orden de un polinomio de grado g≥0, y que para ser realistas nada bueno se puede obtener si g≥3, se pueden extraer las siguientes conclusiones sobre el coste de un m´etodo DyV: 1. Si la sobrecarga es constante, i.e. para g=0, Tvencer (x>xbase ) viene dado por el Teorema 3: en funci´on del n´ umero de llamadas a que se realicen y de lo equilibrada que sea la divisi´on de la talla original en cada una de ellas, c, Tvencer (x>xbase ) variar´a entre Θ(logc x) para a=1 y Θ(xlogc a ) para a>1.
2. Si la sobrecarga es lineal con la talla del problema x, i.e. g=1, el Teorema 4 permite obtener Tvencer (x > xbase ): la elecci´on de los valores de a y c determina un coste que var´ıa entre Θ(x) para a<c y Θ(xlogc a ) para a>c, pasando por Θ(x ∗ logc x) si a=c.
A grosso modo, lo que indican estos dos resultados es que al usar la estrategia DyV con una sobrecarga constante o lineal, un n´ umero de llamadas excesivo puede contrarrestar el efecto beneficioso de una distribuci´on equilibrada de la talla del problema.
3. Para sobrecargas mayores que la lineal, mencionar tan s´olo que se puede demostrar (v´ease la secci´on 7.5.3 del libro de Weiss, p´ags.195-196) que si a > cg , Tvencer (x) ∈ O(xlogc a ); si a = cg , Tvencer (x) ∈ O(xg ∗ log x); si a < cg , Tvencer (x) ∈ O(xg ) 38 2.
Ejercicio propuesto: estudiar la resoluci´on del problema de la subSecuencia de Suma M´axima que se plantea en las secciones 7.5.1 y 7.5.2 del libro de Weiss, p´ags.188-194.
Validaci´ on de un dise˜ no DyV Hasta el momento, para validar un m´etodo recursivo se ha demostrado su terminaci´on y la coherencia de sus llamadas y se ha obviado la demostraci´on de su correcci´on o prueba formal de que el m´etodo obtiene la soluci´on correcta del problema que resuelve para cualquier valor de su talla; ahora bien, para m´etodos DyV esta prueba resulta sencilla y clarificadora, por lo que se incluir´a como parte de la validaci´on: si se demuestra por Inducci´on sobre la talla del problema que el m´etodo DyV dise˜ nado es correcto se comprueba que la secuenciaci´on de los m´etodos que implementan los pasos DIVIDIR VENCER y COMBINAR tambi´en lo es; por ejemplo, para demostrar por Inducci´on sobre la talla del problema que el m´etodo vencer es correcto se deber´a comprobar que: Base de la Inducci´ on: si casoBase(x), vencer es correcto si lo es solucionBase(x); Prueba de Inducci´ on: si !casoBase(x), suponiendo por Hip´ otesis de Inducci´ on que los resultados de las (al menos dos) llamadas recursivas a vencer(x/c) son correctas, vencer(x) es correcto, suponiendo que dividir y combinar tambi´en lo son.
Mejora adicional del coste de ejecuci´ on de los m´ etodos DyV En diferentes puntos de este tema se ha subrayado que s´olo hay que resolver recursivamente aquellos problemas lo suficientemente complejos como para merecerlo; cuando existen dos soluciones a un mismo problema, por ejemplo el de la Ordenaci´on, una iterativa sencilla pero poco eficiente, como la de Inserci´on o Selecci´on Directa, y otra recursiva DyV m´as eficiente pero tambi´en m´as sofisticada, para tallas suficientemente grandes del problema no cabe duda de cual hay que utilizar. Sin embargo, cuando la ejecuci´on el m´etodo DyV alcanza tallas suficientemente peque˜ nas, digamos que menores que una cierta talla umbral, el consumo Espacial y Temporal extra que supone la ejecuci´on de un m´etodo recursivo invalida la comparaci´on establecida; por ejemplo, se puede determinar experimentalmente que para tallas del problema menores que 10, aunque cualquier valor entre 5 y 20 produce resultados similares, el m´etodo iterativo insercionDirecta es m´as eficiente que el m´etodo recursivo DyV quickSort. Es por ello que, siempre que sea posible, tras calcular experimentalmente su talla umbral, el coste de ejecuci´on de un m´etodo DyV se puede mejorar transformando su caso base como sigue: public static TipoResultado vencer( TipoDatos x ){ TipoResultado resMetodo, resLlamada1,..., resLlamadaK; if ( x < X_UMBRAL ) resMetodo = solucionIterativa(x); else{ int c = dividir(x); resLlamada1 = vencer(x/c); ... resLlamadaK = vencer(x/c); resMetodo = combinar(x, resLlamada1, ..., resLlamadaK); } return resMetodo; } Cuesti´ on: si se escoge como estrategia de Ordenaci´on Divide y Vencer´as, raz´onese por qu´e es mejor usar insercionDirecta que seleccionDirecta como solucionIterativa(x).
M.Galiano,N.Prieto 39 2.
Soluciones DyV al problema de la Ordenaci´ on gen´ erica de un array A modo de ejemplo, se plantea ahora la forma de utilizar la estrategia DyV para resolver eficientemente el problema de la Ordenaci´on gen´erica de un array; ello servir´a para describir m´as adelante dos m´etodos concretos que instancian dicho planteamiento, mergeSort y quickSort.
Como ya se sabe, la estrategia general para ordenar un array v es un Recorrido en el que la visita a cada componente v[i] del array, 0≤i<v.length, consiste en ordenarla con respecto a las restantes; por tanto, 1. antes de visitar v[i] todas las componentes del subarray v[0 ... i-1] est´an ordenadas y s´olo restan por ordenar las componentes del subarray v[i ... v.length-1]; 2. tras visitar v[i] se ha avanzado un paso hacia la terminaci´on de la Ordenaci´on de v, o se ha decrementado en uno la talla del problema; en concreto, v quedar´a ordenado cuando concluya la visita a v[v.length-1], pues s´olo restar´an por ordenar las cero componentes de un subarray vac´ıo que, obviamente, ya est´an ordenadas.
A partir de lo dicho, para completar la estrategia de Ordenaci´on s´olo resta determinar c´omo ordenar la componente v[i] del subarray v[i ... v.length-1], 0≤i≤v.length. Para ello, como se estudi´o en PRG, se pueden aplicar tres principios: el de Inserci´on, el de Selecci´on y el de Intercambio; el primero de ellos, recu´erdese, fue el que se us´o en el Tema 3 para dise˜ nar el siguiente m´etodo iterativo de Ordenaci´on Ascendente: public static <T extends Comparable<T>> void insercionDirecta(T v[]){ for( int i = 1; i < v.length; i++ ){ T aIns = v[i]; int posIns = i; // B´ usqueda del lugar de inserci´ on ordenada; desplazar mientras NO se encuentre for (; posIns>0 && aIns.compareTo(v[posIns-1])<0 ; posIns--) v[posIns]=v[posIns-1]; // Inserci´ on en posIns v[posIns] = aIns; } } El c´odigo de este m´etodo refleja c´omo ordenar v[i] por Inserci´on: se determina primero mediante una B´ usqueda Descendente la posici´on posIns que debe ocupar v[i] en el subarray ya ordenado v[0 ... i-1], esto es la posici´on de inserci´on ordenada de v[i] en v, y luego se inserta v[i] en tal posici´on; durante la B´ usqueda, precisamente para que cuando concluya v[i] se pueda insertar directamente en posIns, las componentes de v[0 ... i-1] mayores o iguales que v[i] se desplazan una posici´on a la derecha. N´otese entonces que la primera componente de v que se ordena es v[1], pues v[0] ya est´a ordenada con respecto a las cero componentes del subarray vac´ıo que hay a su izquierda; insercionDirecta es un m´etodo natural de Ordenaci´on, pues cuanto m´as ordenado est´a inicialmente v menor es su coste y viceversa: en el Peor de los Casos, cuando inicialmente v est´a ordenado descendentemente, posIns = 0 para cualquier componente de v y, por tanto, la B´ usqueda de la posici´on de inserci´on ordenada de v[i] tiene un coste lineal con la talla i del subarray v[0...i-1]; en el Mejor de los casos, cuando inicialmente v ya est´a ordenado ascendentemente, posIns = i para cualquier componente de v y, por tanto, la B´ usqueda de la posici´on de inserci´on ordenada de v[i] tiene un coste independiente de la talla de v[0...i-1].
40 2.
Enunciando recursivamente esta estrategia se tendr´ıa que, para ordenar ascendentemente las componentes de un subarray v[i ... v.length-1], 0≤i≤v.length: si el subarray est´a vac´ıo o tiene una componente, i.e. i == v.length ´ o i == 0, no hay que hacer nada, pues obviamente ya est´a ordenado; si el subarray tiene al menos dos componentes, i.e. 2≤i<v.length, primero se ordena ascendentemente por Inserci´on su i-´esima componente y luego, aplicando los pasos 1 ´o 2, se ordenan sus restantes v.length-i-1 componentes.
Traduciendo a Java esta estrategia se tendr´ıa: /** 1 <= i <= v.length*/ public static <T extends Comparable<T>> void insercionDirectaR(T v[], int i){ if ( i < v.length ){ T aIns = v[i]; int posIns = i ; for (; posIns>0 && aIns.compareTo(v[posIns-1])<0; posIns--) v[posIns]=v[posIns-1]; v[posIns] = aIns; /** Ordenada por Inserci´ on v[i], ordenar las restantes v.length-i-1 */ insercionDirectaR(v, i+1); } } N´otese que este m´etodo difiere de su equivalente iterativo insercionDirecta en dos cosas: el if que eval´ ua el caso de la Recursi´on y la llamada recursiva insercionDirectaR(a, i+1) substituyen al bucle for que se utiliza para recorrer iterativamente v; es necesario realizar la invocaci´on insercionDirectaR(v, 1) desde un m´etodo gu´ıa para ordenar el array v.
Por lo dem´as, como ambos m´etodos usan la misma estrategia para resolver el mismo problema, el coste Temporal de insercionDirecta se puede obtener a partir de las Ecuaciones de Recurrencia asociadas a insercionDirectaR: considerando que la talla del problema es el n´ umero de componentes del subarray v a ordenar, x = v.length-i, TinsercionDirectaR (x≤1) = k’ TinsercionDirectaR (x>1) = 1 ∗ TinsercionDirectaR (x−1) + Tvisitar (x) Obviamente, para poder resolver estas ecuaciones hay que especificar antes Tvisitar (x), el coste de Ordenar por Inserci´on una componente de v con respecto a las x-1 restantes. Como ya se ha se˜ nalado, este coste depende de cu´an ordenadas est´en inicialmente las componentes de v: en el Peor de los Casos, si inicialmente las componentes est´an ordenadas descendentemente, Tvisitar P (x) = k ∗ x; en el Mejor de los Casos, si las componentes ya est´an ordenadas ascendentemente, Tvisitar M (x)=k∗1. Por tanto, TinsercionDirectaR P (x>1) = 1 ∗ TinsercionDirectaR P (x−1) + k ∗ x de donde, aplicando el Teorema 2 con a=c=1, TinsercionDirectaR P (x) ∈ Θ(x2 ).
TinsercionDirectaR M (x>1) = 1∗TinsercionDirectaR M (x−1)+ k.
de donde, aplicando el Teorema 1 con a=c=1, TinsercionDirectaR M (x) ∈ Θ(x).
A partir del coste obtenido para sus instancias significativas ya se puede deducir que en general, para cualquier instancia, la Ordenaci´on por Inserci´on Directa se realizar´a en un tiempo como m´aximo cuadr´atico con la talla, O(x2 ), y como m´ınimo lineal con ella, Ω(x).
Cuesti´ on: usando el criterio de Selecci´on para ordenar la componente v[i], dis´en ˜ ese el m´etodo seleccionDirectaR y, tras analizar su coste, comp´arese con insercionDirectaR.
M.Galiano,N.Prieto 41 2.
Si se desea utilizar una estrategia Divide y Vencer´as para mejorar el coste de la estrategia de Ordenaci´on que subyace en insercionDirectaR, i.e. Recursi´on Lineal con reducci´on aritm´etica de la talla y sobrecarga lineal en el Peor de los Casos, se deben tener en cuenta lo siguiente: No se pueden utilizar los resultados del Teorema 3 sino los del 4 pues, en la mayor´ıa de las ocasiones, ordenar una componente de un array con respecto a las restantes requiere un tiempo lineal con la talla y no constante; la cota lineal del Peor de los Casos del criterio de Inserci´on no se mejora ni utilizando el criterio de Selecci´on, que es lineal para cualquier instancia, ni el de Intercambio, que tiene el mismo comportamiento que el de Inserci´on pero provoca una Ordenaci´on no natural.
La posibilidad de coste lineal que proporciona el Teorema 4 con a<c queda excluida al considerar que requiere una divisi´on geom´etrica y equilibrada de la talla del problema, i.e. como m´ınimo c=2, y que la estrategia recursiva que se quiere mejorar es Lineal, a=1. En conjunto, las dos condiciones expresadas obligan a usar Recursi´on M´ ultiple con a≥c; es m´as, la posibilidad de que a>c tambi´en queda descartada, por ejemplo tres o m´as llamadas recursivas en las que la talla es la mitad de la original, pues su coste est´a acotado por xlogc a , igual o superior al coste de la estrategia que se quiere mejorar.
Por tanto, no queda m´as remedio que caracterizar cualquier posible estrategia DyV que se proponga para la Ordenaci´on como aquella en la que, en promedio, hay que VENCER dos subproblemas de talla aproximadamente la mitad que la original, a = c = 2, y en el que se emplea como m´aximo un tiempo lineal para DIVIDIR la talla original de forma equilibrada y COMBINAR los subproblemas resueltos. Con estas caracter´ısticas, el Teorema 4 garantiza un coste Θ(x ∗ logc x), que para valores suficientemente grandes de la talla mejora bastante la cota cuadr´atica en promedio de cualquier estrategia de Ordenaci´on recursiva Lineal.
2.2.1.
Ordenaci´ on por Fusi´ on o Merge: m´ etodos mergeSort y fusionDyV La Ordenaci´ on por Fusi´ on o Merge que realiza el m´etodo denominado mergeSort es el ejemplo m´as claro y directo de aplicaci´on de la estrategia Divide y Vencer´as al problema de la Ordenaci´on. En efecto, para ordenar los x = der-izq+1 > 1 Datos de un subarray v[izq...der], 0≤izq≤der<v.length, la estrategia de Fusi´on realiza los siguientes pasos: 1. DIVIDIR por 2, c = 2, el n´ umero de componentes a ordenar por Fusi´on; para ello basta calcular la posici´on central de v[izq...der], mitad = (der+izq)/2, lo que permite descomponerlo en dos subarray v[izq...mitad] y v[mitad+1...der], cada uno de los cuales tiene una talla aproximadamente igual a la mitad de la original; 2. VENCER u ordenar por Fusi´on los dos subarray en los que se ha descompuesto el original, tambi´en a = 2, siempre que sus tallas sean estrictamente mayores que uno; si alguno de ellos contiene tan s´olo una componente evidentemente ya est´a ordenada; 3. COMBINAR en tiempo lineal los resultados de los dos subproblemas resueltos en el paso anterior para obtener la Ordenaci´on de las componentes de v[izq ... der]; como las componentes de v[izq...mitad] y v[mitad+1...der] ya han sido ordenadas, se puede realizar su Fusi´ on o Mezcla Natural en tiempo lineal.
La transcripci´on directa a Java de la estrategia presentada ser´ıa la siguiente: 42 2.
private static <T extends Comparable<T>> void mergeSort(T v[], int izq, int der){ if ( izq < der ){ int mitad = (izq+der)/2; mergeSort(v, izq, mitad); mergeSort(v, mitad+1, der); fusionDyV(v, izq, mitad+1, der); } } donde fusionDyV es una modificaci´on del m´etodo fusion que se present´o en el apartado anterior de este tema que permite COMBINAR en un tiempo lineal los resultados de los dos subproblemas en que se ha dividido la Ordenaci´on en mergeSort; espec´ıficamente, los cambios a realizar en fusion son los siguientes: En lugar de dos arrays a y b de tipo int y tallas a.length y b.length respectivamente, se deben fusionar los dos subarray de tipo gen´erico T extends Comparable ya ordenados en los que se ha divido el original v[izq...der], v[izq...mitad] y v[mitad+1...der].
Al variar los Datos del problema cambian el n´ umero de par´ametros formales que los representan en la cabecera del m´etodo; as´ı v es el u ´ nico array que aparece junto con los ´ındices donde empiezan y acaban sus dos subarray a fusionar, los que determinan sus tallas y permiten inicializar adecuadamente las variables locales a la fusi´on.
Esta variaci´on de Datos repercute tambi´en en el tipo del resultado del m´etodo; en lugar de un nuevo array el resultado es el propio v[izq...der] ya ordenado, por lo que la fusi´on se realiza en un array auxiliar que luego se debe copiar en v[izq...der].
El siguiente m´etodo fusionDyV recoge todos estos cambios: /** izqA es la 1er posici´ on del array ordenado en la 1-er llamada; * juega el papel de a[0] en fusion, de ah´ ı su nombre * izqB es la 1er posici´ on del array ordenado en la segunda llamada; * juega el papel de b[0] en fusion, de ah´ ı su nombre. Adem´ as, * izqB == derA + 1, por lo que derA no aparece como par´ ametro formal * derB es la ´ ultima posici´ on del array ordenado en la segunda llamada; * juega el papel de b[b.length] en fusion, de ah´ ı su nombre **/ private static <T extends Comparable<T>> void fusionDyV(T v[],int izqA,int izqB,int derB){ T[] res = Arrays.copyOf(v, derB-izqA+1); int i = izqA, derA = izqB - 1, j = izqB, k = 0; while ( i <= derA && j <= derB ){ if ( v[i].compareTo(v[j])<0 ) res[k] = v[i++]; else res[k] = v[j++]; k++; } for ( int l = i; l <= derA; l++ ) res[k++] = v[l]; for ( int l = j; l <= derB; l++ ) res[k++] = v[l]; // res se copia en v[izq...der] for ( int l = izqA; l <= derB; l++ ) v[l] = res[l-izqA]; } Recordar finalmente que hay que realizar la invocaci´on mergeSort(v,0,v.length-1) desde un m´etodo gu´ıa hom´onimo para ordenar un array v.
Ejercicio propuesto: sea el array de Integer (3,41,52,26,38,5,7,9,49); real´ıcese una traza del m´etodo mergeSort sobre ´el.
M.Galiano,N.Prieto 43 2.
Validaci´ on de mergeSort Como para cualquier otro m´etodo recursivo, la validaci´on de mergeSort se compone de las siguientes pruebas: 1. Terminaci´ on: en su caso general la talla del problema x = der-izq+1 decrece, pues en cada una de las dos llamadas que se producen se divide aproximadamente por 2: la talla de mergeSort(v,izq,mitad) es mitad-izq+1 = x2 y la de mergeSort(v,mitad+1,der) es der-mitad = x−1 , cualquiera de ellas menor estricta que x puesto que x≥2 si izq<der; 2 por tanto, en base a las propiedades de la divisi´on entera, ambas pueden alcanzar en un tiempo finito el valor 1 del caso base, donde termina la Recursi´on.
2. Coherencia de las llamadas recursivas: en cualquiera de los casos establecidos, los valores de los par´ametros formales izq y der siempre cumplen la Precondici´on ya que en cualquier llamada, al ser 0 ≤ izq ≤ mitad < der < v.length, var´ıan dentro del dominio de definici´on, i.e. 0 ≤ i ≤ j < v.length; n´otese que en la llamada m´as alta izq=0 y der=v.length-1 y en cualquier otra bien se mantienen como en la precedente (el de izq en la primera y el de der en la segunda) o bien, cuando var´ıan, izq lo hace en el intervalo [mitad+1 ... v.length-1] y der en [0...mitad].
3. Correcci´ on: probar por Inducci´on que mergeSort ordena v[izq...der] supone a su vez Base de la Inducci´ on: probar que si x=1 entonces mergeSort(v, izq, der) ordena la u ´ nica componente de v[izq...der]. N´otese que esta prueba es trivial porque un array de talla uno ya est´a ordenado y mergeSort no hace nada si izq == der.
Prueba de Inducci´ on: probar que si x>1 entonces mergeSort(v, izq, der) ordena el subarray v[izq...der], suponiendo por Hip´ otesis de Inducci´ on (HI) que la llamada a mergeSort(v, izq, mitad) ordena v[izq...mitad] y que la llamada a mergeSort(v, mitad+1, der) hace otro tanto con v[mitad+1...der].
Tambi´en ahora la prueba es f´acil: si por HI v[izq...mitad] y v[mitad+1...der] est´an ordenados entonces fusionDyV los mezcla en un u ´ nico array v[izq...der] tambi´en ordenado y, por tanto, mergeSort en su caso general es correcto; n´otese que es la correcci´on de fusionDyV la que garantiza la de mergeSort.
Coste Asint´ otico de mergeSort Para comprobar que el coste Temporal de mergeSort es Θ(x ∗ log2 x) se deben obtener primero a partir de su c´odigo las siguientes Relaciones de Recurrencia: TmergeSort (x=1) = k’ TmergeSort (x>1) = 2 ∗ TmergeSort ( 2x ) + TfusionDyV (x) Recordando entonces que TfusionDyV (x) ∈ Θ(x) y aplicando el Teorema 4 con a=c=2 se tiene que para cualquier instancia TmergeSort (x) ∈ Θ(x ∗ log2 x).
A pesar de este excelente coste Temporal, que puede ser mejorado significativamente como se propone en los ejercicios 1 y 2 que figuran a continuaci´on, mergeSort presenta un serio inconveniente frente a otros m´etodos de Ordenaci´on r´apida in-situ que se estudiar´an m´as adelante: requiere inevitablemente el uso de un array auxiliar para llevar a cabo la fusi´on de los subarray ya ordenados v[izq...mitad] y v[mitad+1...der] y, por ello, su coste Espacial de ejecuci´on, que no el Asint´otico, dobla al de ´estos.
44 2.
Ejercicios propuestos: 1. Real´ıcense las modificaciones necesarias en el m´etodo mergeSort propuesto para que en cada llamada a fusionDyV se evite la copia del array auxiliar en el original.
2. Determ´ınese experimentalmente el valor de la talla umbral para mergeSort, esto es el tama˜ no del array v a partir del cu´al es m´as efectivo espacial y temporalmente ordenar por un m´etodo directo como insercionDirecta.
3. Una estrategia alternativa a la presentada para dise˜ nar la Ordenaci´on por Fusi´on ser´ıa la de dividir el array en tres partes, ordenarlas y despu´es fusionarlas. Anal´ıcese su coste Temporal e ind´ıquese si mejora el del m´etodo mergeSort propuesto.
2.2.2.
Quick Sort: m´ etodos quickSort y particion Para evitar la fusi´on de subarrays ya ordenados que caracteriza a mergeSort se puede pensar en DIVIDIR el subarray a ordenar utilizando un procedimiento un poco m´as sofisticado: ordenar una dada de sus componentes, el denominado pivote, situando a su izquierda aquellas que sean menores (o iguales) que ella y situando a su derecha aquellas que sean mayores (o iguales); as´ı, como ilustra la siguiente figura, la ordenaci´on del pivote provoca una Partici´ on del resto de las componentes del subarray en dos grupos disjuntos, que acto seguido pueden ser ordenados independientemente usando el mismo procedimiento.
La estrategia DyV esbozada recibe el nombre de Quick Sort y, como se puede deducir con ayuda del ejemplo de la figura anterior, sus dos caracter´ısticas m´as relevantes son las siguientes: M.Galiano,N.Prieto 45 2.
1. para que la Partici´on del subarray a ordenar se produzca en un tiempo lineal, y con ello se cumpla la restricci´on de sobrecarga que exige la estrategia DyV, el pivote se debe ordenar por Intercambio: para ordenar la componente elegida como pivote en el ejemplo, v[4] = 57, como 92 es mayor que 57 y 13 menor, intercambiar(92, 13); como 81 es mayor que 57 y 26 menor, intercambiar(81,26); ...; tras intercambiar(65,43) concluye la Partici´on porque el pivote es igual a s´ı mismo. N´otese entonces que, obviamente, el n´ umero de comparaciones realizadas es exactamente igual a la talla del subarray v.
2. la Partici´ on del subarray v es m´ as o menos equilibrada en funci´ on del pivote que se elija, o m´as precisamente del valor que tenga el pivote con respecto a los que poseen las restantes componentes del subarray: u ´ nica y exclusivamente porque el pivote elegido en el ejemplo, v[4] = 57, es la mediana de las componentes a ordenar la Partici´on que se produce es la m´as equilibrada posible, o da lugar a dos subarray de talla aproximadamente igual a la mitad de la original; sin embargo, si se hubiera elegido como pivote la componente m´ınima o la m´axima del subarray, v[8] = 13 o v[0] = 92, la Partici´on habr´ıa sido completamente desequilibrada, un subarray vac´ıo y otro con una componente menos que el original.
En resumen, y teniendo en cuenta que al DIVIDIR es posible generar subarray vac´ıos, una posible transcripci´on Java de la estrategia de Ordenaci´on DyV Quick Sort ser´ıa la siguiente: private static <T extends Comparable<T>> void quickSort(T v[], int izq, int der){ if (izq < der){ // DIVIDIR el problema en dos subproblemas disjuntos: ordenar por Intercambio // el pivote de forma que, EN PROMEDIO, se obtenga una Partici´ on equilibrada int indiceP = particion(v, izq, der); // VENCER cada subproblema planteado: EN PROMEDIO, // ordenar por Quick Sort x/2 componentes menores(o iguales) que el pivote // ordenar por Quick Sort x/2 componentes mayores (o iguales) que el pivote quickSort(v, izq, indiceP-1); quickSort(v, indiceP+1, der); // ******** NO ES NECESARIO COMBINAR ******** // v[izq ... der] YA est´ a ordenado: se ha ordenado su pivote v[indiceP] // y se han ordenado v[izq ... indiceP-1] y v[indiceP+1 ... der] } } public static <T extends Comparable<T>> void quickSort(T v[]){ quickSort(v, 0, v.length-1); } Cabe rese˜ nar que en este c´odigo no se especifican detalles de dise˜ no que pueden afectar significativamente a su coste, como la elecci´on del pivote o el tratamiento de las componentes que son iguales al pivote o la forma precisa de realizar la Partici´on en tiempo lineal; s´olo cuando se realice el an´alisis del coste de quickSort se estar´a en disposici´on de decidir cu´al es la mejor manera de implementarlos, por lo que se ha decidido relegarlos al dise˜ no del m´etodo particion que se realizar´a m´as adelante.
Ejercicio propuesto: recordando que la talla del problema puede llegar a valer cero y suponiendo que el m´etodo particion funciona correctamente, realizar la validaci´on de quickSort.
46 2.
Coste Asint´ otico de quickSort Para tallas mayorores que uno la Complejidad del m´etodo quickSort depende u ´ nicamente del resultado del m´etodo particion, el int indiceP que representa el orden que el pivote elegido ocupa entre las componentes de v y, por tanto, determina la talla de las dos llamadas que se realizan tras obtenerlo, quickSort(v,izq,indiceP-1) y quickSort(v,indiceP+1,der), o la talla de los respectivos subarray vI y vD que se ordenan con ellas.
As´ı, en el Mejor de los Casos indiceP = (izq+der) en cada llamada que se realiza a quickSort, 2 i.e. el pivote y la mediana de v coinciden y se logra una Partici´on completamente equilibrada en dos subarray de talla aproximada x2 . La Relaci´on de Recurrencia para este caso, TquickSort M (x>1) = 2 ∗ TquickSort M ( x2 ) + k ∗ x se puede resolver utilizando el Teorema 4 con a=c=2, de donde TquickSort M (x)∈Θ(x ∗ log2 x); por tanto, para cualquier instancia del problema TquickSort (x) ∈ Ω(x ∗ log2 x).
En el Peor de los Casos indiceP = izq o indiceP = der en cada llamada, i.e. el pivote elegido es el m´ınimo o el m´aximo de v y se origina una Partici´on completamente desequilibrada en dos subarray, uno vac´ıo y otro que contiene todas las componentes de v menos el pivote: si indiceP = izq, vI es un array vac´ıo y vD = v[izq+1...der] y si indiceP = der, vD es un array vac´ıo y vI = v[izq...der-1]. A ra´ız de esta Partici´on, la llamada recursiva asociada al subarray vac´ıo ya no genera m´as llamadas y es s´olo la otra la que se considera para expresar la Complejidad de quickSort en el Peor de los Casos: TquickSort P (x>1) = 1 ∗ TquickSort P (x-1) + k ∗ x Aplic´andole el Teorema 2 con a = c = 1, TquickSort P (x) ∈ Θ(x2 ) y, para cualquier otra instancia, TquickSort (x) ∈ O(x2 ).
Los resultados del an´alisis realizado permiten concluir que, cuando se dise˜ ne particion, una buena implementaci´on de la selecci´on del pivote y del paso de Partici´on debiera minimizar la posibilidad de obtener una Partici´on desequilibrada, esto es con tallas de vI y vD desiguales, a´ un para instancias degeneradas como aquellas en las que v est´a inicialmente ordenado Ascendente o descendentemente o, peor a´ un, aquellas en las que todas sus componentes son iguales. Asimismo, vista la enorme diferencia que los separa, obligan a plantear sin paliativos el estudio de su coste Medio; recu´erdese que ya al presentar la estrategia DyV para la Ordenaci´on R´apida se ha indicado que se espera, en promedio, DIVIDIR la talla original por la mitad al ordenar cada componente del array en tiempo lineal, lo que supone que la cota O(x ∗ log2 x) indicada es la de su caso Medio. Aunque esta expectativa es suficiente para los prop´ositos de la asignatura, no constituye sin embargo una demostraci´on formal, como la que se puede encontrar en las p´aginas de la 228 a la 230 del Cap´ıtulo 8 del libro de Weiss; en ella, se logra calcular el coste Medio de cada llamada recursiva a quickSort y, a partir de ´el, el coste medio de quickSort que es, efectivamente, O(x ∗ log2 x).
Dise˜ no del m´ etodo particion A continuaci´on se propone un esquema algor´ıtmico del m´etodo particion que, en tiempo lineal, debe seleccionar una componente de v[izq...der] como pivote y ordenarla con respecto a las dem´as; no se considera en ´el la posibilidad de que existan componentes iguales al pivote: M.Galiano,N.Prieto 47 2.
T pivote = elegirPivote(v, izq, der); /** ordenar el pivote: para toda componente de v[izq...der] * intercambiar aquella que situada a la izquierda del pivote, * desde izq, sea mayor que ´ este CON aquella que situada a la * derecha del pivote, desde der, sea menor que ´ este **/ int i = izq; int j = der; do{ /** B´ usqueda Ascendente de la primera componente de v[i...der] mayor que el pivote */ while ( v[i].compareTo(pivote) < 0 ) {i++} /** B´ usqueda Descendente de la primera componente de v[izq...j] menor que el pivote */ while ( v[j].compareTo(pivote) > 0 ) {j--} /** intercambiar v[i] con v[j] y seguir */ if ( i <= j ) { intercambiar( v, i, j); i++; j--; } } while ( i <= j ) /** i > j AND (pivote = v[j] AND vI == v[izq...j-1] AND vD = v[i...der]) * OR (pivote = v[i] AND vI == v[izq...j] AND vD = v[i+1...der]) * * Para ordenar el resto, ejecutar quickSort(v, izq, j); quickSort(v, i, der); **/ En lo que sigue, en primer lugar se completar´a su dise˜ no desarrollando aquellas implementaciones de la elecci´on del pivote y el tratamiento de las componentes iguales a ´el que garanticen que al ordenar el pivote se consigue una divisi´on equilibrada de v; una vez se disponga de c´odigo ejecutable, se introducir´an en ´el nuevas modificaciones para ahorrar intercambios y comparaciones innecesarias, lo que mejorar´a su coste real de ejecuci´on, que no el Asint´otico, a costa de su legibilidad.
Implementaci´ on eficaz de la elecci´ on del pivote El estudio del Peor de los Casos indica que para una elecci´on del pivote eficaz se requiere un m´etodo que, independientemente de la instancia, minimice la posibilidad de obtener una Partici´on desequilibrada. As´ı, queda excluido elegir el pivote como la primera (´ ultima) componente de v, pues si ´este inicialmente ya est´a ordenado ascendentemente ser´ıa su m´ınimo (m´aximo) -viceversa para el orden inverso- o elegirlo al azar, pues para instancias aleatorias puede resultar ser el m´aximo o el m´ınimo de v.
Una elecci´on m´as razonable es la de la componente central de v, v[ izq+der ], perfecta para 2 instancias ordenadas puesto que coincide con su mediana y que para instancias aleatorias tiene una probabilidad muy baja de forzar un coste cuadr´atico. Sin embargo, se le puede achacar como defecto que sea una estrategia tan pasiva como las anteriores, que no hace nada para seleccionar un buen pivote pero evita elegir uno malo.
En el m´etodo que se propone ahora, la Mediana de Tres, se intenta seleccionar un pivote mejor que el central partiendo del hecho de que, como indica el estudio del Mejor de los Casos, el mejor pivote de cualquier array es su componente mediana; como por desgracia el c´alculo de la mediana de v[izq...der] aumenta significativamente la sobrecarga real de quickSort, para obtener una buena estimaci´on de ´esta en tiempo constante se calcula la mediana de s´olo tres de sus componentes: la primera, la central y la u ´ ltima.
48 2.
private static <T extends Comparable<T>> T int central = (primera+ultima)/2; if ( v[central].compareTo(v[primera]) if ( v[ultima].compareTo(v[primera]) if ( v[ultima].compareTo(v[central]) /** v[central] es la Mediana de Tres, * menor (o igual) que v[ultima] **/ return v[central]; } medianaDeTres(T v[], int primera, int ultima){ < 0 ) intercambiar(v, primera, central); < 0 ) intercambiar(v, primera, ultima); < 0 ) intercambiar(v, central, ultima); mayor (o igual) que v[primera] y Utilizar medianaDeTres como implementaci´on de elegirPivote supone realizar en el esquema de particion, adem´as de un obvio cambio de nombre, una serie de peque˜ nos ajustes: gracias a que la ejecuci´on de medianaDeTres(v, izq, der) no s´olo proporciona el pivote de sino que tambi´en ordena v[izq] y v[der] con respecto a ´este, la Partici´on en posici´on izq+der 2 las B´ usquedas de componentes a intercambiar pueden empezar en i = izq+1 y j = der-1, en lugar de izq y der respectivamente, y tener como centinelas a las propias v[izq] y v[der], en la Descendente sobre j y en la Ascendente sobre i respectivamente.
Tratamiento eficaz de las componentes iguales al pivote Hasta el momento se ha eliminado del esquema de particion la posibilidad de que en el array existan componentes iguales al pivote; con ello se exclu´ıa tambi´en la posibilidad de ordenar con quickSort instancias con todas las componentes iguales, que aunque a primera vista pueda parecer hasta absurda -¿cu´ando sino se puede encontrar un caso real en el que se quieran ordenar miles de componentes iguales?- no lo es tanto cuando se recuerda que quickSort es un m´etodo recursivo. Por ejemplo, si se quiere ordenar un array de 1.000.000 componentes, de las cuales 3.000 son iguales entre s´ı, no es de extra˜ nar que un momento dado se produzca una llamada recursiva con s´olo esas 3.000; y para tal ocasi´on, resulta imprescindible asegurar que quickSort sigue siendo un m´etodo eficiente.
La discusi´on anterior muestra la necesidad de contemplar detenidamente cu´al de las dos siguientes estrategias es la mejor cuando en una B´ usqueda del bucle de Partici´on aparece una componente igual al pivote: parar la B´ usqueda como cuando se encuentra una componente mal situada con respecto al pivote y, por tanto, intercambiarla con otra m´as tarde o bien continuar.
Para responder adecuadamente, consid´erese de nuevo el caso en el que todas las componentes del array sean iguales. Parar la B´ usqueda provocar´ıa un intercambio por cada par de componentes ¡iguales! comparadas con el pivote, esto es x2 intercambios por cada x comparaciones; aunque pudiera parecer un desperdicio de tiempo, sin embargo, no lo es: gracias a ´el, los ´ındices i y j se cruzan justo en el centro del array, la posici´on del pivote, por lo que la Partici´on resultante es siempre equilibrada. Por el contrario, si la decisi´on que se toma al encontrar una componente igual al pivote es continuar la B´ usqueda, aunque no se produce intercambio alguno, a cambio, i terminar´ıa valiendo der, si se hubiera controlado el posible overflow y, por tanto, se obtendr´ıa una Partici´on completamente desequilibrada.
El an´alisis realizado es concluyente: como es mejor hacer intercambios innecesarios que particiones desiguales, hay que detener la B´ usqueda del bucle de Partici´on en la que aparezca una componente igual al pivote. N´otese que el esquema de particion presentado ya contempla esta situaci´on, por lo que no sufrir´a modificaci´on alguna para que trate eficazmente aquellos array que tengan componentes repetidas.
M.Galiano,N.Prieto 49 2.
Algunas mejoras m´ as del coste efectivo de particion Como se indic´o al principio de esta secci´on, una vez se dispone de c´odigo ejecutable para particion se le pueden introducir algunas modificaciones para que, a costa de la legibilidad, mejore su coste real de ejecuci´on. Espec´ıficamente, el c´odigo que figura a continuaci´on es el resultado de realizar las siguientes: 1. Eliminar los intercambios innecesarios que se producen para desplazar el pivote desde su posici´on inicial (la central del array) hasta su posici´on ordenada; para ello, basta con quitarlo de en medio durante el proceso de su ordenaci´on, dej´andolo por ejemplo en la posici´on der-1, y situarlo en su posici´on ordenada una vez ´esta haya sido establecida.
Cuesti´ on: ¿cu´al es la posici´on ordenada del pivote en la primer Partici´on del array de Integer [10, 4, 8,2, 3, 1, 9]? Calc´ ulese cu´antos intercambios cuesta situar al pivote en ella cuando su posici´on inicial es la central del array y cuando es der-1.
2. Eliminar el if ( i<=j ) que precede a cada intercambio del anterior bucle de particion para que ´este se realice siempre dentro de los l´ımites del array; para ello, basta con ejecutar una vez menos el bucle de Partici´on, s´olo mientras i<j. Aunque as´ı se puede producir a veces un u ´ ltimo intercambio incorrecto basta con deshacerlo al acabar el bucle.
3. Compactar al m´aximo los dos bucles de B´ usqueda modificando, s´olo, su inicializaci´on.
T pivote = medianaDeTres(v, izq, der); /** ocultar el pivote en la posici´ on der-1, pues para ordenarlo basta * buscar su posici´ on ordenada y, tras encontrarla, situarlo en ella */ intercambiar(v, (izq+der)/2, der-1); /** ordenar el pivote: buscar la posici´ on ordenada del pivote */ int i = izq; int j = der - 1; for ( ; i < j ; ){ /** B´ usqueda Ascendente de la primera componente * de v[i...der] mayor o igual que el pivote */ while ( v[++i].compareTo(pivote) < 0 ){} /** B´ usqueda Descendente de la primera componente * de v[izq...j] menor o igual que el pivote */ while ( v[--j].compareTo(pivote) > 0 ){} /** intercambiar v[i] con v[j] **/ intercambiar(v, i, j); } /** deshacer el ´ ultimo intercambio por si fuera incorrecto */ intercambiar(v, i, j); /** restaurar el pivote: situarlo en su posici´ on ordenada */ intercambiar(v, i, der-1); /** izq <= i < der AND pivote = v[i] AND vI == v[izq...i-1] AND vD == v[i+1...der] * Para ordenar el resto, ejecutar quickSort(v, izq, i-1); quickSort(v, i+1, der); */ quickSort VS mergeSort Para finalizar esta secci´on se debe se˜ nalar que quickSort (casi) siempre es m´as r´apido que mergeSort gracias a lo compacto y sofisticado que resulta el c´odigo de particion, tan laboriosamente obtenido: aunque en promedio ambos m´etodos resuelven el problema de ordenar un array de igual manera, dos llamadas recursivas de talla la mitad que la original y una sobrecarga lineal, el proceso de Partici´on implementado es m´as eficiente que el de Fusi´on, aunque no siempre conduzca a divisiones de la talla equilibradas, y no requiere de un array auxiliar.
50 2.
Ejercicios propuestos: 1. Real´ıcese la traza de la ejecuci´on de quickSort(v, 0, 10) sobre el array de Integer {86, 66, 24, 78, 100, 106, 46, 53, 89, 69, 5}, indicando para cada llamada recursiva el valor de los par´ametros izq y der, el estado del array tras la llamada a medianaDeTres y el valor del pivote, los intercambios que se realizan en el bucle de Partici´on y el estado del array tras los intercambios y la restauraci´on del pivote.
2. Ord´enese el array {8, 1, 4, 1, 5, 9, 2, 6, 5} usando los m´etodos insercionDirecta, mergeSort, quickSort con pivote igual a la componente central del array y quickSort con pivote igual a la Mediana de Tres y talla umbral de tres.
3. Si todas las componentes del array son iguales ¿qu´e tiempos de ejecuci´on tienen mergeSort, quickSort e insercionDirecta? ¿y si las componentes ya est´an ordenadas inicialmente? 2.3.
Una soluci´ on eficiente al problema de la Selecci´ on: m´ etodo seleccionRapida Estrechamente relacionado con el de Ordenaci´on, el denominado problema de la Selecci´ on consiste en encontrar el k-´esimo menor Dato de una Colecci´on de talla dada, del que un caso particular importante es el c´alculo de su mediana, o sea del x2 -´esimo menor. Si la Colecci´on se representa sobre un array, una soluci´on al problema de coste Θ(x ∗ log x) ser´ıa ordenarlo, por ejemplo con quickSort, y despu´es acceder a su posici´on k-1 (recu´erdese que la primera posici´on de un array es la cero); alternativamente, se puede obtener el mismo resultado pero con coste Θ(x ∗ k) tras ordenar con seleccionDirecta las k-1 primeras componentes del array. Ahora bien, como la Selecci´on es un problema m´as sencillo que la Ordenaci´on, un peque˜ no cambio en quickSort es capaz de rebajar los costes anteriores hasta una cota promedio lineal con la talla. En efecto, la denominada estrategia de Selecci´ on R´ apida, se basa en la idea de que ordenar el pivote de v[izq...der], 0≤izq≤der< v.length, i.e. situarlo en su posici´on ordenada indiceP, provoca una Partici´on en la que todas las componentes menores o iguales que el pivote se sit´ uan a su izquierda, en vI == v[izq...indiceP-1], y todas las mayores o iguales a su derecha, en vD == v[indiceP+1...der]. As´ı, si despu´es de la Partici´on k-1 = indiceP, la k-´esima menor componente ya ocupa la posici´on k-1 de v; sino, cuando k-1 < indiceP la k-´esima menor componente v se debe buscar en vI y sino en vD. Naturalmente el proceso expuesto es v´alido para array de talla mayor estricta que uno; cuando s´olo hay una componente ´esta es la u ´ nica que puede ser seleccionada, con lo que concluye el proceso.
El siguiente m´etodo Java implementa la estrategia de Selecci´on R´apida expuesta para tallas mayores que una cierta talla umbral, que expresa indirectamente la constante LIMITE: private static <T extends Comparable<T>> void seleccionRapida(T v[],int k,int izq,int der){ if ( izq + LIMITE > der) insercionDirecta(v, izq, der); else{ int indiceP = particion(v, izq, der); if ( k-1 < indiceP ) seleccionRapida(v, k, izq, indiceP-1); else if ( k-1 > indiceP ) seleccionRapida(v, k, indiceP+1, der); } } public static <T extends Comparable<T>> void seleccionRapida(T v[], int k){ seleccionRapida(v, k, 0, v.length-1); } M.Galiano,N.Prieto 51 2.
Ejercicios propuestos: 1. Anal´ıcese de manera pormenorizada el coste Asint´otico del m´etodo seleccionRapida para las instancias significativas del problema.
2. Real´ıcese la traza de la ejecuci´on de seleccionRapida(v,4) sobre el array de Integer [86, 66, 24, 78, 100, 106, 46, 53, 89, 69, 5)], indicando para cada una de las llamadas recursivas los valores de los par´ametros izq y der, el estado de v tras la llamada a medianaDeTres y el valor del pivote, los intercambios que se realizan en el bucle de Partici´on y el estado de v tras los intercambios y la restauraci´on del pivote.
52 ...