Resumen Algoritmos y estructura de datos I mod1 PDF

Preview

Summary

Algoritmos y Tiempos de Algoritmos algoritmo al conjunto finito y ordenado de acciones con las que podemos resolver un determinado problema. Llamamos problema a una que se nos presenta y que, mediante la de un algoritmo, pretendemos Cuando se tienen algoritmos distintos que resuelven un mismo proble...

Description

Algoritmos y Tiempos de Ejecución Algoritmos “Llamamos algoritmo al conjunto finito y ordenado de acciones con las que podemos resolver un determinado problema. Llamamos problema a una situación que se nos presenta y que, mediante la aplicación de un algoritmo, pretendemos resolver” Cuando se tienen algoritmos distintos que resuelven un mismo problema de maneras distintas, se dice que dichos algoritmos son equivalentes. En el ámbito informático, cuando se habla de algoritmos, se está haciendo referencia al conjunto de acciones que debe seguir una computadora para resolver un problema.

Diseño de algoritmos Para poder diseñar correctamente un algoritmo, es necesario conocer su contexto, de manera que se tenga claro su alcance, sus datos de entrada y sus salidas. Para diseñar los algoritmos, también se cuenta con 3 recursos principalmente: memoria, operaciones aritméticas y operaciones lógicas.

Análisis de algoritmos A la hora de elegir un algoritmo para programar la funcionalidad de una aplicación, se tendrán que tener en cuenta parámetros tales como el hardware sobre el que se ejecutará dicha aplicación, la cantidad de datos que procesará y los tiempos de ejecución esperados por el tipo de usuario al que está destinada. Entonces, se vuelve indispensable encontrar formas de analizar los algoritmos para poder determinar su eficiencia. Para ello, se analiza el comportamiento de los algoritmos en forma matemática. Si se sacan otros factores como la velocidad, la cantidad de procesadores, la calidad del compilador y la cantidad y la velocidad de la memoria, entre otros, el tiempo de ejecución de un algoritmo es una función de la cantidad de los datos de entrada que deben procesar. A mayor cantidad de datos, mayor será el tiempo de ejecución, por lo que se utilizan funciones matemáticas para caracterizar la eficiencia de los algoritmos. Un algoritmo lineal es aquel que tiene un tiempo de ejecución que responde a una función lineal. Es el más eficiente. Sin embargo, existen algoritmos no lineales con tiempos de ejecución mucho más elevados. Las funciones más comúnmente encontradas en el análisis de algoritmos son las siguientes, ordenadas de mayor a menor eficiencia: Lineal: el tiempo de ejecución se incrementa a la misma velocidad en que se incrementa la cantidad de datos de entrada. O sea, son directamente proporcionales a la cantidad de datos de entrada a los que se someten. Es por esto que es el tipo de algoritmo más eficiente.  N * log (N): el logaritmo es una función que crece lentamente. Aunque crece más rápido que la función lineal, es más lenta que la cuadrática y la cúbica. El tiempo de ejecución en estos algoritmos es N veces el logaritmo de N, siendo N el tamaño de la entrada.

Cuadrática: el tiempo de ejecución está definido por una función cuadrática (por ejemplo, 3N2+2N +3) siendo N el tamaño de la entrada. Los algoritmos de este tipo son menos eficientes que los del tipo N*Log(N). Cúbica: el tiempo de ejecución está definido por una función cúbica (por ejemplo, 4N3+3N2+2N +3) siendo N el tamaño de la entrada. Están entre los menos eficientes, ya que ante pequeños incrementos en el tamaño de los datos, el tiempo de ejecución del algoritmo crece rápidamente. Pueden darse casos en que, por las constantes implicadas, una función N*Log(N) sea más eficiente que una lineal. Sin embargo, ante una misma complejidad, las lineales son más eficientes. Distinto es el caso de los algoritmos cuadráticos que tienen altos tiempos de ejecución, a partir de un tamaño de entrada de unos pocos miles. Peor aún, en el caso de los algoritmos cúbicos que tienen tiempos de ejecución lentos, a partir de un tamaño de entrada de unos pocos cientos. Normalmente, el tiempo de ejecución se ve afectado cuando el tamaño de la entrada es grande. Por esto, es en las grandes cantidades de entradas donde preocupa más la eficiencia del algoritmo. Cabe aclarar que, cuando se está ante la presencia de entradas pequeñas, la tasa de crecimiento puede no llegar a ser del todo importante. Incluso,puede suceder que una función con una tasa de crecimiento mayor que otra función sea más eficiente. De todas maneras, se podrá usar una u otra función sin notar mucha diferencia entre ellas. Pero, esto no es lo que suele suceder. Es por esto que la optimización del algoritmo es la tarea principal a la hora de hacer que un código se ejecute en forma eficiente, es decir, diseñar un buen algoritmo desde un principio. No importa qué tanto se optimice el código. La optimización debe realizarse primeramente sobre el algoritmo, porque es él quien define la eficiencia en la ejecución.

