Notação Assintótica - PT02

Prévia do material em texto

� Utilizada para representar o comportamento
assintótico das funções de complexidade de
tempo dos algoritmos, bem como relacionar
o comportamento das funções de
complexidade de dois algoritmos.
� Uma função g(n) domina assintoticamente
outra função f(n) se existem duas constantes
positivas c e n0 tais que, para n ≥ n0, temos
que |f(n)| ≤ c . |g(n)|.
� Considere f(n) = n e g(n) = n2.
� É fácil observar que : |n| ≤ c . |n2|
� Considerando c = 1 e n0 = 1 |n| ≤ 1 . |n2|
� Portanto g(n) domina assintoticamente f(n). No
entanto, f(n) não domina g(n), pois |n2| > c . |n|
n |n| ≤ c . |n2| (c = 1)
1 1 ≤ 1
2 2 ≤ 4
3 3 ≤ 9
4 4 ≤ 16
� Considere f(n) = (n + 1)3 e g(n) = n3.
� Considere c = 3 e n0 = 3.
� Prove que g(n) domina assintoticamente f(n).
21
 Uma função f(n) é O(g(n)), notação f(n) = O(g(n)), se existirem 
duas constantes positivas c e n0 tais que:
 f(n) ≤ c.g(n), para todo n ≥ n0;
 f(n) = O(g(n)): g(n) é o limite superior para f(n); (tempo máximo do 
algoritmo)
22
 Uma função f(n) é Ω(g(n)), notação f(n) = Ω(g(n)), se existirem 
duas constantes positivas c e n0 tais que:
 c.g(n) ≤ f(n), para todo n ≥ n0;
 f(n) = Ω(g(n)): g(n) é limite inferior para f(n) (tempo mínimo do 
algoritmo) 
23
 Uma função f(n) é Θ(g(n)), notação f(n) = Θ(g(n)), se existem 
duas constantes positivas c1, c2 e n0 tais que
 0 ≤ c1.g(n) ≤ f(n) ≤ c2.g(n), para todo n ≥ n0; 
 f(n) = Θ(g(n)): g(n) é limite assintótico para f(n); (tempo máximo e 
mínimo)
24
 Uma função f(n) é o(g(n)), notação f(n) = o(g(n)), se para 
qualquer constante c > 0, existe uma constante n0 > 0 tal 
que 0 ≤ f(n) < c.g(n), para todo n ≥ n0;
 Uma função f(n) é ω(g(n)), notação f(n) = ω(g(n)), se para 
qualquer constante c > 0, existe uma constante n0 > 0 tal 
que 0 ≤ c.g(n) < f(n), para todo n ≥ n0;
25
 Diferença entre as notações O (maiúsculo) e o 
(minúsculo):
 f(n) = O(g(n)), o limite 0 ≤ f(n) ≤ c.g(n) é válido para alguma
constante c > 0
 f(n) = o(g(n)), o limite 0 ≤ f(n) < c.g(n) é válido para toda
constante c > 0
 Mesma regra é válida para a diferença entre as notações 
Ω e ω
26
 Muitas das propriedades relacionais de números reais também 
se aplicam a comparações assintóticas. No caso das 
propriedades abaixo, suponha f(n) e g(n) assintoticamente
positivas.
1. Transitividade (válido também para O, Ω, o e ω):
f(n) = Θ(g(n)) e g(n) = Θ(h(n)) então f(n) = Θ(h(n)).
2. Reflexividade (válido também para O e Ω):
f(n) = Θ(f(n))
3. Simetria:
f(n) = Θ(g(n)) se e somente se g(n) = Θ(f(n))
4. Simetria de transposição:
f(n) = O(g(n)) se e somente se g(n) = Ω(f(n))
f(n) = o(g(n)) se e somente se g(n) = ω(f(n))
27
 Se f1(n) = O(g1(n)) e f2(n) = O(g2(n)), então f1(n) + f2(n) 
está em O(max(g1(n), g2(n))).
 Se f1(n) = O(g1(n)) e f2(n) = O(g2(n)), então f1(n).f2(n) está 
em O(g1(n).g2(n)).
28
 A seguir, são apresentadas algumas classes de 
complexidade de problemas comumente usadas
 O(1): ordem constante. As instruções são executadas um número 
fixo de vezes. Não depende do tamanho dos dados de entrada
 O(log n): ordem logarítmica. Típica de algoritmos que resolvem um 
problema transformando-o em problemas menores
 O(n): ordem linear. Em geral, uma certa quantidade de 
operações é realizada sobre cada um dos elementos de entrada
 O(1) < O(log n ) < O(n) < O(n log n ) < O(n2) < O(n3) < O(2n) < O(n!)
29
 Mais classes de problemas
 O(n log n): ordem log linear. Típica de algoritmos que trabalham 
com particionamento dos dados. Esses algoritmos resolvem um 
problema transformando-o em problemas menores, que são 
resolvidos de forma independente e depois unidos
 O(n2): ordem quadrática. Normalmente ocorre quando os dados 
são processados aos pares. Uma característica deste tipo de 
algoritmos é a presença de um aninhamento de dois comandos 
de repetição
 O(1) < O(log n ) < O(n) < O(n log n ) < O(n2) < O(n3) < O(2n) < O(n!)
30
 Mais classes de problemas
 O(n3): ordem cúbica. É caracterizado pela presença de três 
estruturas de repetição aninhadas
 O(2n): ordem exponencial. Geralmente ocorre quando se usa uma 
solução de força bruta. Não são úteis do ponto de vista prático
 O(n!): ordem fatorial. Geralmente ocorre quando se usa uma 
solução de força bruta. Não são úteis do ponto de vista prático. 
Possui um comportamento muito pior que o exponencial
 O(1) < O(log n ) < O(n) < O(n log n ) < O(n2) < O(n3) < O(2n) < O(n!)