NotacionA

Análisis de algoritmos
Tema 05: Notación asintótica
Solicitado: Tarea 04: Graficación de ordenes de complejidad
M. en C. Edgardo Adrián Franco Martínez
http://www.eafranco.com
edfrancom@ipn.mx
@edfrancom

edgardoadrianfrancom

1

• Introducción
• Asíntota
• Dominio asintótico
• Ejemplo 1
• Ejemplo 2

• Dominio asintótico a la función complejidad
• Notación de orden (Cotas asintóticas)

Análisisde algoritmos
05 Notación asintótica
Prof. Edgardo Adrián Franco Martínez

Contenido

• Cota Superior: Notación 𝑂 mayúscula
• Cota Superior no ajustada: Notación 𝑜 minúscula
• Diferencia entre 𝑂 y 𝑜

• Cota Inferior: Notación Ω
• Cota ajustada asintótica: Notación Θ

• Observaciones sobre las cotas asintóticas
• Ordenes de complejidad (Cota superior)
• Tarea 05: Graficación de ordenes decomplejidad

2

• El costo para obtener una solución de un problema concreto
aumenta con el tamaño 𝐧 del problema.
• Para valores suficientemente pequeños de 𝑛, el coste de
ejecución de cualquier algoritmo es pequeño, incluyendo los
algoritmos ineficientes; i.e. la elección del algoritmo no es un
problema crítico para problemas de pequeño tamaño.
• El análisis de algoritmos se realiza para valores grandesde
𝒏. Para lo cual se considera el comportamiento de sus
funciones de complejidad para valores grandes de 𝑛, es decir
se estudia el comportamiento asintótico de 𝑓(𝑛), lo cuál
permite conocer el comportamiento en el límite del coste
cuando 𝑛 crece.

Análisis de algoritmos
05 Notación asintótica
Prof. Edgardo Adrián Franco Martínez

Introducción

3

• Se le llama asíntota a una línea recta que seaproxima
continuamente a otra función o curva; es decir que la
distancia entre las dos tiende a cero, a medida que se
extienden indefinidamente.
• También se puede decir que es la curva la que se aproxima
continuamente a la recta; o que ambas presentan un
comportamiento asintótico.

Análisis de algoritmos
05 Notación asintótica
Prof. Edgardo Adrián Franco Martínez

Asíntota

4

• Sean 𝑓 y 𝑔funciones de ℕ a ℝ. Se dice que 𝑓 domina
asintóticamente a 𝑔 o que 𝑔 es dominada asintóticamente
por 𝑓; si ∃𝑘 ≥ 0 𝑦 𝑚 ≥ 0 tales que:
𝑔(𝑛) ≤ 𝑚 𝑓 𝑛 , ∀𝑛 ≥ 𝑘
• En otros términos, podemos decir que si una función domina a
otra, su velocidad de crecimiento es mayor o igual.
• Puesto que las funciones complejidad son funciones con dominio
ℕ(𝑛ú𝑚𝑒𝑟𝑜𝑠 𝑛𝑎𝑡𝑢𝑟𝑎𝑙𝑒𝑠), y contradominio ℝ 𝑛ú𝑚𝑒𝑟𝑜𝑠 𝑟𝑒𝑎𝑙𝑒𝑠;
los conceptosy las propiedades de dominio asintótico
proporcionan una manera conveniente de expresarlas y
manipularlas.

Análisis de algoritmos
05 Notación asintótica
Prof. Edgardo Adrián Franco Martínez

Dominio asintótico

5

Análisis de algoritmos
05 Notación asintótica
Prof. Edgardo Adrián Franco Martínez

• Gráficas de las funciones 𝑚 𝑓(𝑛) y 𝑔(𝑛) ,donde 𝑘 es el valor a
partir del cual 𝑚 𝑓(𝑛) es mayor que𝑔(𝑛) y esta relación de
magnitud se conserva conforme 𝑛 crece.

6

• Ejemplo 1: Sean 𝑓 𝑛 = 𝑛 y 𝑔 𝑛 = 𝑛3 funciones de ℕ a ℝ.
i.

Demostrar que 𝑔 domina asintóticamente a 𝑓
∃𝑚 ≥ 0, 𝑘 ≥ 0 𝑡𝑎𝑙𝑒𝑠 𝑞𝑢𝑒 𝑓(𝑛) ≤ 𝑚 𝑔 𝑛 , ∀𝑛 ≥ 𝑘

ii.

Demostrar que 𝑓 no domina asintóticamente a 𝑔
¬(∃𝑚 ≥ 0, 𝑘 ≥ 0 𝑡𝑎𝑙𝑒𝑠 𝑞𝑢𝑒 𝑔 𝑛

≤ 𝑚 𝑓 𝑛 , ∀𝑛 ≥ 𝑘)

Análisis de algoritmos
05 Notación asintótica
Prof. Edgardo Adrián FrancoMartínez

Dominio asintótico (Ejemplo 1)

7

• Ejemplo 1: Sean 𝑓 𝑛 = 𝑛 y 𝑔 𝑛 = 𝑛3 funciones de ℕ a ℝ.
Demostrar que 𝑔 domina asintóticamente a 𝑓
∃𝑚 ≥ 0, 𝑘 ≥ 0 𝑡𝑎𝑙𝑒𝑠 𝑞𝑢𝑒 𝑓(𝑛) ≤ 𝑚 𝑔 𝑛 , ∀𝑛 ≥ 𝑘
• Substituyendo 𝑓(𝑛) y 𝑔(𝑛)
𝑛 ≤ m 𝑛3 , ∀𝑛 ≥ 𝑘
• Si se toman 𝑚 = 1 y 𝑘 = 1, las desigualdades anteriores se cumplen,
por lo tanto, 𝑚 y 𝑘 existen, y en consecuencia 𝑔 domina
asintóticamente a 𝑓.

Análisis dealgoritmos
05 Notación asintótica
Prof. Edgardo Adrián Franco Martínez

i.

8

• Ejemplo 1: Sean 𝑓 𝑛 = 𝑛 y 𝑔 𝑛 = 𝑛3 funciones de ℕ a ℝ.
Demostrar que 𝑓 no domina asintóticamente a 𝑔
¬(∃𝑚 ≥ 0, 𝑘 ≥ 0 𝑡𝑎𝑙𝑒𝑠 𝑞𝑢𝑒 𝑔 𝑛
• Aplicando la negación se tiene

≤ 𝑚 𝑓 𝑛 , ∀𝑛 ≥ 𝑘)

∀𝑚 ≥ 0, 𝑘 ≥ 0, ∃𝑛 ≥ 𝑘 𝑡𝑎𝑙 𝑞𝑢𝑒 𝑔(𝑛) > 𝑚 𝑓(𝑛)
• Sustituyendo 𝑔 y 𝑓 en cada lado de la desigualdad
𝑛3 > 𝑚 𝑛
• Simplificando

𝑛2 > 𝑚
𝑛2 > 𝑚
𝒏>...