Retomando aquí el socorrido ejemplo del factorial, tratemos de analizar el coste de dicho algoritmo, en su versión iterativa, codificada en MODULA 2, se tiene:
PROCEDURE Factorial(n : CARDINAL) : CARDINAL
BEGIN
VAR Resultado,i : CARDINAL ;
Resultado :=1 ;
FOR i :=1 TO n DO
Resultado :=Resultado*i ;
END ;
RETURN Resultado
END Factorial ;
Aplicando las técnicas de análisis de coste en
algoritmos iterativos de forma rápida y mentalmente (es
como se han de llegar a analizar algoritmos tan simples
como éste), se tiene: hay una inicialización antes de
bucle, de coste constante. El bucle se repite un número
de veces n y en su interior se realiza una operación de
coste constante. Por tanto el algoritmo es de coste
lineal o expresado con algo más de detalle y rigor, si
la función de coste del algoritmo se expresa por T(n),
se tiene que T(n)
.
Una versión recursiva del mismo algoritmo, también codificada en MODULA-2, es:
PROCEDURE Factorial(n: CARDINAL): CARDINAL; BEGIN IF n=0 THEN RETURN 1 ELSE END END Factorial;
Al aplicar el análisis de coste aprendido para análisis de algoritmos iterativos se tiene: hay una instrucción de alternativa, en una de las alternativas simplemente se devuelve un valor (operación de coste constante). En la otra alternativa se realiza una operación de coste constante (multiplicación) con dos operandos. El primer operando se obtiene por una operación de coste constante (acceso a la variable n), el coste de la operación que permite obtener el segundo operando es ??? ... es ???... : -()... : -( .... ¡ es el coste que estamos calculando !, es decir es el coste de la propia función factorial (solo que para parámetro n-1). Es decir, para conocer el orden de la función de coste de este algoritmo ¿ debemos conocer previamente el orden de la función de coste de este algoritmo ?, entramos en una recurrencia .
Y efectivamente, el asunto está en saber resolver recurrencias. Si T(n) es la función de coste de este algoritmo se puede decir que T(n) es igual a una operación de coste constante c cuando n vale 0 y a una operación de coste T(n-1) más una operación de coste constante (el acceso a n y la multiplicación) cuando n es mayor que 0, es decir:
Se trata entonces de encontrar soluciones a recurrencias como ésta. Entendiendo por solución una función simple f(n) tal que se pueda asegurar que T(n) es del orden de f(n).
En este ejemplo puede comprobarse que T(n) es de orden lineal, es decir del orden de la función f(n)=n, ya que cualquier función lineal T(n)= a.n +b siendo a y b constantes, es solución de la recurrencia:
T(0)= b , es decir una constante
T(n)= a.n+b= an-a+ b+a= a(n-1)+b+a= T(n-1)+a , es decir el coste de T(n) es igual al de T(n-1) más una constante.
Una buena noticia: el planteamiento y solución de recurrencias, abordándolo desde un punto de vista general, queda fuera del programa de PROGRAMACION II. Una menos buena: sí que forma parte del programa de PROGRAMACION III (el lector interesado puede empezar a estudiarlas en "Fundamentos de Algoritmia" de Brassard y Batley, texto básico de PROGRAMACION III ). Otra muy importante: en PROGRAMACION II han de conocerse y aplicarse dos recurrencias básicas que permiten analizar el coste de muchos algoritmos recursivos, y en concreto de todos los estudiados en esta asignatura.
Dos recurrencias básicas
Para el análisis de coste de los algoritmos recursivos que se abordan en PROGRAMACION II va a ser necesario conocer dos tipos básicos de recurrencia, se ha de saber también aplicar la solución de estas recurrencias a problemas concretos y , es más, se han de saber interpretar los parámetros fundamentales que intervienen en ellas.
Las primera de ellas es:
Esta recurrencia es aplicable a cualquier algoritmo recursivo en el que:
a) El cálculo del caso trivial es una operación de orden polinómico nk, es decir, para k=0 una operación de coste constante, para k=1 una operación de coste lineal, para k=2 una operación de coste cuadrático etc.
b) El cálculo del caso no trivial se realiza por medio de a llamadas a la propia función recursiva con tamaño de problema reducido mediante resta en un factor b. Además se realiza una operación adicional que se supone del mismo tipo (en cuanto a coste asintótico) que la de caso trivial.
Al apricarla a ejemplos se comprenderán mejor estos conceptos, pero no se ha de olvidar que:
a) k determina el orden de la operación de caso trivial y de la adicional de caso no trivial
b) a es el número de llamadas recursivas necesarias para realizar la operación de caso no trivial, a=1 en los casos de recursividad simple, que serán los habituales.
c) b es el valor en que se disminuye, por substracción, el tamaño del problema en cada llamada.
Una vez identificados los valores a,b y k de un problema concreto, la solución a esta recurrencia es que la función de coste T(n) será de un orden dado por:
La segunda recurrencia es:
y la única diferencia básica , respecto a la primera, es que la reducción del tamaño del problema se hace por división, siendo ahora b el divisor.
La solución a esta segunda recurrencia es:
Como ya se ha indicado, la mejor forma de comprender el sentido de estas recurrencias y sus soluciones es aplicarlas a ejemplos concretos. Después, se ha de ser capaz de sintetizar la información de cara a comprender cómo influyen los parámetros a, b y k, y el tipo de recursividad (con reducción de coste por resta o por división), en el coste final del algoritmo. Por lo tanto, manos a los ejemplos.
Ejemplos
1) Factorial
El algoritmo recursivo de cálculo del factorial de un número natural n se realiza recursivamente:
devolviendo directamente 1 si n=0
devolviendo el producto de n y el resultado de una llamada recursiva a la propia función para parámetro n-1 si n >0
en este caso, y puesto que se reduce el problema por resta, se tiene la primera recursividad (Rec 1) con:
a=1 (una sola llamada recursiva en el caso trivial)
b=1 (el valor en que se disminuye el tamaño de problema)
k=0 (coste constante en operaciones adicionales y trivial)
Aplicando la solución (Sol 1)
se obtiene 
2) Suma lineal de los elementos de un vector
El siguiente algoritmo recursivo devuelve la suma de los elementos de un vector v definido como vect: vector [1..n] de enteros. En realidad es una función que calcula la suma de los elementos del vector de índices entre 1 e i, si se ejecuta con i=n suma todos los elementos del vector. Para obtener la suma de los elementos de índices entre 1 e i aplica el siguiente razonamiento recursivo: si i=0 devolver 0 (suma de los elementos de un vector vacío), sin i>0 ejecutar recursivamente la propia función para sumar los elementos de índices entre 1 e i-1, entonces sumarle a este resultado el valor de v[i]:
fun suma(v: vect; i:entero) dev s: entero
caso i=0 -> 0
. i>0 -> suma(v,i-1)+ v[i];
fcaso
ffun
El tamaño de problema viene dado por n (número total de elementos del vector a sumar) La reducción del tamaño de problema es por resta (Rec 1) se tiene:
a=1 (una sola llamada recursiva)
b=1 (el valor en que se disminuye el tamaño de problema
k=0 (operaciones adicionales y trivial de coste constante)
Luego de nuevo la solución (Sol
1) es
3) Búsqueda lineal
El siguiente algoritmo (que se expresa en pseudocódigo simplificado, quien ya domine la notación de Peña no tendrá dificultades en traducirlo a dicha notación), búsqueda lineal, busca un elemento x en un vector v de índices 1..n. Para ello el algoritmo que en realidad busca el elemento entre los elementos de índices i a n , y se ha de ejecutar con parámetro de llamada inicial i=1. Devuelve dos elementos: un booleano que indica si la búsqueda ha tenido éxito, y el índice del lugar en el que se encuentra x (en caso de fracaso en la búsqueda este índice no es significativo). La búsqueda es lineal, el caso trivial se tiene cuando i=n+1 y por tanto se busca en un vector vacío. En este caso devuelve falso en el booleano. En el caso no trivial devuelve cierto si v[i] es el elemento buscado y si no es así ejecuta una llamada recursiva a la propia función para que busque en i+1 ...n.
funcion Busqueda(v: vect; x,i:entero) dev (b: booleano, p:entero)
si i>n entonces devolver <falso, i>
sino
si x=v[i] entonces devolver <cierto,i>
sino BusquedaLineal(v,x,i+1);
fsi
fsi
ffun
El tamaño de problema aquí es la longitud del tamaño de búsqueda, dada por n-i, es decir la función de coste es t(n,i)=n-i, al realizar la llamada recursiva se hace con i+1 como segundo parámetro luego la función de coste vale t(n,i+1)=n-(i+1)=(n-i)-1=t(n,i)-1. Es decir, la reducción del tamaño de problema es por resta con b=1. Por tanto:
a=1 (una sola llamada recursiva en el caso peor)
b=1 (valor en que se disminuye el tamaño de problema)
k=0 (operación trivial y adicional de coste constante )
y de nuevo se tiene función de coste lineal.
4) Búsqueda dicotómica
Cuando el vector está ordenado se puede realizar una búsqueda más eficiente que la lineal, expresado en forma simplificada para buscar el elemento en el intervalo de índices i a j del vector, se toma el valor medio m=(i+ j) div 2, si x está en esa posición se devuelve cierto y el índice m, si no es así se compara x con el elemento v[m], si x es menor que v[m] se ha de buscar en la mitad inferior del intervalo, si es mayor que v[m] se ha de buscar en la mitad superior. El caso trivial es aquel en el que se llega a intervalo nulo (i>j). El algoritmo, conocido como "búsqueda dicotómica" se puede encontrar en el capítulo 4 de Peña (figura 3.5 de la primera edición).
El tamaño de problema viene dado por la longitud del intervalo de búsqueda t(i,j)=j-i, cuando se realiza llamada recursiva el tamaño del intervalo de búsqueda se reduce a la mitad, aproximadamente, en efecto, y por ejemplo:
t(i,m)= t(i, (i+j) div 2) = (i+j) div 2-i » (j-i) div 2 =t(i,j) div 2
Luego se obtiene una recursividad del tipo Rec 2 en la que:
a=1 (una sola llamada recursiva , obsérvese que sólo se ejecuta una de las dos posibles llamadas)
b=2 (división por 2 del intervalo de búsqueda )
k=0 (operación trivial y adicional de coste constante)
Aplicando la solución (Sol 2) se tiene:
Como puede observarse la posibilidad de reducción a la mitad del espacio de búsqueda en cada pasada hace que el algoritmo sea muy eficiente. Al doblar el espacio de búsqueda sólo se incrementa en una llamada recursiva más el proceso
5) Suma "dicotómica"
Supóngase que se intenta un algoritmo de suma "dicotómico" en lugar del lineal del ejemplo 2). El algoritmo calcula la suma de los elementos del vector situados entre los índices i y j llamando recursivamente al propio algoritmo para sumar la mitad inferior del intervalo, volviendo a llamar para sumar la mitad superior y luego sumando ambos resultados. Se puede encontrar en el Capítulo 4 de Peña (pagina 52 de la primera edición).
De forma similar al caso de la búsqueda dicotómica el tamaño del intervalo se disminuye por división por 2 en cada llamada. Sin embargo en este caso se han de realizar dos llamadas recursivas siempre. La recursividad es del tipo Rec 2 con:
a=2 (dos llamadas recursivas cada vez)
b=2 (división por 2 del intervalo de suma)
k=0 (solución trivial y operación adicional de coste constante)
La solución es (téngase en cuenta que a=2> bk =1en este caso):
Es decir, en este caso no se ha conseguido una suma más eficiente que la del algoritmo 2). Ello es debido a que, aunque el intervalo de suma se reduce a la mitad en cada llamada, se han de realizar dos llamadas recursivas, en lugar de una en el algoritmo lineal, siempre.
5) Torres de Hanoi
El algoritmo que resolvía el problema de las torres de Hanoi es:
Procedimiento Hanoi(n, i, j)
Si n=1 entonces
mover disco de i a j
Si no entonces
Hanoi(n-1,i,6-i-j)
mover disco de i a j
Hanoi(n-1,6-i-j,j)
Fin Si
Fin Hanoi
El caso trivial es una operación de coste constante (mover un disco). En el caso no trivial se realizan dos llamadas recursivas con tamaño de problema reducido por resta de 1 (mover n-1 discos) y una operación de coste constante (mover un disco). Luego se tiene recursividad de tipo Rec 1 con:
a=2 (dos llamadas recursivas siempre)
b=1 (se disminuye el tamaño de problema por resta de 1 disco)
k=0 (operación trivial y adicional de coste constante)
Aplicando la solución (Sol 1) se tiene:
Es decir, se trata de un algoritmo de coste exponencial. Estos algoritmos son los llamados "intratables" debido a su elevado coste asintótico. Téngase en cuenta que si un monje moviera un disco por segundo para resolver el problema de las torres para 10 discos tardaría del orden de 210 segundos, es decir 1024 segundos o 17 minutos. Para 11 discos el tiempo se doblaría, es decir sería de unos 34 minutos. Para 20 discos el tiempo ya sería de unos 12 días. Para mover los 64 discos tardaría 264 segundos, es decir 1,84. 1019 segundos o sea algo así como ¡ 600.000 millones de años !. Si en lugar de realizar movimiento manual de discos, se simula en un computador rápido a razón de un movimiento por microsegundo la solución para 64 discos se alcanzaría en unos 600.000 años. O sea que el potente ordenador no evita que estemos todos calvos cuando se acabe de solucionar el problema (según la leyenda el mundo se acaba cuando los monjes hayan conseguido mover los 64 discos)