fuykjhjhkj



UNIVERSIDAD AUTÓNOMA DE NUEVO LEÓN

Facultad de Ingeniería Mecánica Eléctrica


ALGORITMOS COMPUTACIONALES
ACTIVIDAD 3.-
*TECNICAS DE ANALISIS DE ALGORITMOS
*NOTACION ASINTOTICA
*EFICIENCIA DE ALGORITMOS COMPUTACIONALES


Reyna Samaniego Alpha Michelle 1527630



N.A. Jessica Martínez
Jueves, Hora:M1,M2,M3
Salón:2-202




San Nicolás de los Garza, Nuevo León a 14 de Febrero de 2013




Introducción
En las Ciencias de la Computación cuando se dice que un problema tiene solución, significa que existe un algoritmo susceptible de implantarse en una computadora, capaz de producir la respuesta correcta para cualquier instancia del problema en cuestión.
Para ciertos problemas es posible encontrarmás de un algoritmo capaz de resolverlos, lo cual nos enfrenta al problema de escoger alguno de ellos. La tarea de decidir cuál de ellos es el mejor debe basarse en criterios acordes a nuestros intereses.
El Análisis de Algoritmos tiene como objetivo describir de manera muy precisa y detallada la eficiencia de algoritmo.
La importancia del análisis asintótico se encuentra en la combinación deelementos con formalidad matemática y la capacidad de analizar resultados sin considerar todos los elementos.



















Análisis de Algoritmos:

La resolución práctica de un problema exige por una parte un algoritmo o método de resolución y por otra un programa o codificación de aquel en un ordenador real. Ambos componentes tienen su importancia; pero la delalgoritmo es absolutamente esencial, mientras que la codificación puede muchas veces pasar a nivel de anécdota.
A efectos prácticos o ingenieriles, nos deben preocupar los recursos físicos necesarios para que un programa se ejecute. Aunque puede haber muchos parametros, los mas usuales son el tiempo de ejecución y la cantidad de memoria (espacio).
La función complejidad, f(n); donde n es el tamaño delproblema, da una medida de la cantidad de recursos que un algoritmo necesitará al implantarse y ejecutarse en alguna computadora. Puesto que la cantidad de recursos que consume un algoritmo crece conforme el tamaño del problema se incrementa.

La memoria y el tiempo de procesador son los recursos sobre los cuales se concentra todo el interés en el análisis de un algoritmo, así pues distinguiremosdos clases de función complejidad:
a) Función complejidad espacial. Mide la cantidad de memoria que necesitará un algoritmo para resolver un problema de tamaño n.
b) Función complejidad temporal. Indica la cantidad de tiempo que requiere un algoritmo para resolver un problema de tamaño n; viene a ser una medida de la cantidad de CPU que requiere el algoritmo.
La cantidad de memoria queutiliza un algoritmo depende de la implantación, no obstante, es posible obtener una medida del espacio necesario con la sola inspección del algoritmo. Para obtener esta cantidad es necesario sumar todas las celdas de memoria que utiliza. En general se requerirán dos tipos de celdas de memoria:
a) Celdas estáticas. Son las que se utilizan en todo el tiempo que dura la ejecución del programa, porejemplo, las variables globales.
b) Celdas dinámicas. Se emplean sólo durante un momento de la ejecución, y por tanto pueden ser asignadas y devueltas conforme se ejecuta el algoritmo, por ejemplo, el espacio de la pila utilizado por las llamadas recursivas.



Notación Asintótica
A la hora de analizar un algoritmo nos interesa, principalmente, la forma en que se comporta el algoritmo al aumentarel tamaño de los datos; es decir, cómo aumenta su tiempo de ejecución. Esto se conoce como eficiencia asintótica de un algoritmo y nos permitirá comparar distintos algoritmos puesto que deberíamos elegir aquellos que se comportarán mejor al crecer los datos. La notación asintótica se describe por medio de una función cuyo dominio es el conjunto de números naturales, N. Se describe la notación O...