Bitacora

INSTITUTO TECNOLÓGICO DE TUXTLA GUTIÉRREZ

INGENIERÍA EN SISTEMAS COMPUTACIONALES

ESTRUCTURA DE DATOS

“ANÁLISIS DE ALGORITMOS”

Aguilar Avendaño Carlo Yovani
Gómez Pérez Alexis Mauricio
Gutiérrez Arias Gabriel
Rodríguez González Ediberto
Sánchez López Antonio
Vázquez Cruz José pablo

Tuxtla Gutiérrez, Chiapas
septiembre de 2011.

REPORTE ANÁLISIS DE ALGORITMOS

Definiciónde algoritmo

Como tema principal debemos de mencionar el concepto de algoritmo como sabemos es un conjunto de reglas finitas bien definidas que siguen una secuencia la cual sirve para resolver diferentes problemas. En palabras más entendibles es el conjunto de pasos a seguir que nos permite obtener a solución a un problema. Los algoritmos deben de contar con las siguientes características:* Entradas y salidas: un algoritmo siempre tendrá la entrada y salidas de datos.
* Finitud: todo algoritmo debe acabar en un determinado número de pasos.
* Efectividad: se entiende por esto que una persona sea capaz de realizar el algoritmo de modo exacto y sin ayuda de una maquina en un lapso de tiempo finito.
* Definibilidad: todo algoritmo debe de definirse de forma clara paracada paso, es decir, haya que evitar toda ambigüedad al definir cada paso.

Complejidad algorítmica
Un algoritmo siempre será más eficiente comparado con otro, siempre que consuma los mínimos recursos posibles, como el tiempo y espacio de memoria necesarios para ejecutarlo.
La eficiencia de un algoritmo puede ser cuantificada con las siguientes medidas de complejidad:
Complejidad Temporal oTiempo de ejecución:  Este punto se refiere al tiempo de necesario para que la computadora pueda ejecutar algún programa.
Complejidad Espacial: Es la 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.
Este análisis se basa en las Complejidades Temporales, con este fin, para cada problema determinaremos una medida N, que llamaremos tamaño de la entrada onúmero de datos a procesar por el programa, intentaremos hallar respuestas en función de dicha N.
El concepto exacto que cuantifica N 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 número de elementos que la componen; para un grafo, podría ser el número de nodos o arcos que lo arman, no se puede establecer una reglapara N, pues cada problema acarrea su propia lógica y complejidad.

Tabla de tipos de complejidad algorítmica

Aritmética de la notación O
La notación O (también llamada O mayúscula), se utiliza para comparar la eficiencia de los algoritmos.
La notación O-grande ignora los factores constantes, es decir, ignora si se hace una mejor o peor implementación del algoritmo, además de serindependiente de los datos de entrada del algoritmo. Es decir, la utilidad de aplicar esta notación a un algoritmo es encontrar un límite superior del tiempo de ejecución, es decir, el peor caso

Las operaciones elementales son:

  * Las operaciones aritméticas básicas: ( +, -, *, /)
  * Asignación a variables 
  * Los saltos: llamadas a funciones, procedimientos, retornos, ciclos.
  * Lascomparaciones y operaciones lógicas: > < = and or not 
  * Acceso a vectores y matrices 

Tiempo de Ejecución de un Algoritmo

* El tiempo de ejecución de un algoritmo, es prioritario cuando este es analizado.
* El tiempo de ejecución de un algoritmo o estructura de datos depende de varios factores relativos al hardware (procesador, reloj, memoria, disco, etc.) y el software...