DIRECCIÓN GENERAL DE EDUCACIÓN SUPERIOR TECNOLÓGICA.

[pic 1] SECRETARÍA DE EDUCACIÓN PÚBLICA.[pic 2]

DIRECCIÓN GENERAL DE EDUCACIÓN SUPERIOR TECNOLÓGICA.

Instituto Tecnológico de Veracruz.

[pic 3]

Cano Caballero Alan G.

Núñez Romero Natalia A.

Vélez Reyes Mitzi Yoali

Estructura de Datos

Unidad 1

Luis Bernardo Ballesteros Barradas

13-14 hrs

H. Veracruz a 4 de Febrero de 2016

ÍNDICE

Índice de tablas y/o figuras ……………………………………………………………………………………….……….3

Introducción ………………………….………………………………………………………………………………….……….4

Análisis de los algoritmos …………………………………………………………………………………………………..5

1. Concepto de complejidad de los algoritmos (Aritmética de la notación O)
2. Complejidad en el Tiempo
3. Complejidad en el Espacio
4. Evaluación y selección de algoritmos

Conclusión ………………………………………………………………………………………………………………………11

Bibliografía ………………………………………………………………………………………………………………………12

ÍNDICE DE TABLAS Y/O FIGURAS

Grafica 1.1.1 Factor tiempo de ejecución de un algoritmo……………………………………………………5

Grafica 1.1.2 Definición de la notación O. la ficción f(n) es O(g(n)) para f(n)<=c*g(n) cuando n>=………………………………………………………………………………………………………………………………..…7[pic 4]

Tabla 1.1.1 Tipos de datos primitivos de Java…………………………………………………..…………………..9

INTRODUCCIÓN

El análisis de algoritmos es una parte importante de la Teoría de complejidad computacional más amplia, que provee estimaciones teóricas para los recursos que necesita cualquier algoritmo que resuelva un problema computacional dado. Estas estimaciones resultan ser bastante útiles en la búsqueda de algoritmos eficientes.

A la hora de realizar un análisis teórico de algoritmos es común calcular su complejidad en un sentido asintótico, es decir, para un tamaño de entrada suficientemente grande. La cota superior asintótica, y las notaciones omega (cota inferior) y theta (caso promedio) se usan con esa finalidad. Normalmente las estimaciones asintóticas se utilizan porque diferentes implementaciones del mismo algoritmo no tienen por qué tener la misma eficiencia. No obstante, la eficiencia de dos implementaciones "razonables" cualesquiera de un algoritmo dado están relacionadas por una constante multiplicativa llamada constante oculta.

La medida exacta (no asintótica) de la eficiencia a veces puede ser computada pero para ello suele hacer falta aceptar supuestos acerca de la implementación concreta del algoritmo, llamada modelo de computación. Un modelo de computación puede definirse en términos de un ordenador abstracto, como la Máquina de Turing, y/o postulando que ciertas operaciones se ejecutan en una unidad de tiempo.

Las medidas exactas de eficiencia son útiles para quienes verdaderamente implementan y usan algoritmos, porque tienen más precisión y así les permite saber cuánto tiempo pueden suponer que tomará la ejecución.

Las estimaciones de tiempo dependen de cómo definamos un paso. Para que el análisis tenga sentido, debemos garantizar que el tiempo requerido para realizar un paso se encuentre acotado superiormente por una constante. Hay que mantenerse precavido en este terreno; por ejemplo, algunos análisis cuentan con que la suma de dos números se hace en un paso. Este supuesto puede no estar garantizado en ciertos contextos.

ANALISIS DE LOS ALGORITMOS

1. Concepto de complejidad de algoritmos (aritmética de la notación O)

Algoritmo, 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á más eficiente comparado con otro, siempre que consuma menos recursos, como el tiempo y espacio de memoria necesarios para ejecutarlo. La complejidad de un algoritmo es aquella función que da el tiempo de y/o el espacio utilizado por el algoritmo en función del tamaño de la entrada.

Cada algoritmo guarda una estrecha relación con una estructura de datos. Por ello, no siempre es posible utilizar el algoritmo más eficiente, puesto que la elección 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 situación 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.

La eficiencia de un algoritmo puede ser cuantificada con las siguientes medidas de complejidad:

1. Complejidad Temporal o Tiempo de ejecución. Tiempo de cómputo necesario para ejecutar algún programa.
2. Complejidad Espacial. Memoria que utiliza un programa para su ejecución, 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 estática de un algoritmo se suma la memoria que ocupan las variables declaradas en el algoritmo. Para el caso de la memoria dinámica, el cálculo no es tan simple ya que, este depende de cada ejecución del algoritmo.

Una vez dispongamos de un algoritmo que funciona correctamente, es necesario definir criterios para medir su rendimiento o comportamiento. Estos criterios se centran principalmente en su simplicidad y en el uso eficiente de los recursos.  A menudo se piensa que un algoritmo sencillo no es muy eficiente. Sin embargo, la sencillez es una característica muy interesante a la hora de diseñar un algoritmo, pues facilita su verificación, el estudio de su eficiencia y su mantenimiento.

La complejidad de un algoritmo o complejidad computacional, estudia los recursos y esfuerzos requeridos durante el cálculo para resolver un problema los cuales se dividen en: tiempo de ejecución y espacio en memoria. El factor tiempo, por lo general es más 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 ejecución 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 gráficas:

[pic 5]

[pic 6]

Como se puede apreciar en las gráficas, entre mayor se al número de datos mayor tiempo se aplica en las gráficas a), b) y c), lo cual no ocurre con la gráfica d), por lo tanto, podemos deducir que una función que se acerque más al eje de las x es más constante y eficiente en el manejo de grandes cantidades de datos.

El análisis de algoritmo es una parte muy importante de la ciencia de la computación, de modo que la medida de la eficiencia de un algoritmo será uno de los factores fundamentales. Por consiguiente, es importante poder analizar los requisitos de tiempo y espacio de un algoritmo para ver si existe dentro de límites aceptables. Es difícil realizar un análisis simple de un algoritmo que determine la cantidad exacta de tiempo requerida para ejecutarlo. La primera complicación es que la cantidad exacta de tiempo dependerá de la implementación del algoritmo y de la maquina en que se ejecuta. El análisis normalmente debe ser independiente del lenguaje o máquina que se utilice para implementar el algoritmo. El análisis del algoritmo tratará de obtener el orden de magnitud de tiempo requerido para la ejecución del mismo y cada algoritmo tendrá un coste computacional diferente. La eficiencia es un criterio que se debe utilizar cuando se selecciona un algoritmo y su implementación. Existe al menos tres dificultades fundamentales que son los siguientes:

...