INSTITUTO TECNOLOGICO DE VERACRUZ

Estructura de Datos

Unidad VII: Anlisis de algoritmos

Alumno: Diaz Vzquez Sebastian Profesor: Ballesteros Barrados Luis BernardoINDICE

Introduccin------------------------------------------------------------------------------------------ 3

Concepto de complejidad de algoritmos--------------------------------------------------- 4Figura 1.1---------------------------------------------------------------------------------------------- 5

Aritmtica de la notacin O---------------------------------------------------------------------- 6Figura 1.2---------------------------------------------------------------------------------------------- 6

Complejidad en el tiempo------------------------------------------------------------------------ 8

Complejidad en el espacio--------------------------------------------------------------------- 10Tabla1------------------------------------------------------------------------------------------------- 10

Evaluacin y seleccin de algoritmos eficientes--------------------------------------- 12

Conclusin ----------------------------------------------------------------------------------------- 15

Bibliografa ----------------------------------------------------------------------------------------- 16

IntroduccinEl presente trabajo contiene el anlisis de los conceptos de Complejidad, de Tiempo, de Espacio, y de igual modo hablaremos de la Evaluacin y Seleccin de Algoritmos.Qu es un Algoritmo? Un Algoritmo, es el conjunto de pasos para resolver un problema, mientras que complejidad significa la cantidad de recursos que se utilizan para llegar a una meta.Un algoritmo ser ms eficiente comparado con otro, siempre que consuma menos recursos, como el tiempo y espacio de memoria necesarios para ejecutarlo.Por otro lado la complejidad de un algoritmo es aquella funcin que da el tiempo de y/o el espacio utilizado por el algoritmo en funcin del tamao de la entrada.El objetivo principal es conocer cmo trabaja el algoritmo y su estrecha relacin con la estructura de datos. Por ello, no siempre es posible utilizar el algoritmo ms eficiente, puesto que la eleccin de las estructuras de datos depende de varias cuestiones, incluida la de qu tipo de datos administramos y la frecuencia con que se realizan diferentes operaciones sobre ellos. As, deberemos encontrar una situacin compromiso entre tiempo y compromiso utilizados. En general, si aumentamos el espacio necesario para almacenar los datos, conseguiremos un mejor rendimiento en el tiempo y viceversa. Tambin encontrarn la eficiencia con la que trabaja un algoritmo ya que estos pueden ser cuantificados con las siguientes medidas de complejidad:1. Complejidad Temporal o Tiempo de ejecucin. Tiempo de cmputo necesario para ejecutar algn programa.2. Complejidad Espacial. Memoria que utiliza un programa para su ejecucin, La eficiencia en memoria de un algoritmo indica la cantidad de espacio requerido para ejecutar el algoritmo; es decir, el espacio en memoria que ocupan todas las variables propias al algoritmo. Para calcular la memoria esttica de un algoritmo se suma la memoria que ocupan las variables declaradas en el algoritmo. Para el caso de la memoria dinmica, el clculo no es tan simple ya que, este depende de cada ejecucin del algoritmo.Este anlisis se basa en las Complejidades Temporales, con este fin, para cada problema determinaremos una medida N, que llamaremos tamao de la entrada o nmero de datos a procesar por el programa, intentaremos hallar respuestas en funcin de dicha N.Durante la investigacin, uno de los obstculo es el Qu pasara si?. Si el algoritmo tiene varias modificaciones. Esto depender de la naturaleza del problema, si hablamos de un array se puede ver a N como el rango del array, para una matriz, el nmero de elementos que la componen; para un grafo, podra ser el nmero de nodos o arcos que lo arman, no se puede establecer una regla para N, pues cada problema acarrea su propia lgica y complejidad.

Concepto de complejidad de algoritmos.

La mayora de los problemas que se plantean en la actualidad se pueden resolver con algoritmos que difieren en su eficiencia. Dicha diferencia puede ser irrelevante cuando el nmero de datos es pequeo pero cuando la cantidad de datos es mayor la diferencia crece. Ejemplo: Suma de 4 y 10 primero nmeros naturales.

1+2+3+4 = 101+2+3+4+5+6+7+8+9+10 = 553 3tiempo9 34*(4+1)/2 = 1010*(10+1)/2 = 55

La complejidad de un algoritmo o complejidad computacional, estudia los recursos y esfuerzos requeridos durante el clculo para resolver un problema los cuales se dividen en: tiempo de ejecucin y espacio en memoria. El factor tiempo, por lo general es ms importante que el factor espacio, pero existen algoritmos que ofrecen el peor de los casos en un menor tiempo que el mejor de los casos, lo cual no es la mejor de las soluciones.El factor tiempo de ejecucin de un algoritmo depende de la cantidad de datos que se quieren procesar, una forma de apreciar esto es con las cuatro curvas que se presentan en las grficas de la figura 1.1.

Como se puede apreciar en las grficas, entre mayor se al nmero de datos mayor tiempo se aplica en las grficas a), b) y c), lo cual no ocurre con la grfica d), por lo tanto podemos deducir que una funcin que se acerque ms al eje de las x es ms constante y eficiente en el manejo de grandes cantidades de datos.

Aritmtica de la notacin O.

La notacin asinttica O (grande) se utiliza para hacer referencia a la velocidad de crecimiento de los valores de una funcin, es decir, su utilidad radica en encontrar un lmite superior del tiempo de ejecucin de un algoritmo buscando el peor caso.La definicin de esta notacin es la siguiente: f(n) y g(n) funciones que representan enteros no negativos a nmeros reales. Se dice que f(n) es O(g(n)) si y solo si hay una constante real c>0 y un entero constante n0>=1 tal que f(n)= n0. Esta definicin se ilustra en la figura 1.2.

Nota: el orden de magnitud de una funcin es el orden del trmino de la funcin ms grande respecto de n. La notacin asinttica O grande se utiliza para especificar una cota inferior para la velocidad de crecimiento de T(n), y significa que existe una constante c tal que T(n) es mayor o igual a c(g(n)) para un nmero infinito de valores n.

Regla para la notacin ODefinicin (O)T(n) es O(f(n)) si existen las constantes positivas c y n0 tales que n >= n0 se verifica T(n)