PDF de programación - Técnicas de análisis de algoritmos

Técnicas de análisis
de algoritmos

¿Qué es un buen algoritmo? No es fácil responder a esta pregunta. Muchos criterios
para un buen algoritmo incluyen cuestiones muy subjetivas como simplicidad, cla-
ridad y adecuación a los datos manejados. Una meta más objetiva, lo cual no signi-
fica que sea más importante, es la eficiencia en tiempo de ejecución. En la sección 1.5
se abordaron las técnicas básicas para establecer el tiempo de ejecución de progra-
mas simples. Sin embargo, en casos más complejos se requieren técnicas nuevas,
como cuando los programas son recursivos. Este corto capitulo presenta algunas
técnicas generales para resolver ecuaciones de recurrencia que se presentan en el aná-
lisis de los tiempos de ejecución de algoritmos recursivos.

9.1 Eficiencia de los algoritmos

Una forma de determinar la eficiencia del tiempo de ejecución de un algoritmo es
programarlo y medir el tiempo que lleva la versión en particular, en un computador
especifico, para un conjunto seleccionado de entradas. Aunque es popular y útil,
este enfoque tiene algunos problemas inherentes. Los tiempos de ejecución depen-
den no sólo del algoritmo base, sino tambikn del conjunto de instmcciones del com-
putador, de la calidad del wmpilador y de la destreza del programador. El progra-
ma tambien puede adaptarse para trabajar correaamente sobre el conjunto particu-
lar de entradas de prueba. Estas dependencias pueden ser muy notorias con un com-
putador, un compilador, un programador o un conjunto de entradas de pmeba dis-
tinto. Para superar esos inconvenientes, los expertos en computación han adoptado
la complejidad de tiempo asintótica como una medida fundamental del rendimien-
to de un algoritmo. El termino eficiencia se referid a esta medida y, en especial, a
la complejidad de tiempo en el peor caso (en contraposición al promedio).

Recukrdense del capitulo 1 las definiciones de m n ) ) y R(An)). La eficiencia o
complejidad en el peor caso de un algoritmo es m n ) ) , o jln) para abreviar, si
W n ) ) es la función de n que da el máximo, en todas las entradas de longitud n,
del número de pasos dados por el algoritmo en esas entradas. En otras palabras, exis-
te alguna constante c tal que para una n suficientemente grande, cfln) es una cota
superior del número de pasos dados por el algoritn~o con cualquier entrada de lon-
gitud n.

En la aseveración de que d a eficiencia de un algoritmo dado esfln)», existe la
implicación de que la eficiencia tambien es R(An)), de forma quefln) es la función

Este material es proporcionado al estudiante con fines educativos, para la crítica y la investigación respetando la reglamentación en materia de derechos de autor.Aho, Alfred V., John E. Hopcroft y Ullman. (1998). Técnicas de análisis de algortimos.Este documento no tiene costo alguno. El uso indebido de este documento es responsabilidad del estudiante.En Estructuras de datos y algoritmos (pp. 293-306). México: Adisson Wesley Longman de México.294

TECNICAS DE ANALISIS DE ALGORITMOS

de crecimiento mAs lenta de n que acota el tiempo de ejecución en el peor caso por
amba. Sin embargo, este último requisito no es parte de la definición de O(fln)), y
algunas veces no es posible asegurar que se tenga la cota de crecimiento superior
más lenta.

Esta definición de eficiencia ignora factores constantes en el tiempo de ejecución
y existen varias razones prácticas para ello. Primero, dado que la mayoria de los al-
goritmo~ esten escritos en lenguajes de alto nivel, se deben describir en función de
«pasos», los cuales emplean una cantidad constante de tiempo cuando se traducen
al lenguaje de máquina de cualquier computador. Sin embargo, exactamente cuánto
tiempo requiere un paso depende no sólo del paso mismo, sino del proceso de tra-
ducción y del conjunto de instmcciones de la máquina. Asi, intentar tener más pre-
cisión que para decir que el tiempo de ejecución de un algoritmo es «del orden de
An)», esto es, OMn)), podria empantanar al usuario en detalles de máquinas espe-
cificas y sólo seria aplicable a esas máquinas.

Una segunda razón importante para tratar con la complejidad asintótica e igno-
rar factores constantes es que, más que estos factores, es la complejidad asintótica
lo que determina para qué tamaiio de entradas puede usarse el algoritmo para pro-
ducir soluciones en un computador. En el capitulo 1 se analizó con detalle este as-
pecto. Sin embargo, es necesario tener cautela acerca de la posibilidad de que para
problemas muy importantes, wmo los de clasificación, se pueda considerar adecua-
do analizar los algoritmos con tal detalle que sean factibles ciertas proposiciones
como «el algoritmo A debe ejecutarse con el doble de rapidez que el algoritmo B en
un computador tipico».

