ClubEnsayos.com - Ensayos de Calidad, Tareas y Monografias
Buscar

Notaciones Asintóticas

Alexander Zavaleta CalderonApuntes22 de Octubre de 2018

1.455 Palabras (6 Páginas)130 Visitas

Página 1 de 6
  1. ¿Cuáles de las siguientes afirmaciones son verdaderas? Demuestre sus respuestas. a. 𝒏𝟐 ∈ 𝑶(𝒏𝟑)

b.   𝒏𝟐  ∈ 𝛀(𝒏𝟑)

c.        𝟐𝒏  ∈ 𝜽(𝒏𝟐)

d. 𝒏! ∈ 𝜽((𝟐𝒏 + 𝟏)!)

e.        𝟑𝒏𝟑 + 𝟐𝒏𝟐 ∈ 𝑶(𝒏𝟑)

f.        𝟑𝒏 ∈ 𝑶(𝟐𝒏)

g. 𝒏𝟑 + 𝟐𝒏𝟐 ∈ 𝛀(𝒏𝟑)

h. 𝟑𝒏𝟑 𝑛𝑜 ∈ 𝑶(𝟐𝒏)

es CIERTO pues[pic 2]


𝒏𝟐

[pic 3]

𝐥𝐢𝐦 (  𝟑) = 𝟎

𝒏→∞    𝒏

[pic 4]

Consideramos 𝑓(𝑛) = 𝑛2 y 𝑔(𝑛) = 𝑛3 y aplicamos el teorema del límite como sigue:

lim (


𝑛2

3) = lim ([pic 5]


2 ∗ 𝑛        2

2) = lim ([pic 6][pic 7]


) = 0

𝑛→∞ 𝑛


𝑛→∞


3 ∗ 𝑛


𝑛→∞


6 ∗ 𝑛

Esto significa que 𝒏𝟑 crece más rápido que 𝒏𝟐. En este caso, podríamos afirmar que es FALSO.

es FALSO pues[pic 8]


𝒏𝟐        .

[pic 9]

𝐥𝐢𝐦 (    ) = 𝟎[pic 10]

𝒏→∞

 𝒏!  𝜽((𝟐𝒏 + 𝟏)!)

En este caso, no es posible usar L’Hôpital por ser una factorial. Por lo que usaremos un método distinto. Siendo este el siguiente:

𝒏!

= 𝐥𝐢𝐦[pic 11]

𝒏→∞ (𝟐 ∗ 𝒏 + 𝟏)!

= 𝐥𝐢𝐦[pic 12]


(𝒏) ∗ (𝒏 − 𝟏) ∗ … ∗ 𝟏


= 𝟎

𝒏→∞ (𝟐 ∗ 𝒏 + 𝟏) ∗ (𝟐 ∗ 𝒏) ∗ (𝟐 ∗ 𝒏 − 𝟏) ∗ … ∗ (𝒏) ∗ (𝒏 − 𝟏) ∗ … ∗ 𝟏

Vemos que al desarrollar el factorial podemos eliminar muchos valores. En este caso,        el        resultado        es        0,        ya        que        𝒈(𝒏)        crecerá        más        rápido        que

𝒇(𝒏).

Por consiguiente, es FALSO porque 𝒇(𝒏) ∉ 𝛀(𝒈(𝒏)). Por la tanto, 𝒇(𝒏)) ∉

𝛉(𝒈(𝒏)).

𝟑𝒏𝟑 + 𝟐𝒏𝟐  𝑶(𝒏𝟑)

Sean 𝒏𝟎 = 𝟎 y 𝒄 = 𝟓.

Entonces, para 𝒏 ≥ 𝟎, existe 𝒄 = 𝟓, tal que

𝟑𝒏𝟑 + 𝟐𝒏𝟐 ≤ 𝟓𝒏𝟑

Es CIERTO.

es FALSO pues[pic 13]


𝟐𝒏

𝐥𝐢𝐦 ( 𝒏) = 𝟎[pic 14]

𝒏→∞    𝟑

[pic 15]

Sean 𝒄 = 𝟏 , entonces


𝑻(𝒏) ≥ 𝒄 𝒏𝟑 , para 𝒏 = 𝟎, 𝟏, 𝟐, …