Notación O y Análisis Cota superior asintótica Cota superior asintótica es otra manera de nombrar a la notación O. No interesa tanto el tiempo exacto que demanda la ejecución de un algoritmo. Lo que interesa es cuánto aumenta el tiempo de ejecución demandado por un algoritmo, a medida que aumenta la cantidad de entradas. Lo que se busca es garantizar que el tiempo de ejecución de un algoritmo siempre será menor a una cota o límite superior. Con esto, se sabrá que, en el peor de los casos, este algoritmo tendrá un tiempo de ejecución que será proporcional a la función lineal N. Lo importante en este tipo de análisis es poder encontrar una función que acote el crecimiento que, en el peor de los casos, tendrá la complejidad del algoritmo.

Al conjunto de funciones que acotan dicho crecimiento lo llamamos O(g(x)) donde x representa la cantidad de elementos que se van a procesar y g(x) es cualquier cota superior de la función de complejidad del algoritmo. Más formalmente, lo planteamos de la siguiente manera: sea f(x) la función que expresa la complejidad de un algoritmo, entonces la expresión f(x) pertenece a O(g(x)), significa que f(x) crece, a lo sumo, tan rápido como cualquiera de las funciones g del conjunto O. Se usará la O mayúscula para denotar aquella función que indique el límite superior de crecimiento de una función. En un ejemplo lineal, Se dirá que el algoritmo tiene un tiempo de ejecución del orden de la función lineal denotado como O(N). Esto es conocido como notación O mayúscula o big O. Es evidente notar que el orden será definido por el término más importante de la función. Esto significa que, ante distintas funciones, se hará énfasis en el término que le da el grado a la función analizada. Este término es el más dominante y representa la tasa de crecimiento que interesa analizar. Cota inferior asintótica y cota ajustada asintótica Es útil, a veces, conocer el límite inferior, es decir, el mejor de los casos. Asimismo, se puede querer expresar que una función tiene la misma tasa de crecimiento que otra. Entonces, se encuentra la notación  (g(x)) para denotar una cota inferior asintótica, donde se indica que una función g(x) crecerá más lento o, a lo sumo, tan rápido como f(x). Esto quiere decir que dicho algoritmo analizado no se comportará mejor que una función. En otras palabras, el tiempo de ejecución será siempre mayor o, a lo sumo, igual que el de esa función. También, se encuentra la notación (g(x)) para denotar una cota ajustada asintótica. Por esto, si se dice que una función f(x) es  (g(x)), significa que la función f(x) tendrá la misma tasa de crecimiento que g(x).

Logaritmos Los logaritmos son operaciones en las que, dado un número real positivo a y una base b, permiten calcular el exponente c de la potencia. En la práctica, en el ámbito de la informática, se usan siempre logaritmos de base 2, comúnmente conocidos como logaritmos binarios. Esto es posible debido a que la base no condiciona la capacidad de cálculo de un logaritmo de cualquier base. En el caso de tener un logaritmo con una base b cualquiera, se puede traducirla a un logaritmo binario: Una función logarítmica es de importancia en el ámbito informático puesto que Esta se caracteriza por crecer lentamente y es un orden deseable de conseguir en la práctica, siempre que se pueda, debido a que, ante valores de n grandes, la función no diverge mucho. En comparación con la función logarítmica, la tasa de crecimiento de una función lineal es proporcional a la cantidad de datos de entrada. Es decir, si se ingresa el doble de datos, el tiempo de ejecución se duplica también. Una función logarítmica no se verá muy afectada ante una duplicación de los datos de entrada y es ahí donde radica su importancia.

existen algoritmos que presentan un comportamiento logarítmico cuando se analiza su tiempo de ejecución. Pero también existen otras funciones que se componen de un logaritmo. Una función común de encontrar en el orden del tiempo de ejecución de un algoritmo es 0(n*Log(n)). Los algoritmos de este orden se utilizan para resolver problemas, a través de su división en problemas más pequeños. Tal es el caso de los algoritmos de ordenamiento conocidos como Heapsort y Quicksort. La tasa de crecimiento que ofrecen no es tan buena como la de orden logarítmico O(Log(n)) y mantienen un rendimiento similar a los algoritmos de orden lineal O(n).

Búsqueda estática En el ámbito del software, una de las tareas más recurrentes es la que corresponde a la búsqueda. En la mayoría de los casos, el proceso de búsqueda se efectúa sobre una estructura ya ordenada, para obtener un buen rendimiento. Pero, también puede realizarse sobre estructuras desordenadas. Además, en general, se asume que el elemento que se quiere encontrar, existe. A su vez, existen distintos tipos de procesos de búsqueda, lo cual da por resultado una extensa clasificación. Una forma de clasificación corresponde a la distinción entre búsqueda estática en contraposición a la búsqueda dinámica. La búsqueda dinámica es aquel proceso de búsqueda efectuado sobre una estructura cuyo contenido puede ser alterado a lo largo del tiempo. Esto significa que un elemento podría ser modificado o incluso eliminado. Además también podría tener incorporaciones de nuevos elementos. La búsqueda estática es aquel proceso de búsqueda efectuado sobre una estructura cuyo contenido no se altera a lo largo del tiempo, es decir, se mantienen estáticos Esto implica, también, que no se presentarán inserciones con nuevos elementos o eliminaciones. Por esto, no será necesario tener en cuenta el tiempo insumido en ordenar la estructura posterior a la inserción o eliminación.

