1 Análisis de AlgoritmosIntroducción Basado en el Texto “Algoritmos en C++” , Robert Sedgewick, y “Estructura de Datos, Algoritmos y Programación orientada a Objetos” , Gregory L. Heileman
2 Introducción TAD’s Tipo Abstracto de DatosEn estructura de Datos, la problemática se centró en la representación de los Datos y el conjunto de Operaciones (funciones) de sobre ellos. TAD’s={Estructura de Datos + Operaciones} Ejemplo: Matriz M ObtenerElemento(i,j,M) Sumar(M1,M2) Producto(M1,M2)…
3 Introducción Problema FundamentalSea A={a1,a2,a3,..,an}, un conjunto de algoritmos que resuelven un problema P, cada una con alguna Estructura de Datos. Cual algoritmo es más eficiente? En tiempo CPU, espacios de Memoria o ambas
4 Introducción En el Análisis de Algoritmos, el criterio de selección está definido por tiempo de CPU, esto implica que serán más eficiente el programa es más rápido.
5 Introducción Volúmen n.La rapidez de un progrma P es medida en relación a alguna “Carga” o volumen de tamaño n de datos: Ej. P(n): ordena n datos enteros P(n): calcula factorial de n P(p,q): calcula la determinante de una matriz de tamaño pxq, n=p*q.
6 Introducción Tiempo T(n).Se define T(n) como la rapidez con que se “ejecuta” un algoritmo con una entrada de datos de tamaño n. T(n) se mide en términos de cantidad de operaciones necesarias para concluir el programa.
7 Introducción Calcular el factorial de n. Volumen nint factorial(int n) { int fact=1; for(i=1;i<=n;i++) fact=fact*i; return (fact); } Volumen : el valor entero n
8 Introducción Calculando el factorial de un entero n utilizando un algoritmo lineal ( secuencial). int factorial(int n) { int fact=1; for(i=1;i<=n;i++) fact=fact*i; return (fact); } Tiempo T(n) T(n) = n consultas + n sumas + n multiplicaciones + n asignaciones T(n) = (2 + 4n) operaciones
9 Introducción Calculando el factorial de un entero n utilizando un algoritmo lineal ( secuencial). int factorial(int n) { int fact=1; for(i=1;i<=n;i++) fact=fact*i; return (fact); } Tiempo T(n) Si T(n) = número de multiplicaciones necesarias Entonces T(n) = n mutiplicaciones
10 Introducción Calculando el factorial de n, utilizando la definición RECURSIVA factorial(n) como sigue: si n>0 factorial (n) = factorial(n-1) * n si n=0
11 Introducción Tiempo T(n) int factotrial (int n) { if n=0 return 1;return(factorial(n-1)*n); } Si T(n) = multiplicaciones Necesarias, entonces: ;si n=0 T(n)= T(n-1)+1 ;si n >0
12 Introducción Probando T(n) por inducción matemáticaBuscando una hipótesis, basado solamente en el algoritmo. T(0) = 0 T(1) = 1 T(2) = 2 T(3) = 3 : T(n) = n ???
13 Introducción Resolviendo por inducción matemáticaSea Q una proposición a demostrar Se intenta probar que Q es válida para todo n>= n0 1. Probar que Q es válida para n0 2. Suponer que Q es válida para todo entero <= n-1 (Hipótesis de inducción) 3. Probar que Q es válido para todo n
14 Introducción Resolviendo por inducción matemáticaProposición Q = { T(n) = n} Probar que Q es válida para n0 = 0 T(0) = 0, Q se cumple, por simple vista del algoritmo. Suponer que Q es válida para todo entero 0
15 Introducción Torres de HanoiEl problema de las torres de Hanoi se puede resolver recursivamente: Inicialmente los n Discos están en el poste A Los n-1 disco superiores de A son trasladados al poste B El único disco restante es del poste A se mueve al poste C Los n-1 discos del poste B son trasladados al poste C.
16 Introducción Problema de LasTorres de HanoiDefiniremos una función Hanoi() como sigue: Hanoi(n,A,B,C) mueve n Discos desde A a C, usando B Hanoi(int n,A,B,C) { if(n=1) mover disco superior de A a C return; Hanoi(n-1,A,C,B); mover disco superior de A a C; Hanoi(n-1,B,A,C) }
17 Introducción Calculando T(n) para Problema de las Torres de Hanoi, donde N es la cantidad de movimientos de discos. si n=1 T(n)= 2T(n-1) si n >1
18 Introducción Buscando una hipótesis, basado solamente en el algoritmo.: T(n) = 2n -1 ???
19 Introducción Resolviendo por inducción matemáticaProposición Q = { T(n) = 2n - 1} Probar que Q es válida para n0 = 1 T(1) = 1, Q se cumple, por simple vista del algoritmo. Suponer que Q es válida para todo entero 1
20 Introducción Análisis Asintótico Definición 1Sean f(n) y g(n) dos funciones [f,g : Z+ → R+]. Se dice que f(n) es “O grande” de g(n) y se escribe como: f(n) = O(g(n)) Si existen dos constantes positivas c,n0 tal que f(n) ≤ c g(n) para todo n≥ n0
21 Introducción Propiedades 3- Se puede demostrar queO(g(n)2) = O(g(n)*g(n)) = O(g(n))*O(g(n)) Así, Similarmente O((lg n)2) = O(lg n)2
22 Introducción Ejemplo 1 Sea f(n)=n3 + 20 n2 + 100 n f(n) = O(g(n))Puesto que: n n n <= n n n3 = 121 n3 Escogiendo C = 121 y n0 = 0 Es suficiente para que se cumpla la definición
23 Introducción Otro ejemplo, sea f(n)=lg n, y g(n)=(n/4)2Podemos observar que: g(n) < f(n) para todo n, tal que a < n < b. Será que g(n) = O(f(n))?, la respuesta es NO pues si hacemos n0=a, la igualdad anterior no se cumple para n > b, y por lo tanto no se cumple para todo n > n0. Será que f(n) = O(g(n))?, la respuesta es SI pues si hacemos n0=b, la igualdad anterior si se cumple para n > b, y por lo tanto se cumple para todo n > n0. Lo anterior considerando por ejemplo c=1. g() f() g()<=f() g()>f() a b Nota: de aquí en adelante, lg n corresponde a log2 n
24 TALLER 2 Revisar los algoritmos fundamentales de búsqueda.Problema: Buscar la o las cartillas ganadoras en el juego de azar KINO, considere 1.000, , cartillas. Se pide: Revisar los algoritmos fundamentales de búsqueda. Implementar en C++ o Java Obtener f(n) para cada uno de ellos Comprobar f(n) graficando el comportamiento del algoritmo para los diferentes volúmenes de datos.
25 Introducción Análisis Asintótico Definición 2Sean f(n) y g(n) dos funciones [f,g : Z+ → R+]. Se dice que f(n) es “Omega grande” de g(n) y se escribe como: f(n) = Ω(g(n)) Si existen dos constantes positivas c y n0 tal que f(n) ≥ c g(n) para todo n≥ n0
26 Introducción Ejemplo, sea f(n)=lg n, y g(n)=(n/4)2Será que f(n) = Ω(g(n))?, la respuesta es NO porque no se puede encontrar c y n0 que satisfaga f(n) que satisfaga f(n) ≥ cg(n) para todo n ≥ n0. Será que g(n) = Ω(f(n))?, la respuesta es SI pues si hacemos n0=b, la igualdad anterior si e cumple para c=1 y n ≥ b, y por lo tanto se cumple para todo n > n0. g() f() g()<=f() g()>f() a b
27 Introducción Así tenemos que f(n)=Ω(g(n) ssi g(n)=O(f(n))Esta simetría implica que las propiedades que se cumple para O() también se cumple para Ω().
28 Introducción Análisis Asintótico Definición 3 (Cota Asintótica)Sean f(n) y g(n) dos funciones [f,g : Z+ → R+]. Se dice que f(n) es “Theta grande” de g(n) y se escribe como: f(n) = Θ(g(n)) Si existen dos constantes positivas c1 c2, y n0 tal que c2 g(n) ≤ f(n) ≤ c2 g(n) para todo n≥ n0
29 Introducción Por la definición 1 y 2, podemos expresar:f(n) = Θ(g(n)) ssi f(n)=O(g(n)) y g(n)=Ω(f(n)) Pues ambas en conjunto aseguran la existencia de dos constantes positivas c1 c2, y de n0 tal que c2 g(n) ≤ f(n) ≤ c2 g(n) para todo n≥ n0