Análisis de algoritmos

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




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





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





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...





El modelo RAM









El modelo RAM









El modelo RAM









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.





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.





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)





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)





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





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...





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))”









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))”









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




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))”


Technology

Análisis de algoritmos