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.

...