Introducción al Análisis de Algoritmos
Estructura de Datos Andrea Rodrı́guez Análisis de Algoritmos Notaciones Introducción al Análisis de Algoritmos Sistemas Recurrentes Dividir para conquistar M. Andrea Rodrı́guez-Tastets Universidad de Concepción,Chile www.inf.udec.cl\ ∼andrea [email protected] I Semestre - 2010 Estructura de Datos Andrea Rodrı́guez Análisis de Algoritmos Objetivos de la Clase Durante esta clase revisaremos análisis de algoritmos. Se espera que al final de la clase los alumnos puedan: I Entender el concepto de tiempo de ejecución de un algoritmo. I Poder determinar una cota de tiempo de ejecución de algoritmos simples. I Entender los sistemas recurrentes y aplicar análisis de algoritmos a ellos. Notaciones Sistemas Recurrentes Dividir para conquistar Estructura de Datos Andrea Rodrı́guez Definiciones I Analizar un algoritmo es predecir cuánto recurso requiere su ejecución. Ocasionalmente, recursos de comunicación y hardware son de ı́nteres particular, sin embargo, en la mayorı́a de los casos, es el tiempo de ejecución el de mayor ı́nteres. I El tiempo de ejecución de un algoritmo en base a una entrada en particular de datos es el número de operaciones primitivas o pasos ejecutados. I En este curso nosotros trataremos con algoritmos eficientes (polinomiales). Sin embargo, existen algunos problemas para los cuales no existe un algoritmo eficiente conocido. Un subconjunto de estos casos son los llamados problemas NP-complete. Esta temática se ve en un curso de complejidad de algoritmos. Análisis de Algoritmos Notaciones Sistemas Recurrentes Dividir para conquistar Estructura de Datos Andrea Rodrı́guez Análisis de Algoritmos Notaciones Análisis de Algoritmos Tiempo ejecución n n2 n3 2n 3n n! n = 10 0,00001 seg. 0,0001 seg. 0,001 seg. 0,001 seg. 0,059 seg. 3,63 seg Sistemas Recurrentes n = 20 0,00002 seg. 0,0004 seg. 0,008 seg. 1 seg. 58 min. 771 siglos n = 30 0,00003 seg. 0,009 seg. 0,027 seg. 17,9 min. 6,5 años 8x1016 siglos n = 40 0,00004 seg. 0.0016 seg. 0.064 seg. 12,7 dı́as 3.855 siglos 3x1032 siglos Dividir para conquistar Modelo de Implementación Estructura de Datos Andrea Rodrı́guez I I Para realizar un análisis de algoritmos, se requiere de un modelo de implementación en el cual se ejecutan nuestros algoritmos y que es independiente del lenguaje de máquina. Instrucciones son las comúnmente encontradas en computadores, para las cuales asumimos un tiempo constante. I El modelo random access machine (RAM) considera que la ejecución de intrucciones de algoritmos es secuencial, una tras otra, sin operaciones concurrentes. Cada operación simple (+, −, =, if) toma un paso. Loops y llamadas a subrutinas son operaciones no simples o complejas. Ellas dependenden de la entrada de datos y del contenio de las subrutinas. Cada acceso a memoria toma un paso. I En RAM no se modela la memoria jerárquica (virtual, cache, etc..), lo cual puede ser significante para cierta clase de problemas. Análisis de Algoritmos Notaciones Sistemas Recurrentes Dividir para conquistar Estructura de Datos Andrea Rodrı́guez Análisis de Algoritmos Notaciones Considere el siguiente programa de ordenamiento, donde tk representa el número de veces la condición del if es satisfecha: Sistemas Recurrentes Dividir para conquistar lı́nea 1 2 3 4 5 6 código for i := 1 to n-1 do [ for j:= 1 to n-i do[ if A[j] > A[j+1] do [ temp:= A[j]; A[j] := A[j+1]; A[j+1] : = temp;] ] ] costo constante c1 c2 c3 c4 c5 c6 ejecuciones n Pn−1 (k + 1) k=1 Pn−1 k k=1 Pn−1 t k=1 k Pn−1 t k=1 k Pn−1 t k=1 k Estructura de Datos Andrea Rodrı́guez Análisis de Algoritmos Peor, mejor y caso promedio I La complejidad del peor caso de un algoritmo es una función definida por el número maximo de pasos tomados para instancia n. I La complejidad del mejor caso de un algoritmo es una función definida por el número mı́nimo de pasos tomados para instancia n. I La complejidad del caso promedio de un algoritmo es una función definida pornúmero promedio de pasos tomados para instancia n. Cada una de estas complejidades define una función númerica: tiempo versus tamaño. Notaciones Sistemas Recurrentes Dividir para conquistar Estructura de Datos Andrea Rodrı́guez Análisis de Algoritmos Para la mayorı́a de los algoritmos que veremos en este curso, nos interesará ver el peor caso del análisis, es decir, el mayor tiempo para cualquier entrada de largo n. Las razones son las siguientes: I el peor caso es un lı́mite superior en tiempo de ejecución de cualquier entrada. Ası́, se garantiza que el algoritmo nunca tomará más que eso; I para algunos casos el peor caso es bastante común; y I el caso promedio es muchas veces tan malo como el peor caso. Por ejemplo, considere el ejemplo anterior. En promedio, uno podrı́a estimar que if ocurre la mitad de las veces, osea tk = k/2. Esto resulta en que la función T (n) sigue siendo cuadrática para otra constante dada. Notaciones Sistemas Recurrentes Dividir para conquistar Estructura de Datos Andrea Rodrı́guez Análisis de Algoritmos Notaciones Sistemas Recurrentes Análisis exacto!!! Es muy difı́cil tener una función exacta del mejor, peor o caso promedio. Es más fácil hablar de un lı́mite superior o inferior de la función. Notación asintóticas son una forma más práctica de manejar funciones de complejidad. Dividir para conquistar Estructura de Datos Andrea Rodrı́guez Notación Θ Análisis de Algoritmos Para una función dada g (n): Notaciones Θ(g (n)) = {f (n) : existen las constantes positivas c1 , c2 y n0 tal que 0 ≤ c1 g (n) ≤ f (n) ≤ c2 g (n)para todo n ≥ n0 } Sistemas Recurrentes Dividir para conquistar Estructura de Datos Andrea Rodrı́guez Notación O Análisis de Algoritmos Para una función dada g (n): Notaciones O(g (n)) = {f (n) : existen las constantes positivas c y n0 tal que 0 ≤ f (n) ≤ cg (n)para todo n ≥ n0 } cg(n) f(n) Sistemas Recurrentes Dividir para conquistar Estructura de Datos Andrea Rodrı́guez Notación Ω Análisis de Algoritmos Para una función dada g (n): Notaciones Ω(g (n)) = {f (n) : existen las constantes positivas c y n0 tal que 0 ≤ cg (n) ≤ f (n)para todo n ≥ n0 } f(n) cg(n) Sistemas Recurrentes Dividir para conquistar Estructura de Datos Andrea Rodrı́guez Análisis de Algoritmos Notaciones Ejemplos de O 2 Sistemas Recurrentes 2 2 3n − 100n + 6 = O(n2) porque 3n > 3n − 100n + 6 3n2 − 100n + 6 = O(n3) porque ,01n3 > 3n2 − 100n + 6 3n2 − 100n + 66 6= O(n) porque c ∗ n < 3n2 cuando n > c Se debe pensar en igualdad como en el conjunto de funciones Dividir para conquistar Estructura de Datos Andrea Rodrı́guez Análisis de Algoritmos Notaciones Sistemas Recurrentes Ejemplos de ω Dividir para conquistar 3n2 − 100n + 6 = Ω(n2) porque 2 : 99n2 < 3n2 − 100n + 6 3n2 − 100n + 6 6= Ω(n3) porque 3n2 − 100n + 6 < n3 2 10 3n − 100n + 66 = Ω(n) porque 1010 n < 3n2 − 100 + 6 Estructura de Datos Andrea Rodrı́guez Análisis de Algoritmos Notaciones Ejemplos de θ Sistemas Recurrentes Dividir para conquistar 3n2 − 100n + 6 = Θ(n2) porque se cumple O, Ω 3n2 − 100n + 6 6= Θ(n3) porque se cumple sólo O 3n2 − 100n + 66 6= Θ(n) porque se cumple sólo Ω Estructura de Datos Andrea Rodrı́guez Análisis de Algoritmos Notaciones Propiedades Notaciones I Θ(g (n)) ⊆ O(g (n)) I Θ(g (n)) ⊆ Ω(g (n)) I Transitividad: (f (n) ∈ O(g (n)) ∧ g (n) ∈ O(h(n))) → f (n) ∈ O(h(n)) I Reflexividad: f (n) ∈ O(f (n)) I Simetrı́a Transpuesta: f (n) ∈ O(g (n)) iff g (n) ∈ Ω(f (n)) Sistemas Recurrentes Dividir para conquistar Estructura de Datos Andrea Rodrı́guez Análisis de Algoritmos Notaciones Suma y sustracción Si tenemos que f (n) = O(n2 ) y g (n) = O(n2 ), entonces: I ¿Qué sucede con f 0 (n) = f (n) + g (n)? I ¿Qué sucede con f 00 (n) = f (n) − g (n)? Sistemas Recurrentes Dividir para conquistar Estructura de Datos Andrea Rodrı́guez Ejemplo Dado el siguiente algoritmo, donde A[1:n] es un arreglo ordenado, indique qué hace y derive su complejidad. Indique el caso peor de la complejidad. Análisis de Algoritmos Notaciones Sistemas Recurrentes Dividir para conquistar Procedure UNKNOW (intA[1 : n],int n,int x,var int j) l := 1; u := n; while l < u do [ m := b(l + u)/2c; case [ x > A[m] : l := m + 1; x < A[m] : u := m − 1; else j := m; return; ] ] j: = 0; end UNKNOW Estructura de Datos Andrea Rodrı́guez Análisis de Algoritmos Sistemas recurrentes Notaciones En muchos casos de algoritmos, las técnica básicas de conteo para conjuntos finitos no funcionan. Estos casos son los sistemas recursivos que usan un enfoque de ecuaciones recurrentes. Ejemplo clásico de tales funciones son la secuencia Fibonacci. Sistemas Recurrentes F (0) = F (1) = 0 1 F (n) = F (n − 1) + F (n − 2), n > 1 Dividir para conquistar Estructura de Datos Andrea Rodrı́guez Análisis de Algoritmos Notaciones Un sistema recursivo es un conjunto de condiciones de borde y ecuaciones recurrentes, las cuales especifican una secuencia única o una función desde N k to R, con N siendo los naturales, R los reales y k perteneciente a los enteros positivos I +. Un solución a un sistema recurrente es una función f : N k → R que satisface las condiciones de borde y los ecuaciones de recurrencia. Ejemplo: El número de permutaciones de n objetos puede ser expresado usando el sistema recurrente: P(0) = 1, P(n) = nP(n − 1), n > 0 Sistemas Recurrentes Dividir para conquistar Estructura de Datos Andrea Rodrı́guez Ejemplo: sistemas recursivos Ejemplo: Considere el siguiente algoritmo que retorna la suma de los n primeros números en el arreglo A. ProcedureSUM(n) begin total ← 0; for i ← 1 to n step 1 do total ← total + A[i]; return total; end Análisis de Algoritmos Notaciones Sistemas Recurrentes Dividir para conquistar Estructura de Datos Andrea Rodrı́guez Análisis de Algoritmos Notaciones Asuma que definimos la complejidad de SUM como el número de sumas realizadas. Esta función es caracterizada por el siguiente sistema recursivo o recurrente: f (0) = c1 , f (1) = c2 , f (n) = f (n − 1) + c2 , n > 1 Sistemas Recurrentes Dividir para conquistar Estructura de Datos Andrea Rodrı́guez Ejercicio Considere el siguiente algoritmo recursivo de evaluación de un polinomio. Function P(p) if p es constante then return p a := constante del polinomio pa:= factorización de p por x return P(pa)x+a Ejemplo: Sea p = 5x 4 + 3x 3 + 2x 2 + 1, entonces el algoritmo se ejecuta de la siguiente forma: P(5x 4 + 3x 3 + 2x 2 + 1) = P(5x 3 + 3x 2 + 2x)x + 1 = P(P(5x 2 + 3x + 2)x)x + 1 = P(P(P(5x + 3)x + 2)x)x + 1 = P(P(P(P(5)x + 3)x + 2)x)x + 1 Se pide determinar el tiempo de ejecución estimado de la evaluación de un polinomio en función de n, donde n es el orden del polinomio. Análisis de Algoritmos Notaciones Sistemas Recurrentes Dividir para conquistar Estructura de Datos Andrea Rodrı́guez Análisis de Algoritmos Notaciones Un tipo especial de sistemas recursivos en algoritmos, son los llamados algoritmos que dividen para conquistar. Estos algoritmos dividen el problema en problemas más pequeños, resuelven estos sub problemas y los combinan para obtener la solución global. Este tipo de enfoque de algoritmos es usualmente implementado como un sistema recursivo, ya que en muchos casos, los subproblemas son equivalentes al problema general. Sistemas Recurrentes Dividir para conquistar Estructura de Datos Andrea Rodrı́guez Análisis de Algoritmos Los casos de algoritmos de este tipo que veremos cumplen las siguientes restricciones: 1. El costo de resolver un problema de tamaño n = 1 es c, donde c es una constante no negativa. 2. Para k > 0, problemas de tamaño n = b k son divididos en ‘a’ diferentes problemas de tamaño n/b 3. Para todos los problemas de tamaño n > 1, el costo de dividir el problema en subproblemas más el costo de combinar las soluciones para obtener la solución al problema original es h(n), una función de n. Notaciones Sistemas Recurrentes Dividir para conquistar Estructura de Datos Andrea Rodrı́guez Análisis de Algoritmos Notaciones Sistemas Recurrentes Estas condiciones producen problemas de la siguiente forma: f (1) = c, f (n) = af (n/b) + h(n), n = b k , k > 0 Dividir para conquistar Estructura de Datos Andrea Rodrı́guez Análisis de Algoritmos Notaciones Determinación de Costo de Recurrencia En general, determinar el costo de una recurrencia se hace por: I Método de sustitución I Método del árbol recursivo Sistemas Recurrentes Dividir para conquistar Estructura de Datos Andrea Rodrı́guez Análisis de Algoritmos Notaciones Método de Sustitución El método de sustitución utiliza dos pasos: I Proponer una forma de solución. I Hacer un prueba por inducción para encontrar las constantes y mostrar que la solución funciona. Sistemas Recurrentes Dividir para conquistar Estructura de Datos Andrea Rodrı́guez Análisis de Algoritmos Notaciones Inducción matemática I Probar que funciona para P(1) I Probar que si P(1) . . . P(n) son ciertas, entonces también funciona para P(n + 1), con n cualquier entero positivo. Sistemas Recurrentes Dividir para conquistar Estructura de Datos Ejemplo de sustitución Considere el caso de una recurrencia T (n) = 2T (bn/2c) + n, y asumamos una solución T (n) = O(nlogn). La idea entonces es probar que T (n) ≤ cnlgn para un c > 0. Haciendo inducción: I Asumimos que se cumple para bn/2c, esto es T (bn/2c) = cbn/2clog (bn/2c) I Luego por sustitución: T (n) ≤ 2(cbn/2clog (bn/2c)) + n ≤ cnlog (n/2) + n ≤ cnlogn − cnlog 2 + n ≤ cnlogn − cn + n ≤ cnlogn con c ≥ 1. Andrea Rodrı́guez Análisis de Algoritmos Notaciones Sistemas Recurrentes Dividir para conquistar Estructura de Datos Andrea Rodrı́guez Análisis de Algoritmos Ejemplo de sustitución (cont..) La inducción requiere que se pruebe que la solución funciona para las condicions de borde. Si asumimos que T (1) = 1 es la condición de borde, pero T (n) ≤ cnlogn nos da que T (1) ≤ c1lg 1 = 0, una contradicción. Sin embargo, podemos hacer que T (n) ≤ cnlogn sea verdadero para algún n ≥ n0 . Entonces lo que debemos hacer es definir por ejemplo para un n0 = 2. Ası́ hemos extendido la condición de borde. Notaciones Sistemas Recurrentes Dividir para conquistar Estructura de Datos Andrea Rodrı́guez Ábol recursivo El siguiente árbol representa la recurrencia T (n) = 3T (n/4) + cn2 . T(n/4) T(n/4) Notaciones Sistemas Recurrentes cn2 cn2 Análisis de Algoritmos Dividir para conquistar c(n/4)2 c(n/4)2 c(n/4)2 T(n/4) ......... ......... ......... ............ ......... ......... ......... ......... ......... ......... T(1) T(1) T(1) Estructura de Datos Andrea Rodrı́guez Análisis de Algoritmos Notaciones Método del árbol recursivo En un árbol recursivo, cada nodo representa el costo de un subproblema dentro del proceso recursivo. Se suma el costo de cada nivel del árbol para obtener el costo por nivel y luego se suman los costos por niveles. Estos métodos son especialmente útiles cuando se usan en algoritmos que dividen para conquistar. Sistemas Recurrentes Dividir para conquistar Estructura de Datos Método del árbol recursivo (cont...) El tiempo de ejecución estimado para la recurrencia T (n) = 3T (n/4) + cn2 es: Andrea Rodrı́guez Análisis de Algoritmos Notaciones cn2 cn2 Sistemas Recurrentes Dividir para conquistar c(n/4)2 c(n/4)2 c(n/4)2 ......... ......... ......... ............ ......... ......... ......... ......... ......... ......... T(1) T(1) T(1) 3/16 cn2 O(nlog43) Total : O(n2) Estructura de Datos Andrea Rodrı́guez Teorema Maestro Teorema: Sea a y b enteros tal que a ≥ 1 y b > 1, y sea T : N → R la función recurrente: Análisis de Algoritmos Notaciones Sistemas Recurrentes T (n) = aT (n/b) + f (n), n = b k , k > 0 donde n/b es bn/bc o dn/be, entonces: I Si f (n) = O(nlogb a− ), para alguna constante > 0, entonces T (n) es acotada por Θ(nlogb a ). I Si f (n) = O(nlogb a ), entonces T (n) es acotada por Θ(nlogb a logn). I Si f (n) = Ω(nlogb a+ ), para alguna constante > 0, si af (n/b) ≤ cf (n) para un c < 1 entonces f (n) y si n es suficientemente grande, entonces T (n) es acotada por Θ(f (n)). Dividir para conquistar Estructura de Datos Andrea Rodrı́guez Ejemplo: Dividir para Conquistar El siguiente algoritmo de MAXMIM aplica una técnica de dividir para conquistar para devolver los valores máximo y mı́nimo de las entradas A[i], . . . , A[j] de un vector A de enteros. Function MAXMIN(int i, int j) :< int, int > begin if i = j then return < A[i], A[i] > else < max1, min1 >← MAXMIN(i, b i+j c); 2 < max2, min2 >← MAXMIN(b i+j c + 1, j); 2 if max1 < max2 then max1 ← max2; if min1 > main2 then min1 ← min2; return < min1, max2 > end Análisis de Algoritmos Notaciones Sistemas Recurrentes Dividir para conquistar Estructura de Datos Andrea Rodrı́guez Análisis de Algoritmos Notaciones Se define la complejidad de este algoritmo como T (n), con T (n) el número de comparaciones entre elementos del arreglo cuando A tiene n entradas. El siguiente sistema recurrente describe la función T para cada argumento potencia de 2: T (1) = c1 , T (n) = 2f (n/2) + c2 , n = 2 , k > 0 k Entonces por el teorema, donde f (n) = Θ(nlogb a ) = Θ(1), T (n) = Θ(logn). Sistemas Recurrentes Dividir para conquistar Estructura de Datos Andrea Rodrı́guez Análisis de Algoritmos Notaciones Ejercicios Sistemas Recurrentes I Use el teorema Maestro par determinar las cotas de las siguientes funciones de costo computacional: I I I I T (n) = 4T (n/2) + n; T (n) = 9T (n/3) + n; T (n) = 4T (n/2) + n2 ; T (n) = 4T (n/2) + n3 ; Dividir para conquistar Estructura de Datos Andrea Rodrı́guez Ejercicios (cont...) Considere el siguiente algoritmo con un arreglo A[1.. n] : Procedure XX (var int A[1..n], i, j) begin if j ≤ i then return XX (A, i, b(i + j)/2c); XX (A, b(i + j)/2c + 1, j); for k = i to j do for l = k + 1 to j do if (A[k] < A[l]) then temp := A[k]; A[k] := A[l]; A[l] := temp; endif enddo enddo end Indique lo que hace el algoritmo y dé su tiempo de ejecución estimado em función del largo del arreglo A (n). Análisis de Algoritmos Notaciones Sistemas Recurrentes Dividir para conquistar
© Copyright 2024