Es CIERTO.

𝟑𝒏𝟑 ∉ 𝑶(𝟐𝒏) es FALSO pues 𝐥𝐢𝐦 ( 𝟐𝒏 ) = .[pic 16]

𝒏→∞


𝟑𝒏𝟑

  1. Comparar los siguientes pares de funciones usando la notación asintótica. En cada caso establecer si f(n) ϵ O(g(n)), f(n) ϵ Ω(g(n)), f(n) ϵ θ(g(n)).

f(n)        g(n)

10−3𝑛4        10−3𝑛3

𝑛2        𝑛 𝑙𝑜𝑔 𝑛

𝑙𝑜𝑔(𝑛)        𝑙𝑜𝑔(𝑙𝑜𝑔 𝑛)

22𝑛        𝑛2𝑛

100𝑛 + 𝑙𝑜𝑔10𝑛        𝑛 + (𝑙𝑜𝑔 𝑛)2

𝑙𝑜𝑔(𝑛)        𝑙𝑜𝑔 𝑛2

𝑛𝑙𝑜𝑔 𝑛        𝑛

[pic 17]

10−3𝑛4

lim[pic 18]

𝑛→∞ 10−3


𝑛3 = ∞

Por muy alta que se la constante multiplicativa de 𝑔(𝑛) nunca superará a 𝑓(𝑛).

  • 𝑓 = Ω(𝑔) indica que, al comparar dos funciones 𝑓(𝑛) y 𝑔(𝑛) , 𝑓(𝑛) no está dominada por 𝑔(𝑛).

Por lo tanto, el caso que coincide con la función anterior es 𝒇(𝒏) = 𝛀(𝒈(𝒏)) y la función se puede escribir como 𝟏𝟎−𝟑𝒏𝟒 = 𝛀 𝟏𝟎−𝟑𝒏𝟑

[pic 19]

lim[pic 20][pic 21]


𝑛2

= ∞[pic 22]

𝑛→∞ 𝑛  log 𝑛

Por muy alta que se la constante multiplicativa de 𝑔(𝑛) nunca superará a 𝑓(𝑛).

  • 𝑓 = Ω(𝑔) indica que, al comparar dos funciones 𝑓(𝑛) y 𝑔(𝑛) , 𝑓(𝑛) no está dominada por 𝑔(𝑛).

Por lo tanto, el caso que coincide con la función anterior es 𝒇(𝒏) = 𝛀(𝒈(𝒏)) y la función se puede escribir como 𝒏𝟐 = 𝛀 𝒏 𝒍𝒐𝒈 𝒏.

 𝒇(𝒏) = 𝒍𝒐𝒈 𝒏 , 𝒈(𝒏) = 𝒍𝒐𝒈(𝒍𝒐𝒈 𝒏)

lim[pic 23]


log 𝑛

= ∞

𝑛→∞ log(log 𝑛)


Por muy alta que se la constante multiplicativa de 𝑔(𝑛) nunca superará a 𝑓(𝑛).

  • 𝑓 = Ω(𝑔) indica que, al comparar dos funciones 𝑓(𝑛) y 𝑔(𝑛) , 𝑓(𝑛) no está dominada por 𝑔(𝑛).

Por lo tanto, el caso que coincide con la función anterior es 𝒇(𝒏) = 𝛀(𝒈(𝒏)) y la función se puede escribir como 𝐥𝐨𝐠 𝒏 = 𝛀 𝐥𝐨𝐠(𝐥𝐨𝐠 𝒏).

[pic 24]

lim


22𝑛

2𝑛 = 0[pic 25]

𝑛→∞ 𝑛

Se sabe que 𝑔(𝑛) crece exponencialmente en comparación a 𝑓(𝑛). Sería su cota superior.

Por lo tanto, el caso que coincide con la función anterior es 𝒇(𝒏) = 𝐎(𝒈(𝒏)) y la función se puede escribir como 𝟐𝟐𝒏 = 𝐎 (𝒏𝟐𝒏).

...

Descargar como (para miembros actualizados) txt (9 Kb) pdf (438 Kb) docx (49 Kb)
Leer 5 páginas más »
Disponible sólo en Clubensayos.com