1. No category

Estructuras de Datos 2016-10
Solución propuesta Taller 1
2.1 Factorial
1. La gráfica presenta el tiempo (en segundos) que tarda en ejecutarse la función recursiva para calcular
el factorial de un número (curva roja) y la función iterativa para calcular el factorial (curva verde),
utilizando un número creciente entre 0 y 160.
Al analizar la gráfica, lo que puede observarse es que tanto la curva roja como la curva verde presentan
el mismo comportamiento, lo que indicaría que ambas funciones tardan el mismo tiempo en ejecutarse.
El tiempo de ejecución es bastante pequeño, por lo que no alcanza a marcar valores diferentes de 0 en
la medición.
2. La complejidad teórica de los dos algoritmos presentados es O(n). En el caso de la función recursiva,
se hacen tantos llamados recursivos a la función como el número de entrada, por lo que la complejidad
es de orden lineal (O(n)). En el caso de la versión iterativa, el ciclo se ejecuta cerca de n+1 veces, lo
que también representa una complejidad de orden lineal (O(n)).
En relación con la evidencia experimental recopilada en la gráfica, ya se observó que los
comportamientos son similares, por lo que puede decirse que el método empírico corrobora en este
caso el análisis teórico. Ambas versiones (recursiva e iterativa) pueden utilizarse indistintamente, ya
que su complejidad es la misma y en tiempo de ejecución tardan el mismo tiempo, independientemente
de su longitud en términos de líneas de código.
3. Al calcular 170! se obtiene un valor de 7.25742e+306, pero al calcular el siguiente factorial, es
decir, 171!, se obtiene inf como resultado. Esto se debe al tipo de dato utilizado para almacenar el
resultado. En este caso, se está usando un double, que tiene un límite de representación hasta el valor
1.7E+/­308 (15 dígitos). El valor 170! alcanza a caer dentro de este rango de representación, pero el
factorial del siguiente número ya no alcanza a representarse utilizando ese tipo de dato.
2.2 Sort
1. La primera gráfica presenta el tiempo (en segundos) que tarda en ejecutarse el algoritmo de
ordenamiento en burbuja (bubblesort, curva roja), el algoritmo de ordenamiento rápido (quicksort,
curva verde) y el algoritmo de ordenamiento por montículos (heapsort, curva azul) sobre un arreglo de
datos aleatorios, de tamaño entre 500 y 40000.
La segunda gráfica presenta el tiempo (en segundos) que tarda en ejecutarse el algoritmo de
ordenamiento en burbuja (bubblesort, curva roja), el algoritmo de ordenamiento rápido (quicksort,
curva verde) y el algoritmo de ordenamiento por montículos (heapsort, curva azul), ahora sobre un
arreglo de datos ya ordenados, de tamaño entre 500 y 40000.
La última gráfica presenta el tiempo (en segundos) que tarda en ejecutarse el algoritmo de
ordenamiento en burbuja (bubblesort, curva roja), el algoritmo de ordenamiento rápido (quicksort,
curva verde) y el algoritmo de ordenamiento por montículos (heapsort, curva azul), ahora sobre un
arreglo de datos ordenados inversamente, de tamaño entre 500 y 40000.
De las tres gráficas puede observarse que el algoritmo de ordenamiento en burbuja (bubblesort) es el
que más tarda en ejecutarse en las tres configuraciones de las entradas. Para cuando los datos son
aleatorios, los algoritmos de ordenamiento rápido (quicksort) y por montículos (heapsort) tardan el
mismo tiempo de ejecución, sin embargo, cuando los datos están ordenados ascendente o
descendentemente, el algoritmo de ordenamiento rápido (quicksort) tiende a tomar mucho más tiempo
que el algoritmo de ordenamiento por montículos (heapsort). Con esto se puede decir que el algoritmo
de peor comportamento en tiempo es el bubblesort, mientras que el de mejor comportamiento en
tiempo es el heapsort. En arreglos de tamaño “pequeño”, hasta 10000 datos, las diferencias en tiempo
para los algoritmos son relativamente pequeñas, por lo que en esos casos podrían no ser necesariamente
críticas. Ya en arreglos de más tamaño, las diferencias empiezan a notarse entre los 3 algoritmos.
2. El algoritmo de ordenamiento en burbuja (bubblesort) presenta una complejidad teórica de O(n^2).
Esto es debido a que en el peor caso, debe hacer intercambios de cada uno de los datos con todos los
demás.1 La implementación permite evidenciar que se utiliza un primer ciclo para recorrer cada dato
del arreglo, y para cada uno de ellos, se utiliza un segundo ciclo para recorrer el resto de datos y revisar
si es necesario el intercambio. Como cada ciclo se hace sobre todos los datos, la complejidad de cada
ciclo es de O(n), y al estar anidados, su complejidad se multiplica, resultando en O(n^2).
El algoritmo de ordenamiento rápido (quicksort) presenta una complejidad teórica general de O(n log
n), aunque en algunos casos muy particulares puede tomar hasta O(n^2). 2 El algoritmo particiona el
arreglo en dos, y recursivamente ordena cada partición. El trabajar cada vez con la mitad del arreglo
implica un orden de complejidad de O(log n), pero además, en cada partición los datos se ordenan
haciendo intercambios, por lo que en cada intercambio se comparan todos los datos entre sí, llegando a
un orden de complejidad de O(n). La combinación de ambos procesos implica una multiplicación de
los órdenes de complejidad, resultando en O(n log n).
El algoritmo de ordenamiento por montículos (heapsort) presenta una complejidad teórica de O(n log
n).3 El procedimiento para el ordenamiento implica crear primero un montículo con los datos (árbol
binario con propiedad especial), y luego generar el arreglo ordenado a partir de la extracción controlada
de los elementos del montículo. El proceso de creación del montículo y su actualización a medida que
se van extrayendo los elementos para que se realice de manera ordenada implica un proceso de
complejidad O(n log n).
3. De acuerdo a la complejidad teórica de los algoritmos, y el tiempo de ejecución observado en la
experimentación, se puede decir que la evidencia experimental soporta correctamente los análisis
teóricos de complejidad. De acuerdo al análisis teórico, bubblesort es el de peor comportamento, con
complejidad O(n^2), y heapsort es el de mejor comportamiento, con complejidad O(n log n). La
complejidad de quicksort oscila entre esos dos valores, y la evidencia experimental permitió identificar
que dependiendo de la configuración de los datos de entrada quicksort puede ser muy rápido o puede
tardar tanto como bubblesort. En la experimentación, la curva de heapsort siempre se mantuvo muy
cerca al eje horizontal, siendo en todos los casos el mejor algoritmo. Y la curva de bubblesort siempre
fue la de mayor crecimiento, indicando que en las tres configuraciones es el que más tiempo tarda.
2.1 Lucas
1. La gráfica presenta el tiempo (en segundos) que tarda en ejecutarse la función recursiva para calcular
el número de Lucas (curva roja) y la función iterativa para calcular el número de Lucas (curva verde),
1
2
3
http://www.cs.nott.ac.uk/~psznza/G52ADS/simplesorts1.pdf
https://www.khanacademy.org/computing/computer-science/algorithms/quick-sort/a/analysis-of-quicksort
https://fmse.info.uaic.ro/getteachingfile/53/heap-comp.pdf
utilizando un número creciente entre 0 y 50.
Al analizar la gráfica, lo que puede observarse es que tanto la curva roja como la curva verde presentan
el mismo comportamiento hasta cerca del número de Lucas 38, lo que indicaría que ambas funciones
tardan el mismo tiempo en ejecutarse. Hasta ese punto, el tiempo de ejecución es bastante pequeño, por
lo que no alcanza a marcar valores diferentes de 0 en la medición. Sin embargo, a partir del número de
Lucas 39, la curva roja empieza a crecer rápidamente, mientras que la curva verde se mantiene cerca al
eje horizontal. De esta forma, el algoritmo recursivo tarda bastante más tiempo en generar el resultado
que el algoritmo iterativo.
2. La complejidad de los algoritmos para calcular el número de Lucas corresponde también a la
complejidad del cálculo de los números de Fibonacci, pues la estructura de los algoritmos es la misma,
sólo cambian los valores de inicialización. En el caso de la función recursiva, su complejidad está
acotada por O(2n), aunque para mayor exactitud se suele hablar de O(1.6n).4 Para calcular un número de
Lucas, se requiere tener el valor de dos números anteriores. Como para cada llamado el cálculo se
duplica, y estos llamados se hacen casi tantas veces como el valor del número de entrada, es por esto
que se define la complejidad como O(2n). En el caso de la versión iterativa, el ciclo se ejecuta cerca de
n-1 veces, lo que representa una complejidad de orden lineal (O(n)).
En relación con la evidencia experimental recopilada en la gráfica, se puede afirmar que la evidencia
experimental corrobora correctamente los análisis teóricos de complejidad. El crecimiento de la
función 2n es bastante poco al principio, pero luego tiene un crecimiento bastante acelerado, a
comparación de la tendencia de la función lineal. De esta forma, para algunos pocos números pequeños
es posible usar tanto la versión iterativa como la recursiva, pero en general es mejor utilizar la versión
iterativa, pues su complejidad en tiempo es menor. Esto es independiente de la cantidad de líneas de
código en la implementación de cada algoritmo, pues siempre la versión recursiva es más compacta.
4
http://stackoverflow.com/questions/360748/computational-complexity-of-fibonacci-sequence