Unidad 7 Analisis de algoritmos

15/03/2015

INSTITUTO TECNOLÓGICO
DE VERACRUZ

Estructura de Datos
Unidad VII: Análisis de algoritmos
Alumna: Jazmín A. Carrasco Cruz
No Control. E14020226
Clase: 14:00 – 15:00 hrs
Profesor: Luis Bernardo Ballesteros Barradas

Introducción
El presente trabajo contiene el análisis de los conceptos de Complejidad, de Tiempo, de Espacio,
y de igual modo hablaremos de la Evaluación y Selección deAlgoritmos.
¿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á más 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 esaquella función que da el tiempo de y/o el
espacio utilizado por el algoritmo en función del tamaño de la entrada.
El objetivo principal es conocer cómo trabaja el algoritmo y su estrecha relación con la
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
dedatos 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.
También encontrarán la eficiencia con la que trabaja un algoritmo ya que estos puedenser
cuantificados 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 todaslas 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, quellamaremos tamaño de la entrada o número de datos a
procesar por el programa, intentaremos hallar respuestas en función de dicha N.
Durante la investigación, uno de los obstáculo es el ¿Qué pasaría 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 número de elementosque la
componen; para un grafo, podría ser el número de nodos o arcos que lo arman, no se puede
establecer una regla para N, pues cada problema acarrea su propia lógica y complejidad.

2

Índice

UNIDAD 7: ANÁLISIS DE LOS ALGORITMOS

7.1 Concepto de complejidad de los algoritmos (Aritmética de a notación Ø)………pág. 4

7.2 Complejidad en el tiempo…………………………………………………………………………….…..pág. 7

7.3Complejidad en el espacio…………………………………………………………………………..……pág. 9

7.4 Evaluación y selección de los algoritmos eficientes………………………….……………….pág.11

Conclusión.………………………………………………………………………………………………………..…….pág. 13

Bibliografía………………………………………………………………………………………………………..……..pág.14

3

7.1 CONCEPTO DE COMPLEJIDAD DE ALGORITMOS
(ARITMÉTICA DE LA NOTACIÓN Ø)
Antes de empezar, hay que comenzar por entender losconceptos básicos, que a
continuación se muestran:


¿Qué es Complejidad?
Complejidad es la cualidad de lo que está compuesto en diversos elementos. En
términos generales, la complejidad tiende a ser utilizada para caracterizar algo
con muchas partes que forman un conjunto intrincado y difícil de comprender.
Esto quiere decir que le complejidad es algo “Difícil” en cualquier tema o ámbito
y por lo...