Notacion Asintotica

Analisis y Diseno de Algoritmos

Marzo 2014

Analisis y Diseno de Algoritmos Notacion Asintotica 1/29

Complejidad

Complejidad

La complejidad (o costo) de un algoritmo es una medida de lacantidad de recursos (tiempo, memoria) que el algoritmonecesita. La complejidad de un algoritmo se expresa enfuncion del tamano del problema (entradas). Elcomportamiento de la funcion determina la eficiencia. No esunica para un algoritmo, depende de los datos.

Analisis y Diseno de Algoritmos Notacion Asintotica 2/29

Ordenes de Complejidad

Ordenes de Complejidad

Se dice que O(f (n)) define un orden de complejidad.Escogeremos como representante de este orden a la funcionf (n) mas sencilla del mismo. As tendremos:

O(1) Orden Constante

O(log n) Orden Logartmico

O(n) Orden Lineal

O(n log n) Log-lineal (cuasilineal)

O(n2) Orden Cuadratico

O(n3) Orden Cubico

O(na) Orden Polinomial a > 3

O(an) Orden Exponencial a > 1

O(n!) Orden Factorial

Analisis y Diseno de Algoritmos Notacion Asintotica 3/29

Analisis y Diseno de Algoritmos Notacion Asintotica 4/29

Analisis y Diseno de Algoritmos Notacion Asintotica 5/29

Analisis y Diseno de Algoritmos Notacion Asintotica 6/29

Analisis y Diseno de Algoritmos Notacion Asintotica 7/29

Analisis y Diseno de Algoritmos Notacion Asintotica 8/29

Notacion Asintotica

Notacion Asintotica

El interes principal del analisis y diseno de algoritmos radica ensaber como crece el tiempo de ejecucion, cuando el tamano dela entrada crece. Esto es la eficiencia asintotica del algoritmo.Se denomina asintotica porque analiza el comportamiento delas funciones en el lmite, es decir su tasa de crecimiento(infinito).

Analisis y Diseno de Algoritmos Notacion Asintotica 9/29

Notacion Asintotica 2

Notacion Asintotica

Se describe por medio de una funcion cuyo dominio sonlos numeros naturales, estimado a partir de tiempo deejecucion de algoritmos en base a la longitud de laentrada.

Se consideran las funciones asintoticamente no negativas.

Captura el comportamiento de la funcion para valoresgrandes de n (entrada).

Los tres tipos de notacion mas usados son O-grande,-grande y .

Analisis y Diseno de Algoritmos Notacion Asintotica 10/29

O-Grande

O-Grande

Es el metodo mas usado para expresar la complejidad de unalgoritmo. Este denota el lmite o cota superior de la funcionde complejidad. Para una funcion dada g(n), la expresionO(g(n)) (se lee como O grande de g de n), representa elsiguiente conjunto de funciones:

O(g(n)) = f (n): existen constantes positivas c y n0 talque 0 f (n) g(n) para todas n > n0

Podemos escribir f (n) O(g(n)) porque O(g(n)) es unconjunto, pero es conveniente escribirlo as f (n) = O(g(n))

Analisis y Diseno de Algoritmos Notacion Asintotica 11/29

Analisis y Diseno de Algoritmos Notacion Asintotica 12/29

O-Grande: Propiedades

O-Grande: Propiedades

limxf (x)g(n) < f (n) O(g(n)) g(n) O(f (n))

limxf (x)g(n) 0 f (n) O(g(n)) g(n) / O(f (n))

limxf (x)g(n) f (n) / O(g(n)) g(n) O(f (n))

