análisis de algoritmos
TRANSCRIPT
OutlineModelos de referencia
Analisis del Insertion SortCrecimiento de funciones
Notacion ThetaNotacion Big OhNotacion OmegaNotacion Small o
Analisis de Algoritmos
Roberto Carlos Abreu Dıaz
December 2, 2009
Roberto Carlos Abreu Dıaz Analisis de Algoritmos
OutlineModelos de referencia
Analisis del Insertion SortCrecimiento de funciones
Notacion ThetaNotacion Big OhNotacion OmegaNotacion Small o
1 Modelos de referencia
2 Analisis del Insertion SortPseudocodigo
3 Crecimiento de funciones
4 Notacion Theta
5 Notacion Big Oh
6 Notacion Omega
7 Notacion Small o
Roberto Carlos Abreu Dıaz Analisis de Algoritmos
OutlineModelos de referencia
Analisis del Insertion SortCrecimiento de funciones
Notacion ThetaNotacion Big OhNotacion OmegaNotacion Small o
Modelos de referencia
Antes de analizar un algoritmo debemos tener un modelo de laimplementacion de la tecnologıa que se va a usar, incluyendo unmodelo para los recursos de esa tecnologıa y sus costos.
Nosotros...
Asumamos un modelo de computacion generico de acceso aleatorio(Random-Access Machine) y nuestros algoritmos sonimplementados como programas de computadoras
Roberto Carlos Abreu Dıaz Analisis de Algoritmos
OutlineModelos de referencia
Analisis del Insertion SortCrecimiento de funciones
Notacion ThetaNotacion Big OhNotacion OmegaNotacion Small o
El modelo RAM
Las instrucciones se ejecutan una tras otra
No hay operaciones concurrentes
Contiene instrucciones comunmente encontradas encomputadores reales: aritmeticas( +, -, *, /, %), movimientode data (cargar, copiar, almacenar) y control (condicionales,llamado de funciones y retorno)
No modela la jerarquıa de memoria que se encuentra enlas arquitecturas modernas: cache, memoria virtual,etc...
Roberto Carlos Abreu Dıaz Analisis de Algoritmos
OutlineModelos de referencia
Analisis del Insertion SortCrecimiento de funciones
Notacion ThetaNotacion Big OhNotacion OmegaNotacion Small o
El modelo RAM
Las instrucciones se ejecutan una tras otra
No hay operaciones concurrentes
Contiene instrucciones comunmente encontradas encomputadores reales: aritmeticas( +, -, *, /, %), movimientode data (cargar, copiar, almacenar) y control (condicionales,llamado de funciones y retorno)
No modela la jerarquıa de memoria que se encuentra enlas arquitecturas modernas: cache, memoria virtual,etc...
Roberto Carlos Abreu Dıaz Analisis de Algoritmos
OutlineModelos de referencia
Analisis del Insertion SortCrecimiento de funciones
Notacion ThetaNotacion Big OhNotacion OmegaNotacion Small o
El modelo RAM
Las instrucciones se ejecutan una tras otra
No hay operaciones concurrentes
Contiene instrucciones comunmente encontradas encomputadores reales: aritmeticas( +, -, *, /, %), movimientode data (cargar, copiar, almacenar) y control (condicionales,llamado de funciones y retorno)
No modela la jerarquıa de memoria que se encuentra enlas arquitecturas modernas: cache, memoria virtual,etc...
Roberto Carlos Abreu Dıaz Analisis de Algoritmos
OutlineModelos de referencia
Analisis del Insertion SortCrecimiento de funciones
Notacion ThetaNotacion Big OhNotacion OmegaNotacion Small o
El modelo RAM
Las instrucciones se ejecutan una tras otra
No hay operaciones concurrentes
Contiene instrucciones comunmente encontradas encomputadores reales: aritmeticas( +, -, *, /, %), movimientode data (cargar, copiar, almacenar) y control (condicionales,llamado de funciones y retorno)
No modela la jerarquıa de memoria que se encuentra enlas arquitecturas modernas: cache, memoria virtual,etc...
Roberto Carlos Abreu Dıaz Analisis de Algoritmos
OutlineModelos de referencia
Analisis del Insertion SortCrecimiento de funciones
Notacion ThetaNotacion Big OhNotacion OmegaNotacion Small o
Pseudocodigo
Analisis del Insertion Sort
El tiempo que toma Insertion Sort depende fundamentalmentede la entrada: el ordenamiento de 1,000 numeros toma masque el de 10.Mas aun, el Insertion Sort puede tomar distinta cantidad detiempo para ordenar dos entradas del mismo tamano perodiferiendo en que tan ya ordenadas esten.
Preliminares...
El tiempo de ejecucion de un algoritmo en funcion de su entrada esla cantidad pasos ejecutados. Asumeremos que un tiempoconstante se necesita para ejecutar cada lınea de codigo.Las lıneas pueden tener distintos tiempos, pero asumeremos que eltiempo de la i-esima lınea toma Ci, donde Ci es constante.
Roberto Carlos Abreu Dıaz Analisis de Algoritmos
OutlineModelos de referencia
Analisis del Insertion SortCrecimiento de funciones
Notacion ThetaNotacion Big OhNotacion OmegaNotacion Small o
Pseudocodigo
Pseudocodigo
Las lıneas donde estan definidos los bucles se ejecutan una vezmas que el cuerpo del bucle mismo. ¿Por que?El tiempo de ejecucion del algoritmo es la suma de lostiempos de ejecucion de cada sentencia ejecutada. Unasentencia que tome Cx tiempo y se repita n veces contribuyenCx al tiempo de ejecucion del algoritmo.
Roberto Carlos Abreu Dıaz Analisis de Algoritmos
OutlineModelos de referencia
Analisis del Insertion SortCrecimiento de funciones
Notacion ThetaNotacion Big OhNotacion OmegaNotacion Small o
Pseudocodigo
Tiempo de ejecucion del Insertion Sort
Sumando los productos anteriores (costo x veces) llegamos a lasiguiente formula:
T(n) = c1n + c2(n − 1) + c4(n − 1) + c5∑n
j=2 tj +c6
∑nj=2(tj − 1) + c7
∑nj=2(tj − 1) + c8(n − 1)
Roberto Carlos Abreu Dıaz Analisis de Algoritmos
OutlineModelos de referencia
Analisis del Insertion SortCrecimiento de funciones
Notacion ThetaNotacion Big OhNotacion OmegaNotacion Small o
Pseudocodigo
Tiempo de ejecucion del Insertion Sort (2)
Notando que:∑nj=2 tj = n(n+1)
2 − 1 y∑nj=2(tj − 1) = n(n+1)
2Entonces:T(n) =
c1n +c2(n−1)+c4(n−1)+c5(n(n+1)2 −1)+c6(n(n+1))
2 +c7(n(n+1)2 )
T(n)
T(n) =( c5
2 + c62 + c7
2 )n2+(c1+c2+c4+ c52 −
c62 −
c72 +c8)n−(c2+c4+c5+c8)
Roberto Carlos Abreu Dıaz Analisis de Algoritmos
OutlineModelos de referencia
Analisis del Insertion SortCrecimiento de funciones
Notacion ThetaNotacion Big OhNotacion OmegaNotacion Small o
Pseudocodigo
Este tiempo de ejecucion puede ser expresado de la formaan2 + bn + c para las constantes a, b y c que dependen de loscostos ci .
Por lo tanto, es una funcion cuadratica
Generalmente nos interesamos por el peor tiempo de ejecucionde los algoritmos, porque...
(1) Es un lımite superior, garantiza que el algoritmo noexcedera tal lımite
(2) El peor de los casos ocurre frecuentemente. Considera elejemplo de una busqueda en una base de datos.
(3) El caso promedio es difıcil de especificar y termina siendouna funcion similar a la del peor de los casos
Roberto Carlos Abreu Dıaz Analisis de Algoritmos
OutlineModelos de referencia
Analisis del Insertion SortCrecimiento de funciones
Notacion ThetaNotacion Big OhNotacion OmegaNotacion Small o
Crecimiento de funciones
En el analisis de algoritmos nos interesa la proporcion o ordende crecimiento.
Este orden de crecimiento es el termino de mayor orden delpolinomio que expresa el tiempo de ejecucion (n2 en el casodel ordenamiento por insercion
Esto es porque, a medida que n crece, los otros terminos noaportan tanto.
En el caso del ordenamiento por insercion, decimos entoncesque su tiempo de ejecucion en el peor de los casos es de ordenθ(n2)
Hay distintas notaciones para expresar el tiempo deejecucion...
Roberto Carlos Abreu Dıaz Analisis de Algoritmos
OutlineModelos de referencia
Analisis del Insertion SortCrecimiento de funciones
Notacion ThetaNotacion Big OhNotacion OmegaNotacion Small o
Notacion Theta
Dada una funcion g(n), decimos por Θ(g(n)) el conjunto defuncionesΘ(g(n)) = f(n): existen constantes positivas c1, c2yn0 tal que0 <= c1g(n) <= f (n) <= c2g(n) para todas las n => n0
O sea
Una funcion f(n) pertenece al conjunto Θ(g(n)) si existenconstante c1yc2 tal que pueda estar en el medio entrec1g(n)yc2g(n), para una n suficientemente grande.
Al decir f(n) = Θ(g(n)) se debe leer ”f(n) es del ordenΘ(g(n))”
Roberto Carlos Abreu Dıaz Analisis de Algoritmos
OutlineModelos de referencia
Analisis del Insertion SortCrecimiento de funciones
Notacion ThetaNotacion Big OhNotacion OmegaNotacion Small o
Roberto Carlos Abreu Dıaz Analisis de Algoritmos
OutlineModelos de referencia
Analisis del Insertion SortCrecimiento de funciones
Notacion ThetaNotacion Big OhNotacion OmegaNotacion Small o
Notacion Big Oh
Dada una funcion g(n), denotamos por O(g(n)) el conjunto defuncionesO(g(n)) = f(n): existen constantes positivas cyn0 tal quef (n) <= cg(n) para todas las n => n0
O sea
La notacion O solo denota un lımite superior. Es como decir, ”a losumo X”. Por lo tanto, n = O(n2). Esto implica tambien que alutilizar la notacion O para expresar el peor tiempo de ejecucion deun algoritmo, tambien estamos expresando tiempo de ejecucionpara cada entrada.
Al decir f(n) = O(g(n)) se debe leer ”f(n) es del ordenO(g(n))”
Roberto Carlos Abreu Dıaz Analisis de Algoritmos
OutlineModelos de referencia
Analisis del Insertion SortCrecimiento de funciones
Notacion ThetaNotacion Big OhNotacion OmegaNotacion Small o
Roberto Carlos Abreu Dıaz Analisis de Algoritmos
OutlineModelos de referencia
Analisis del Insertion SortCrecimiento de funciones
Notacion ThetaNotacion Big OhNotacion OmegaNotacion Small o
Notacion Omega
Dada una funcion g(n), denotamos por Ω(g(n)) el conjunto defuncionesΩ(g(n)) = f(n): existen constantes positivas cyn0 tal que0 <= cg(n) <= f (n) para todas las n => n0
O sea
Ası como O(g(n)) expresa un lımite asintotico superior, Ω(g(n))exprea un lımite asintotico inferior. Esto implica, similar a Big Oh,que al expresar el mejor tiempo de ejecucion con Ω tambienestamos expresando el tiempo de ejecucion de todas las entradas.Ejemplo: El tiempo de ejecucion del insertion-sort cae entreΩ(n)yO(n2).
Al decir f(n) = Ω(g(n)) se debe leer ”f(n) es del ordenΩ(g(n))” Roberto Carlos Abreu Dıaz Analisis de Algoritmos
OutlineModelos de referencia
Analisis del Insertion SortCrecimiento de funciones
Notacion ThetaNotacion Big OhNotacion OmegaNotacion Small o
Small o
Dada una funcion g(n), denotamos por o(g(n)) el conjunto defuncioneso(g(n)) = f(n): existen constantes positivas cyn0 tal que0 <= f (n) < cg(n) para todas las n => n0
O sea
Small o representa, a diferencia de Big O, un lımite asintoticosuperior pero no fuerte. Ejemplo: 2n = o(n2) pero no 2n2 = o(n2)
Al decir f(n) = o(g(n)) se debe leer ”f(n) es del ordeno(g(n))”
Roberto Carlos Abreu Dıaz Analisis de Algoritmos