Aritmetica de la notacion o

 Analisis Algoritmos Complejidad - Presentation Transcript
1. U1.- Análisis de Algoritmos.
2. 1.1.- Concepto de complejidad de un algoritmo.
Fácil de entender, codificar y depurar.Algoritmo
Uso efectivo de los recursos del computador + menor tiempo de ejecución
Cuando se resuelve un problema
3. Tiempo de ejecución de un programa.
Datos de entrada
Calidad del código generadopara crear el código objeto.
Tiempo de ejecución
Naturaleza y rapidez de las instrucciones maquina
Complejidad de tiempo del algoritmo
4. Tiempo de ejecución de un programa.
T(n). Tiempo deejecución de un programa con una entrada de tamaño n.
T(n) como tiempo de ejecución del “peor caso”. Máximo valor del tiempo de ejecución para entradas de tamaño n.
No es posible expresar T(n) enunidades de tiempo. ¿Por qué?.
5. Asíntotas
Comportamiento asintótico de un algoritmo es cuando el tamaño de las entradas N tiende a infinito.
A un conjunto de funciones que comparten un mismocomportamiento asintótico le denominaremos un orden de complejidad
6. Ordenes de complejidad
7.
8. 1.2 Aritmética de la notación O.
La notación O conocida también como notación asintótica, seutiliza para hacer referencia a la velocidad de crecimiento de los valores de una función.
Ejemplo: T(n) = O(n2). Se lee “o de n al cuadrado”.
Significa que existen constantes enteras c y n0 tales quepara n mayor o igual que n0, se tiene que T(n) ≤ cn2.
9. 1.2 Aritmética de la notación O.
Regla de la suma: T1(n) + T2(n) = O(max(f(n),g(n))). Calcula el tiempo de ejecución de una secuencia depasos de programa, donde cada paso de programa puede contener ciclos y ramificaciones.
Ejemplo: Se tienen O(n2), O(n3), O(nlogn) => O(max(n2,n3) ) es O(n3); y O(max(n3, nlogn)) es O(n3). Por lotanto la suma de los tres es igual a O(n3). 
10. 1.2 Aritmética de la notación O.
Regla del producto: T1(n)T2(n) = O(f(n)f(g)).
Según esta regla O(cf(n)) es lo mismo que O(f(n)).
Ejemplo:...