Métodos Algoritmo de búsqueda secuencial Es un método que consiste en comparar cada elemento de una estructura con el elemento que se quiere encontrar. Esto supone que no es necesario tener una estructura ordenada. Es evidente que, al tener que transitar por todos los elementos, es poco eficiente. Además, este algoritmo puede terminar en dos estados: con éxito (se encontró el elemento buscado) o sin éxito (no se localizó el elemento buscado). De todas maneras, la mayoría de los algoritmos de búsqueda se basan en él. En el peor de los casos, se tendrá que transitar por todos los elementos, hasta llegar al último. Por lo tanto, es de orden lineal O(n). Esto sucede tanto en un caso exitoso (cuando el elemento buscado se encuentra y está en la última posición), como en un caso sin éxito (cuando no se logra encontrar al elemento buscado y se tuvo que recorrer a toda la estructura). Algoritmo de búsqueda binaria Este algoritmo parte de una estructura que está ordenada. Es un algoritmo mucho más eficiente debido a que va subdividiendo la estructura en mitades, hasta lograr encontrar al elemento buscado o evidenciar que dicho elemento no se encuentra. Este método está basado en la técnica divide y vencerás. El procedimiento del algoritmo es bastante sencillo y consta de los siguientes pasos, si asumimos que la estructura está ordenada de menor a mayor: 1) Se comienza el proceso en el elemento central de la estructura (en caso de que la cantidad de elementos sea impar) o casi central (en caso de que la cantidad de elementos sea par). Es decir, se divide a la estructura en dos mitades. 2) Se verifica si el

elemento buscado corresponde al elemento central, en cuyo caso finaliza el proceso. En caso contrario, se valida si el elemento a buscar es mayor o menor a dicho elemento. Si el elemento a buscar es de mayor valor que el elemento central, se descarta la primera mitad. Si el elemento a buscar es de menor valor que el elemento central, se descarta la segunda mitad. 3) Con la mitad no descartada, se comienza el proceso de nuevo, desde el primer paso. Se repite este proceso de manera sucesiva hasta encontrar al elemento buscado o hasta que no se pueda subdividir más la estructura, en cuyo caso se concluye que el elemento buscado no se encuentra. Programáticamente, este algoritmo se resuelve inicialmente teniendo referencias a los extremos y el centro de la estructura. el método responde a un algoritmo de orden O(n*Log(n)). En presencia de valores de n grandes, este método tiene una eficiencia bastante mayor que la búsqueda secuencial. Sin embargo, si se tiene una estructura con una cantidad de elementos n pequeña, este método no es del todo adecuado. Esto se debe a que, por un lado, es complicado de ser codificado y, por otro, frente a un n pequeño, se asemejará a un método secuencial. Por esto, se suelen sugerir estrategias híbridas, donde se aplica el método binario cuando la estructura tiene una dimensión grande y, luego de obtener una estructura de menor tamaño, se procede a cambiar de método usando el algoritmo secuencial. Búsqueda por interpolación La búsqueda por interpolación es una alternativa cuando se presentan ciertas situaciones particulares y ofrece, en promedio, un tiempo de ejecución mejor. Sin embargo, en el peor de los casos, ofrecen un tiempo de ejecución bastante peor que el de la búsqueda binaria. Por lo tanto, es importante detectar cuándo es realmente ventajoso aplicar este método. Los casos donde se recomienda aplicar este algoritmo son:  Cuando acceder al elemento buscado es muy costoso: el acceso a un elemento que se encuentra en la memoria es algo muy rápido. Pero, cuando se debe acceder a un elemento que está almacenado en un disco, el acceso se vuelve una tarea costosa, que demanda tiempo y recursos.  Cuando los elementos están ordenados según una distribución uniforme. Este método se basa en analizar el problema, para realizar una estimación que permita, desde un principio, determinar dónde está localizado el elemento que se quiere encontrar. En el método de búsqueda binaria, en cada iteración, se toma el valor central, mientras que en la búsqueda por interpolación, se toma de referencia un valor que corresponde a la valuación de una fórmula mucho más compleja. Si bien el cálculo de este valor complejiza el proceso y enlentece cada iteración, ocurre que en muchos casos es insignificante comparado con el costo de tener que acceder a un elemento. En el peor de los casos, cuando los elementos de la estructura no responden a una distribución uniforme, este método puede tener un tiempo de ejecución lineal. Pero, si se tiene una estructura con distribución uniforme o, al menos, están distribuidos de una manera bastante uniforme, se puede obtener un promedio de comparaciones de O(n*Log(Log(n))). Esta expresión contiene la operación de logaritmo dos veces, una vez más que en la búsqueda binaria, lo cual permite una reducción de las iteraciones considerable....