ANALISIS ASINTOTICO DE ALGORITMOS

En matemáticas puras y aplicadas, en particular el análisis de algoritmos, el análisis asintótico es un método de descripción de la limitación de comportamiento. Limitar el comportamiento se expresa en el lenguaje de las relaciones de equivalencia. Además, el análisis asintótico se refiere a la solución de problemas aproximadamente hasta tales equivalencias. Por ejemplo, dado funciones de valor complejos f y g de una variable de número natural n, una forma escrita seria.

y otra mas comun seria

lim f(n)/g(n) = 1
n->∞

y f y g son llamados equivalente asintóticamente cuando n → ∞. Esto define una relación de equivalencia (en el conjunto de funciones distinto de cero para todos los n suficientemente grandes - la mayoría de los matemáticos prefieren la definición

en cuanto a la notación de Landau, que evita esta limitación). La clase de equivalencia de f consta de todas las funciones g que "se comportan como" f, en el límite.

Análisis Matemático de Algoritmos
Consiste en tratar de asociar con cada algoritmo una función matemática exacta que mida su “eficiencia” dependiendo sólo de los siguientes factores:

• Las características estructurales del algoritmo.

• El tamaño del conjunto de datos de entrada: El número de datos con los cuales trabaja el algoritmo. Esta medida se interpreta según el tipo de algoritmo sobre el cual se esté trabajando.

Se define la función TA(n) como la cantidad de trabajo realizado por el algoritmo
A para procesar una entrada de tamaño n y producir una solución al problema.

El análisis matemático de algoritmos es independiente de la implementación, sin
embargo tiene varios inconvenientes:

• La imposibilidad de determinar, para muchos problemas y cada una de las posibles entradas, la cantidad de trabajo realizado

• La dificultad para determinar TA(n) exactamente.

Análisis Asintótico de Algoritmos
Técnica derivada del análisis matemático de algoritmos basada en dos conceptos
fundamentales: la caracterización de datos de entrada y la complejidad asintótica.

• Peor caso: Los casos de datos de entrada que maximizan la cantidad de trabajorealizado por un algoritmo.

• Mejor caso: Los casos de datos de entrada que minimizan la cantidad detrabajo realizado por un algoritmo.

• Caso promedio: El valor medio de la cantidad de trabajo realizado por un algoritmo. Se debe tener en cuenta la distribución probabilística de los datos de entrada que se manejan.

• Énfasis en el peor caso, ya que representa una cota superior para la cantidadde trabajo realizado por un algoritmo

• La idea fundamental consiste en tratar de encontrar una función W(n), fácil de calcular y conocida, que acote asintóticamente el orden de crecimiento de la función TA(n)

• Se estudia la eficiencia asintótica de algoritmos: Cómo se incrementa la cantidad de trabajo realizado por un algoritmo a medida que se incrementa (con valores suficientemente grandes”) el tamaño de la entrada

• Para realizar este procedimiento se necesitan herramientas especiales: las notaciones asintóticas

- Bibliografia

^{http://es.wikipedia.org/wiki/An%C3%A1lisis_asint%C3%B3tico}

^{Lo ultimo lo saque de un pdf y no se como ligarlo aqui para que lo chequen.}