O(f (n)) + O(g(n)) O(max(f (n), g(n))O(c f (n)) O(f (n))O(f (n)) O(g(n)) O(f (n) g(n))f (n) = am nm + am1 nm1 + . . . + a1 n + a0 O(nm)

Analisis y Diseno de Algoritmos Notacion Asintotica 13/29

O-Grande: Ejemplo

O-Grande: Ejemplo

3n2 100n + 6 = O(n2) ?

Analisis y Diseno de Algoritmos Notacion Asintotica 14/29

Analisis y Diseno de Algoritmos Notacion Asintotica 15/29

Analisis y Diseno de Algoritmos Notacion Asintotica 16/29

O-Grande: Ejemplo

O-Grande: Ejemplo

3n2 100n + 6 = O(n3) ?

Analisis y Diseno de Algoritmos Notacion Asintotica 17/29

Analisis y Diseno de Algoritmos Notacion Asintotica 18/29

O-Grande: Ejemplo

O-Grande: Ejemplo

3n2 100n + 6 = O(n) ?

Analisis y Diseno de Algoritmos Notacion Asintotica 19/29

Analisis y Diseno de Algoritmos Notacion Asintotica 20/29

Omega-Grande

GrandeEsta notacion es el inverso de la O-grande. Es usada paraexpresar la cota inferior. Para una funcion dada g(n), laexpresion (g(n)) (se lee como grande de g de n),representa el siguiente conjunto de funciones:

(g(n)) = f (n): existen constantes positivas c y n0 talque 0 cg(n) f (n) para todas n > n0

Analisis y Diseno de Algoritmos Notacion Asintotica 21/29

Analisis y Diseno de Algoritmos Notacion Asintotica 22/29

Omega-Grande: Propiedades

Grande : Propiedadeslimx

f (x)g(n) < f (n) (g(n)) g(n) (f (n))

limxf (x)g(n) 0 f (n) / (g(n)) g(n) (f (n))

limxf (x)g(n) f (n) (g(n)) g(n) / (f (n))

(f (n)) + (g(n)) (max(f (n), g(n))(c f (n)) (f (n))(f (n)) (g(n)) (f (n) g(n))f (n) = am nm + am1 nm1 + . . . + a1 n + a0 (nm)si am > 0

Analisis y Diseno de Algoritmos Notacion Asintotica 23/29

Omega-Grande: Ejemplo

Grande : Ejemplo3n2 100n + 6 = (n2) ?3n2 100n + 6 = (n3) ?3n2 100n + 6 = (n) ?

Analisis y Diseno de Algoritmos Notacion Asintotica 24/29

Theta-Grande

GrandeEsta notacion expresa el orden exacto o promedio. Para unafuncion dada g(n), la expresion (g(n)) (se lee como grande de g de n), representa el siguiente conjunto defunciones:

(g(n)) = f (n): existen constantes positivas c1, c2 y n0tal que 0 c1g(n) f (n) c2g(n) para todas n > n0

Una funcion f (n) puede ser escrita como f (n) = (g(n)) sihay coeficientes positivos c1 y c2 tales que f (n) puede estarentre c1g(n) y c2g(n)

Analisis y Diseno de Algoritmos Notacion Asintotica 25/29

Analisis y Diseno de Algoritmos Notacion Asintotica 26/29

Theta-Grande: Propiedades

Grande : Propiedadeslimx

f (x)g(n) < f (n) (g(n))

limxf (x)g(n) 0 f (n) O(g(n)) g(n) / (f (n))

limxf (x)g(n) f (n) (g(n)) g(n) / (f (n))

(f (n)) + (g(n)) (max(f (n), g(n))(c f (n)) (f (n))(f (n)) (g(n)) (f (n) g(n))f (n) = am nm + am1 nm1 + . . . + a1 n + a0 (nm)si am > 0

Analisis y Diseno de Algoritmos Notacion Asintotica 27/29

Theta-Grande: Ejemplo

Grande : Ejemplo3n2 100n + 6 = (n2) ?3n2 100n + 6 = (n3) ?3n2 100n + 6 = (n) ?

Analisis y Diseno de Algoritmos Notacion Asintotica 28/29

Tarea1

Tarea

De las siguientes afirmaciones indicar si es cierta/falsa junto asu demostracion as como su grafica

n2 O(n3)n3 O(n2)2(n + 1) O(2n)3n O(2n)n2 (n3)n3 (n2)2(n + 1) (2n)3n (2n)

http://rechneronline.de/function-graphs/

Analisis y Diseno de Algoritmos Notacion Asintotica 29/29