Analisis Asintoticos de Algoritmos
Ministerio del Poder popular para la Educación
Universidad Jose Antonio Paez
Facultad: Ingeniera de computación
Catedra: Algoritmos y Estructuras II1. Realice un Mapa mental que haga síntesis delanálisisasintótico de un algoritmo:
Anexo al final del trabajo.
2. En que se relaciona el Síntesis del AnálisisAsintótico de Algoritmos con la Complejidad Computacional?
La complejidad Computacional indica el esfuerzo que hay que realizar para aplicar un algoritmo y lo costoso que este resulta, dicho coste, sepuede medir de diversas formas (espacio de memoria, tiempo, tipo de pasos, cantidad de unidades de procesamiento)
El Análisis Asintótico consiste en el cálculo de la complejidad temporal de unalgoritmo en función del tamaño del problema, prescindiendo de factores constantes multiplicativos y suponiendo valores de n muy grandes. No sirve para establecer el tiempo exacto de ejecución, sino quepermite especificar una cota (inferior, superior o amabas) para el tiempo de ejecución de un algoritmo.
Se podría decir que la teoría de la Complejidad Computacional se centra en la clasificación de losproblemas computacionales de acuerdo a su dificultad, introduciendo modelos matemáticos para el estudio de estos problemas y la cuantificación de la cantidad de recursos necesarios para resolverlos,por lo tanto, el análisis de algoritmos es parte importante de la teoría de complejidad ya que, provee estimaciones teóricas para los recursos que necesita cualquier algoritmo que resuelva unproblema dado. Estimaciones que resultan ser bastante útiles en la búsqueda de algoritmos eficientes.
Al momento de realizar un análisis teórico de algoritmos es común calcular su complejidad en unsentido 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....
Regístrate para leer el documento completo.