Una segunda situación en la cual conviene desviarse de la noción de eficiencia
en el peor caso ocurre cuando se conoce la distribución esperada de las entradas a
un algoritmo. En estas situaciones, el análisis del caso promedio puede ser mucho
más significativo que el análisis del peor caso. Por ejemplo, en el capitulo previo se
analizó el tiempo de ejecución promedio de la clasificación rápida en el supuesto de
que todas las permutaciones del orden de clasificación wrrecto tienen la misma pro-
babilidad de presentarse como entradas.

9.2 Anhlisb de programas recursivos

En el capitulo 1 se mostró cómo analizar el tiempo de ejecución de un programa que
no se llama a si mismo en forma recursiva. El análisis de un programa recursivo es
bastante distinto, y suele implicar la solución de una ecuación de diferencias. Las
tbcnicas para la solución de ecuaciones de diferencias algunas veces son sutiles, y tie-
nen una considerable semejanza w n los metodos de solución de ecuaciones diferen-
ciales, alguna de cuya terminologia se utiliza.

Considerese el programa de clasificación presentado en la figura 9.1. Ahi, el pro-
cedimiento mergesort (clasificación por intercalación) toma una lista de longitud n
como entrada, y devuelve una lista ordenada como salida. El procedimiento combi-
na(L,, L,) toma como entrada las listas clasificadas L, y L,, y recorre cada una, ele-
mento por elemento, desde el inicio. En cada paso, el mayor de los dos elementos

Este material es proporcionado al estudiante con fines educativos, para la crítica y la investigación respetando la reglamentación en materia de derechos de autor.Aho, Alfred V., John E. Hopcroft y Ullman. (1998). Técnicas de análisis de algortimos.Este documento no tiene costo alguno. El uso indebido de este documento es responsabilidad del estudiante.En Estructuras de datos y algoritmos (pp. 293-306). México: Adisson Wesley Longman de México.delanteros se borra de esta lista y se emite como salida. El resultado es una sola lista
clasificada w n los elementos de L, y L,. Los detalles de combina no tienen impor-
tancia alguna en este momento, puesto que este algoritmo de clasificación se anali-
zara con detalle en el capitulo 1 l . Lo que importa es que el tiempo empleado por
combina en listas de longitud n12 es q n ) .

fonction mergesorf ( L: LISTA, n: integer ) : LISTA;

1 L es una lista de longitud n. Se devuelve una versión clasificada de L.

Se supone que n es una potencia de 2.1

vlu

begin

L,, &: LIST

il n - 1 then

re-

(0

else begin

end

ead, { mergesori 1

panir L en dos mitades, L, y &, cada una de longitud nl2;
re-

(combina(mergesoML,,n/~, mergesori(L,,n/2)))

Flg. 9.1. Procedimiento recursivo mergesort.

Sea T(n) el tiempo de ejecución en el peor caso del procedimiento mergesort de
la figura 9.1. Se escribe una ecuación de recurrencia (o diferencias) que acote T(n)
por arriba, wmo sigue

El ttrmino c, en (9.1) representa el número constante de pasos dados cuando L tie-
ne longitud 1. En el caso de que n > 1, el tiempo requerido por mergesort puede di-
vidirse en dos partes. Las llamadas recursivas a mergesorf wn listas de longitud n12
cada una llevan un tiempo T(n/Z), de aquí el termino 2T(n/2). La segunda parte wn-
siste en la pmeba para descubrir que n + 1, la división de la lista L en dos partes
iguales y el procedimiento combina. Esas tres operaciones requieren un tiempo que
puede ser una constante, en el caso de la pmeba, o ser proporcional a n al dividir y
combinar. Así, la constante c, puede escogerse de modo que el término c,n sea una
wta superior del tiempo requerido por mergeson para hacer todo excepto las llama-
das recursivas. La ecuación (9.1) representa todo lo anterior.

Obsérvese que (9.1) se aplica sólo cuando n es par, por lo que generará una wta
superior en forma cerrada (esto es, wmo una fórmula para T(n) que no implica nin-
gún T(m) para m < n) sólo cuando n es una potencia de 2. Sin embargo, aunque
sólo se conozca T(n) cuando n es una potencia de 2, se tiene una buena idea de T(n)
para toda n. En particular, para casi todos los algoritmos, se puede suponer que T(n)
esta entre T(23 y T(2" l ) si n está entre 2' y 2"
l. Y con un poco mis de esfuerzo

Este material es proporcionado al estudiante con fines educativos, para la crítica y la investigación respetando la reglamentación en materia de derechos de autor.Aho, Alfred V., John E. Hopcroft y Ullman. (1998). Técnicas de análisis de algortimos.Este documento no tiene costo alguno. El uso indebido de este documento es responsabilidad del estudiante.En Estructuras de datos y algoritmos (pp. 293-306). México: Adisson Wesley Longman de México.para encontrar la solución, se puede reemplazar el término ZT(n12) de (9.1) por
T((n + 1)12) + T((n - 1)/2) para n > 1 impar. Despub, se podría resolver la nueva
ecuación de diferencia para obtener una solución cerrada para toda n.

9.3 Rmlucibn de ecuaciones de racuwncla
Existen tres enfoques distintos para resolver una ecuaci6n de recumncia.
1. Suponer una soluci6n n n )