Complejidad Algoritmica

TRABAJO DE INVESTIGACION

GABRIEL PEÑA PATIÑO

PRESENTADO A:
ANGEL AUGUSTO AGUDELO

EN LA MATERIA DE:
ESTRUCTURAS DE LENGUAJES

UNIVERSIDAD LIBRE SECCIONAL PEREIRA
INGENIERIA DE SISTEMAS2011

TRABAJO DE INVESTIGACION

COMPLEJIDAD ALGORITMICA

La complejidad algorítmica representa la cantidad de recursos, mejor conocidos como temporales, que necesita un algoritmo para resolverun problema y por tanto permite determinar la eficiencia de dicho algoritmo. Los criterios que se pueden emplear para evaluar la complejidad algorítmica no proporcionan medidas absolutas sino medidasrelativas al tamaño del problema.
Se podría decir que lo más básico para tener en cuenta con la complejidad algorítmica es que el tiempo empleado por el algoritmo se mide en pasos, que el costedepende del tamaño de los datos y si el tamaño de los datos es grande lo que importa es el comportamiento asintótico de la eficiencia.

NOTACION O

Los tiempos de ejecución para diferentes algoritmosdan lugar a diferentes clases de complejidad. Cada clase de complejidad se caracteriza por una familia de curvas distinta. Todas las curvas de una clase de complejidad concreta tienen la misma formabásica, pues solo se diferencian entre ellas por el valor de sus constantes
La notación O (también llamada O mayúscula), se utiliza para comparar la eficiencia de los algoritmos. La notación O se centraen el término dominante an2 (es decir, en aquel que más crece cuando n aumenta), e ignora el resto de términos. Por lo tanto, desprecia también la constante de proporcionalidad a así:
O(anˆ2 + bn +c)= O(anˆ2) = O(nˆ2)

NOTACION DE LANDAU

La notación de Landau se define de la siguiente forma:
Si f, g son funciones complejas definidas en un entorno de un punto Xo, entonces
* cuando si ysólo si existe un ε > 0 tal que para todo x en un entorno de .
* cuando si y sólo si para todo ε > 0 tenemos que para todo x en un entorno de .
Una versión un poco más restrictiva pero...