Notación asintótica

Vista previa del material en texto

Crecimiento de funciones 
Análisis asintótico de algoritmos 
wearcaya@unap.edu.pe 
A considerar 
• Crecimiento de funciones 
• Notación asintótica O 
• Notación asintótica Ω 
• Notación asintótica Θ 
• Uso y relación entre las notaciones O, Ω, Θ 
• Notaciones o, ω 
• Reglas 
wearcaya@unap.edu.pe 
https://www.reddit.com/r/math/comments/cz0ll/ 
http://www.cube20.org/ 
wearcaya@unap.edu.pe 
https://www.reddit.com/r/math/comments/cz0ll/
Crecimiento de funciones 
Análisis asintótico de algoritmos 
• Generalmente basada en una descripción de 
seudocódigo ( en vez de código fuente en un 
determinado lenguaje) 
• Caracteriza la complejidad de tiempo como una 
función del tamaño de entrada n. 
• Un algoritmo asintóticamente más eficiente es la mejor 
alternativa para todas las entradas, excepto para las de 
tamaño pequeño 
• Permite analizar la complejidad de un algoritmo 
independiente del sistema computacional utilizado. 
wearcaya@unap.edu.pe 
Notación asintótica O (big-o) 
• Para una función dada g(n), denotamos O(g(n)) al conjunto de 
funciones: 
 O(g(n)) = { f(n): existen constantes positivas c y n0 tales que 
0≤f(n) ≤ c·g(n) para todo n ≥ n0 } 
• Una función f(n) pertenece al conjunto O(g(n)) si existe una 
constante positiva c de forma que ella pueda estar limitada 
por c·g(n) para un valor de n suficientemente grande. 
• Podemos decir que f(n) ϵ O(g(n)) pero generalmente se 
escribe f(n)=O(g(n)) (abuso de la notación de igualdad, no es 
simétrico) 
wearcaya@unap.edu.pe 
Notación asintótica: O (big-o) 
Tomado de Cormen 2009 
•Para todos los valores de n a la derecha 
de n0, el valor de f(n) reside en c·g(n) o 
debajo de él. 
•Formalmente, la función g(n) es un 
límite asintótico superior para f(n) 
•Ejemplo: 2n2 = O(n3) 
Podemos pensar en esa ecuación 
como si fuera 
 2n2 ≤ O(n3) o 
 2n2 ϵ O(n3) 
La tasa de crecimiento de 2n2 es 
menor o igual a la tasa de n3 
wearcaya@unap.edu.pe 
Ejemplos de la notación O 
• Ejemplo 1: 2n + 10 es O(n) 
– Podemos realizar una manipulación para encontrar c y n0: 
 2n + 10 ≤ c·n 
 c·n – 2n ≥ 10 
 (c – 2) n ≥ 10 
 n ≥ 10/ (c – 2) 
 esta afirmación es válida para c = 3 y n0=10 
 
• Ejemplo 2: n2 no es O(n) 
– Supongamos que sí es, entonces tendría que haber la constante c que 
siempre sea mayor o igual a n a partir de un valor n0: 
 n2 ≤ c·n  n ≤ c 
– Ésto último es imposible por tanto por el principio de contradicción se 
acepta lo contrario. 
wearcaya@unap.edu.pe 
• Ejemplo 3: 3n3+ 20n2 + 5 es O(n3) 
– Se necesita encontrar c > 0 y n0 ≥1 tal que 
 3n3+ 20n2 + 5 ≤ c·n3 para todo n ≥ n0 
– Como 3n3+ 20n2 + 5 ≤ (3+20+5)·n3 podemos tomar 
c=28 y cualesquiera n0 > 1 (24+80+5)<224 (n=2) 
• Ejemplo 4: 3 log n + 5 es O(log n) 
– Se necesita encontrar algun c > 0 y n0 ≥1 tal que 
 3 log n + 5 ≤ c·log n para todo n ≥ n0 
– Notar que 3 · log n + 5 ≤ (3 + 5)·log n si n > 1 
(log 1 = 0) 
– Basta tomar por ejemplo c = 8 y cualesquiera n0 ≥ 2 
wearcaya@unap.edu.pe 
• Ejemplo 5: 2n+2 es O(2n) 
– Es necesario c > 0 y n0≥1 tales que 
2n+2 ≤ c · 2n para todo n ≥ n0 
– Notar que 2n+2 = 22 · 2n =4 · 2n 
– Luego basta tomar por ejemplo c =4 y cualesquiera 
n0 
 
wearcaya@unap.edu.pe 
Notacion de igualdad para conjunto de funciones: O 
• La igualdad en este caso es utilizada en el sentido de 
representatividad y puede ser leída como ‘’es’’ 
• Un conjunto en una fórmula representa una función 
anónima en aquel conjunto. 
• Ejemplo 6: 
 f(n) = n3 + O(n2) 
 significa que existe un h(n) ϵ O(n2) de forma que 
 f(n) = n3 + h(n) 
• Ejemplo 7: 
 n2 + O(n) = O(n2) 
 significa que para cualquier f(n) ϵ O(n) existe h(n) ϵ O(n2) 
de forma que n2 + f(n) = h(n) 
 
 
wearcaya@unap.edu.pe 
Trabajo grupal 
wearcaya@unap.edu.pe 
• Todos deben revisar: iteración funcional 
wearcaya@unap.edu.pe