Funciones Asimptoticas

Funciones Asimpt´ oticas Carl os Albert o Cast a˜ no 9 de junio de 2011 Las funcio nes asimpt ´ oticas son funciones que sirven para determinar la relaci´ on entre dos funciones con respecto a su crecimiento, en base a la longitud de la entrada. f (x) : N −→ R + Se denominan asimpt´ oticas porque analizan el comportamiento de las funciones en el limite, es decir, su taza de crecimiento. Existen diferentes notaciones para dichas funciones, que a continuación se ilustrarán. 1. Notación O (.) O (g(n)) = f (n) : ∃c ∈ R + ∃n 0 ∈ N |f (n) cg(n)∀n n 0 Determina una cota superior en la tasa de crecimiento de una funci´ on, dentro de un factor constante. Ejemplo: 6n 3 ∈ O (n 3 ) ya que se cumple la definici´ on con c = 6, n 0 = 1 3log n ∈ O (n) ya que se cumple la definici´ on con c = 1,n 0 = 4 2 n ∈ O (n!) 2. Notación Ω(.) Ω(g(n)) = f (n) : ∃c ∈ R + , ∃n 0 ∈ N |f (n) cg(n)|n n 0 Determina una cota inferior en la tasa de crecimiento de una funci´ on, dentro de un factor constante. Ejemplo: 1

Upload
carlos-alberto
Category

Documents
view
55
download
0

Embed Size (px):

Transcript of Funciones Asimptoticas

5/12/2018 Funciones Asimptoticas - slidepdf.com

http://slidepdf.com/reader/full/funciones-asimptoticas 1/3

Funciones AsimptoticasCarlos Alberto Castano

9 de junio de 2011

Las funciones asimptoticas son funciones que sirven para determinar la relacion entre dos funciones con

respecto a su crecimiento, en base a la longitud de la entrada.

f (x) : N −→ R+

Se denominan asimptoticas porque analizan el comportamiento de las funciones en el limite, es decir, sutaza de crecimiento.

Existen diferentes notaciones para dichas funciones, que a continuacion se ilustraran.

1. Notacion O (.)

O (g(n)) = f (n) : ∃c ∈ R+∃n0 ∈ N |f (n) cg(n)∀n n0

Determina una cota superior en la tasa de crecimiento de una funcion, dentro de un factor constante.

Ejemplo:

6n3 ∈ O (n3) ya que se cumple la definicion con c = 6, n0 = 1

3logn ∈ O (n) ya que se cumple la definicion con c = 1, n0 = 4

2n ∈ O (n!)

2. Notacion Ω(.)

Ω(g(n)) = f (n) : ∃c ∈ R+, ∃n0 ∈ N |f (n) cg(n)|n n0

Determina una cota inferior en la tasa de crecimiento de una funcion, dentro de un factor constante.

Ejemplo:

5/12/2018 Funciones Asimptoticas - slidepdf.com

http://slidepdf.com/reader/full/funciones-asimptoticas 2/3

6n3 ∈ Ω(n3) ya que se cumple la definicion con c = 1, n0 = 1

1/3n ∈ Ω(logn) ya que se cumple la definicion con c = 1/3, n0 = 1

2n ∈ Ω(n!)

3. Notacion Θ(.)

Θ(g(n)) = f (n) : ∃c, d ∈ R+∃n0 ∈ N |cg(n) f (n) dg(n)|n n0

Determina una cota superior e inferior en la tasa de crecimiento de una funcion, dentro de un factor constante.

Ejemplo:

6n3 ∈ Θ(n3) ya que se cumple la definicion con c = 6, d = 6, n0 = 1

1/3n ∈ Θ(n) ya que se cumple la definicion con c = 1/5, d = 1, n0 = 1

3n2 ∈ Θ(n2)

En conclusion la definicion de las funciones anteriores, en el contexto de la computaci on seran utiles paradeterminar la forma en que un algoritmo puede comportarse dependiendo del crecimiento de su entrada,esta medicion puede hacerse en funcion del tiempo o del espacio, la primera se refiere al tiempo en que tarda

un algoritmo en ejecutarse y la segunda al espacio en memoria que ocupar a el mismo, esto servira comobase para posteriormente poder determinar en que casos un algoritmo puede ser mas eficiente que otro conrespecto a los factores ya mencionados.