Cuando se analiza la eficiencia, en tiempo de ejecución, de un algoritmo son posibles distintas aproximaciones : desde el cálculo detallado similar al realizado en Peña 1.1 ( que puede complicarse en muchos algoritmos si se realiza un análisis para distintos contenidos de los datos de entrada, casos más favorables, caso peor, hipótesis de distribución probabilística para los contenidos de los datos de entrada etc ) hasta el análisis asintótico simplificado aplicando reglas prácticas (ver Peña 1.4).
En estos apuntes se seguirá el criterio de análisis asintótico simplificado, si bien nunca se ha de dejar de aplicar el sentido común. Como en todos los modelos simplificados se ha mantener la alerta para no establecer hipótesis simplificadoras que no se correspondan con la realidad.
En lo que sigue se realizará una exposición basada en el criterio de exponer en un apartado inicial una serie de reglas y planteamientos básicos aplicables al análisis de eficiencia en algoritmos iterativos, en un segundo apartado se presenta una lista de ejemplos que permitan comprender algunas de las aproximaciones y técnicas expuestas.
Criterios
1) En general, el análisis se realizará sobre ejemplos expresados según el esquema básico de un algoritmo iterativo:
Inicializar; mientras B hacer Restablecer; Avanzar; fmientras
Se ha de tener en cuenta que cada uno de los bloques básicos: ( Inicializar, Restablecer, Avanzar, incluso el cálculo de la expresión lógica B) pueden a su vez estar formados por una combinación de cada una de las estructuras fundamentales de un lenguaje imperativo:
- SECUENCIA: Composición secuencial de instrucciones: S1, S2, ..., Sn
- ALTERNATIVA: Instrucciones condicionales del tipo: si B entonces S1 si no S2 fsi, o del tipo más general: caso B1 ® S1 ð caso B2® S2....... caso Bn® Sn fcaso
- ITERACION: Iteración, en sus varias formas: mientras B hacer S fmientras, repetir S hasta B, para i desde E1 hasta E2 hacer S fpara, ... Cualquiera de estas formas es transformable a una expresión del primer tipo (bucle "mientras").
( Es conveniente repasar la primera parte del capítulo 4 de Peña ).
2) Para análisis asintótico se aplicarán las reglas de la suma y del producto (Peña Cap 1).
La regla de la suma:
dice que el orden suma de órdenes de varias funciones es igual al orden de la función suma e igual al orden de la función máximo de ambas. En la práctica si se tiene una secuencia de operaciones en un algoritmo: S1, S2, ..., Sn se ha de determinar primero el orden asintótico de cada una de estas operaciones. Entonces el orden de la secuencia es igual al orden de la suma o al orden del máximo. Supóngase, por ejemplo, que en un algoritmo se realizan tres operaciones secuenciales con un vector de tamaño n:
- Asignar un valor dado en el elemento de índice 1.
Operación de coste constante o con función de
coste de orden constante (
) - Sumar todos los elementos del vector. Operación
de coste lineal (
) - Ordenar el vector con un algoritmo de tipo cuadrático
(
)
La secuencia completa será de orden cuadrático puesto que:
Expresado con palabras: cuando el tamaño del problema (n) crece la operación que determina el coste asintótico es la más costosa, o sea la de mayor orden, en este caso la de orden cuadrático. El tiempo de ejecución de esta secuencia de operaciones se multiplicará por cuatro, aproximadamente, al doblar el tamaño del problema. En este crecimiento del tiempo la operación que influye de una forma determinante es la de coste cuadrático.
La regla del producto :
es de aplicación en procesos iterativos. El orden de la función de coste de un proceso iterativo es igual al producto del orden de la función que indica el número de iteraciones en función del tamaño del problema y del orden de la función de coste de la operación interna en el bucle. Este producto de órdenes es , a su vez, igual al orden del producto de la función que expresa el número de iteraciones y la de coste de las operaciones internas al bucle (no confundir "producto del orden" con "orden del producto"). Considérese un ejemplo: Un algoritmo ha de ordenar cada una de las filas de una matriz cuadrada de n x n elementos. El bucle iterativo es:
para i:= 1 hasta n hacer ordenar fila i; fpara
o su equivalente en la forma básica "mientras":
i:=1; mientras i<=n hacer ordenar fila i i:=i+1; fmientras
Es inmediato que el número de repeticiones de la
operación interior es de coste lineal o sea la función
de coste pertenece a , supóngase que para ordenar la fila se
utiliza un algoritmo de tipo cuadrático. Entonces el
coste asintótico de la operación será de tipo cúbico
, ya que:
Es decir, el tiempo de ejecución se multiplicará aproximadamente por 8 cuando la matriz pase de n x n a 2n x 2n.
Por último indicar, que para la ALTERNATIVA, la regla a aplicar será la de analizar el coste de cada una de las operaciones alternativas y tomar la de mayor coste asintótico como coste de la estructura total (análisis en el caso peor)
Ejemplos
1) Ordenación por selección
Entre los métodos elementales de ordenación de vectores se encuentra el algoritmo de selección:
para i desde 1 hasta n hacer imin:= índice del mínimo elemento del vector en v[i..n] intercambiar(v[imin],v[i]); fpara
Es decir, el método se basa en buscar en cada
iteracción el mínimo elemento del subvector situado
entre el índice i y el final del vector
e intercambiarlo con el de índice i.
Tomando la dimensión del vector n como
tamaño del problema es inmediato que el bucle se repite n
veces y por tanto la función que da el número
de repeticiones es de tipo lineal (). La operación interior al bucle
se puede desarrollar a su vez como:
imin:=i; para j desde i+1 hasta n hacer si v[j]<v[imin] entonces imin:=j fsi fpara intercambiar(v[i],v[imin])
Se trata de una secuencia de tres operaciones, la
segunda de las cuales es, a su vez, una iteración. La
primera (asignación) y la tercera(intercambio) pueden
considerarse de coste constante. La segunda es un bucle
que internamente incluye una operación condicional que
en el peor caso supone una operación de coste constante
() (en el
peor caso y en el mejor, puesto que la comparación se ha
de realizar siempre ) y el número de repeticiones de esa
operación es de tipo lineal, ya que se realiza n-(i+1)
veces, y por tanto, al crecer n, el número
de veces crece proporcionalmente a n.
Luego será de coste . =. Éste será entonces el coste de la
secuencia completa (sucesión de dos operaciones de coste
constante y una de coste lineal)
El algoritmo total será entonces de orden .=
Es interesante observar que en este algoritmo el contenido de los datos de entrada , no influye en el coste del algoritmo. En efecto se puede comprobar (aplicar el algoritmo sobre varios vectores ejemplo), que se ejecutan de forma completa ambos bucles tanto para vector desordenado como para vector ordenado
2) Ordenación por inserción
Otro de los métodos simples de ordenación de vectores es el de Inserción:
para i desde 2 hasta n hacer x := v[i]; j : = i-1; mientras j>0 y v[j]> x hacer v[j+1]:=v[j]; j:=j-1; fmientras v[j+1]:=x; fpara
Es conveniente analizar cómo funciona este algoritmo: para cada índice i se guarda en la variable auxiliar x el elemento v[i] y se comienzan a desplazar todos los elementos de índice inferior que sean de valor mayor que el v[i] original (guardado en x), cuando se encuentra un elemento de valor menor o igual que x se guarda x en el hueco libre. La mejor forma de ver como funciona es aplicarlo a vectores sencillos.
Un análisis similar al realizado en el ejercicio anterior permite concluir que el algoritmo es también de coste cuadrático en el caso peor.
Sin embargo este algoritmo es de coste lineal en el caso mejor. Es decir, cuando se aplica sobre vector ya ordenado. Puede comprobarse que, en este caso, las operaciones internas al bucle interno sólo se realizan una vez en cada iteración del bucle externo. Ello es debido a que la comparación v[j]>x dará resultado falso siempre a la primera.
Es decir, si en un caso concreto se ha de optar por uno de los dos algoritmos, el segundo es ventajoso si se va a aplicar sobre vectores en los que la probabilidad de que ya estén ordenados o casi ordenados sea alta. Ésta es una conclusión que va más allá del análisis asintótico, desde ese punto de vista ambos algoritmos son de coste cuadrático.
3) Máximo común divisor
Un algoritmo de cálculo del máximo común divisor de dos enteros n y m es el dado por:
mientras n>0 y m>0 hacer
si n>m entonces
t:=n mod m;
n:=m;
m:=t;
si no
m:=m mod n;
fsi
fmientras
si n=0 devolver m si no devolver n;
O expresado en forma más simple y simétrica si se utiliza la asignación múltiple (ver Peña Cap 4, asignación múltiple ):
mientras n>0 y m>0 hacer
si n>m entonces
<n,m>:=<m, n mod m>;
si no
<n,m>:=<n, m mod n>;
fsi
fmientras
si n=0 devolver m si no devolver n;
Es evidente que aquí las operaciones internas al bucle son de coste constante. El problema es determinar el orden de la función que da el número de repeticiones del bucle. El análisis no es directo, el bucle acaba cuando uno de los enteros acaba tomando el valor 0. En cada iteración el elemento de mayor valor pasa a tomar el valor del menor y el menor pasa a tomar el valor del resto de la división del mayor entre el menor. Conviene ver cómo funciona el algoritmo con algunos ejemplos concretos.
En estos casos una alternativa es la de buscar una función simple que acote superiormente el número de repeticiones del bucle. Se puede observar que el bucle avanza en razón al decrecimiento del mínimo de ambos valores, cuando el mìnimo alcanza el valor cero el bucle finaliza. Se puede demostrar entonces que el mínimo de ambos valores toma un valor igual o menor a la mitad del valor previo en cada iteración:
Dados dos enteros x e y tales que x>=y se tiene que es siempre x mod y <= x/2 . Es decir, el valor del resto de la división es siempre menor o igual que la mitad del dividendo. En efecto:
si y> x/2 entonces es inmediato que x mod y= x-y <x- x/2 = x/2;
si y<= x/2 entonces x mod y< y <= x/2 (por la propiedad del resto).
Puesto que el mínimo de ambos valores se reduce al
menos a la mitad en cada pasada, se tendrá que el número
de repeticiones no será mayor al logaritmo en base 2 del
mayor de los dos enteros. Por tanto el algoritmo es
de coste logarítmico (
(log n), ya que en este caso
no se puede hablar de orden exacto).
Se ha presentado este ejemplo como ilustración de dos problemas que a veces no son simples, por una parte establecer un variable que determine el tamaño del problema, en este caso puede escogerse como tamaño de problema minimo(n,m). Por otra parte, determinar el número de iteraciones de un bucle. En este caso no se puede obtener una solución general exacta, pero es posible acotar superiormente el número de iteraciones por una función apropiada. Estos dos conceptos se asocian en la llamada función limitadora (ver Peña Cap 4), que en este caso podría ser :
T(n,m)= minimo (n,m);
Existe otra forma menos eficiente de algoritmo de máximo común divisor (algoritmo de Euclides), la dada por:
mientras n distinto de m hacer
si n>m entonces
<n,m>:=<n-m,m>;
si no
<n,m>:=<n,m-n>;
fsi
fmientras
devolver n;
Se deja al lector el análisis del coste de este algoritmo y la búsqueda de una función limitadora apropiada para él.
3) Serie de Fibonacci
La sucesión de Fibonacci se define inductivamente como:
Esta sucesión aparece frecuentemente en matemáticas e informática. Un algoritmo para el cálculo del término de orden n de la sucesión puede ser:
i:=1; j:=0; para k desde 1 hasta n hacer j:=i+j; i:=j-i; fpara devolver j;
En principio se puede deducir que es un algoritmo de coste lineal, teniendo en cuenta que el bucle se repite n veces y las operaciones internas son elementales, es decir de coste constante. ¿ Son elementales ?. Si se ejecuta este algoritmo en un computador que utilice enteros de 32 bits, se comprobará que la suma i+j provocará desbordamiento para valores de n relativamente bajos (del orden de 50). Así el cálculo de un término n mayor que 50 de la serie de Fibonacci obliga a operar con enteros de más precisión. De hecho para calcular un término del orden de 10000 de la serie de Fibonacci sería necesario almacenar enteros de miles de dígitos. Por tanto la operación de suma deja de poder ser considerada una operación elemental para n no excesivamente grande y será una operación que dependerá del tamaño del problema.
Este ejemplo se presenta simplemente como ilustracción de la necesidad de evaluar con cuidado cuándo una operación se puede considerar de coste constante.
4) Comentarios sobre el algoritmo "quicksort"
Uno de los algoritmos avanzados para ordenamiento de vectores es el conocido como método rápido, de Hoare o "quicksort". Este método se presenta en el apartado 4.4 de Peña, 1ª Edición. También se pueden estudiar las versiones recursiva e iterativa y un análisis del coste en el texto de Niklaus Wirth (padre de Pascal y Modula 2): "Algoritmos + Estructuras de Datos=Programas", publicado por Ediciones del Castillo. Los algoritmos de ordenación de vectores se pueden clasificar en dos grupos:
a) Los simples: Insercción, Selección, Intercambio o "burbuja"... De coste cuadrático, n.n
b) Los avanzados: Shell, Montículo o "Heapsort", Rápido o "Quicksort"... De orden n.log n
Si se realiza un análisis para caso peor del "Quicksort" se obtiene coste cuadrático. Sin embargo al aplicarlo sobre la mayoría de los vectores el coste es de orden n.log n . De hecho es uno de los algoritmos de ordenación más rápidos conocidos. La explicación radica en que en este caso no es apropiado estudiar coste para el caso peor, ya que un vector con contenido de datos que den lugar al caso peor será muy improbable si se elige el pivote de comparación del algoritmo de forma apropiada. Es, por tanto, más importante su comportamiento en el caso promedio.
Este ejemplo se incluye como ilustración de un caso en el que el análisis de caso peor no es el más apropiado.