Buscar

Notação assintótica

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você viu 3, do total de 4 páginas

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Prévia do material em texto

Análise de Algoritmos | Aulas | Bibliografia | WWW | Dicionário | Índice
Análise assintótica: ordens O, Omega e Theta
Ao ver uma expressão como n+10 ou n²+1, a maioria das pessoas pensa automaticamente em
valores pequenos de n. A análise de algoritmos faz exatamente o contrário: ignora os valores
pequenos e concentra-se nos valores enormes de n. Para valores enormes de n, as funções
n2 , (3/2)n2 , 9999n2 , n2/1000 , n2+100n , etc.
crescem todas com a mesma velocidade e portanto são todas “equivalentes”. Esse tipo de
matemática, interessado somente em valores enormes de n, é chamado assintótico. Nessa
matemática, as funções são classificadas em “ordens” (como as ordens religiosas da Idade Média);
todas as funções de uma mesma ordem são “equivalentes”. As cinco funções acima, por exemplo,
pertencem à mesma ordem.
Veja o verbete Big O notation na Wikipedia.
Ordem O
Convém restringir a atenção a funções assintoticamente não negativas, ou seja, funções f tais que
f(n) ≥ 0 para todo n suficientemente grande. Mais explicitamente: f é assintoticamente não
negativa se existe n0 tal que f(n) ≥ 0 para todo n maior que n0. Agora podemos definir a
ordem Ο. [Esta letra é um O maiúsculo. Ou melhor, um ômicron grego maiúsculo, conforme
Knuth.]
DEFINIÇÃO: Dadas funções assintoticamente não negativas f e g, dizemos que f está
na ordem Ο de g e escrevemos f = Ο(g) se f(n) ≤ c · g(n) para algum c positivo e
para todo n suficientemente grande. Em outras palavras, existe um número positivo
c e um número n0 tais que f(n) ≤ c · g(n) para todo n maior que n0.
(A notação “Ο(∗)” empregada nesta definição é conhecida como notação assintótica ou notação de
Landau.)
Exemplo 1: Se f(n) ≤ 9999 g(n) para todo n ≥ 1000 então f = Ο(g). (Cuidado: a recíproca não é
verdadeira!)
Exemplo 2: Suponha que f(n) = 2n² + 3n + 4 e g(n) = n². Observe que
2n2 + 3n + 4 ≤ 2n2 + 3n2 + 4n2 = 9n2
desde que n ≥ 1. Resumindo, f(n) ≤ 9 g(n) para todo n ≥ 1. Portanto, f(n) = Ο(g(n)).
Exemplo 3: Suponha que f(n) = 3 + 2/n e que g(n) = n0, ou seja, g(n) = 1. Então
3 + 2/n ≤ 3 + 1 = 4 = 4n0
desde que n ≥ 2. Resumindo, f(n) ≤ 4 g(n) para todo n ≥ 2. Portanto, f(n) = Ο(g(n)).
Exemplo 4: Suponha que f(n) = n3 e que g(n) = 200n2. Não é verdade que f(n) = Ο(g(n)). De fato,
Notação assintótica http://www.ime.usp.br/~pf/analise_de_algoritmos/aulas/Oh.html
1 de 4 14/03/2015 13:16
se existissem c e n0 tais que f(n) ≤ c g(n), teríamos n ≤ 200c para todo n ≥ n0. Mas isso é
absurdo!
Exercícios
Faz sentido dizer “f(n) está em Ο(n²) para n ≥ 4”?1. 
Fica bem dizer “f(n) está em Ο(n²) com c = 12 e n0 = 4”?2. 
Critique a seguinte definição alternativa da classe Ο: “Dizemos que f está em Ο(g) se existem
números positivos c, n0 e n ≥ n0 tais que f(n) ≤ c g(n).”
3. 
Critique a seguinte definição alternativa da classe Ο: “Dizemos que f está em Ο(g) se existe
um número natural n0 tal que f(n) ≤ c g(n) para algum número positivo c e para todo n ≥ n0.”
4. 
[INTERESSANTE] A cláusula “n suficientemente grande” na definição da classe Ο é supérflua
quando estamos lidando com funções estritamente positivas. De fato, suponha que f é Ο(g) e
g(n) > 0 para todo n natural e mostre que existe um número positivo c′ tal que f(n) ≤ c′ g(n)
para todo n natural.
5. 
Critique o seguinte raciocínio: “A derivada de 4n2+2n é 8n+2. A derivada de n2 é 2n. Como
8n+2 > 2n, podemos concluir que 4n2+2n cresce mais que n2 e portanto 4n2+2n não é Ο(n2).” 
Critique o seguinte raciocínio: “A derivada de 4n2+2n é 8n+2. A derivada de 9n2 é 18n. 
Como 8n+2 ≤ 18n para n ≥ 1, podemos concluir que 4n2+2n é Ο(9n2).”
6. 
É verdade que 10n = Ο(n) ? É verdade que 10n2 = Ο(n) ? É verdade que 10n55 = Ο(2n) ?7. 
É verdade que n2 + 200n + 300 = Ο(n2) ? 8. 
É verdade que n2 − 200n − 300 = Ο(n) ?9. 
É verdade que (3/2)n2 + (7/2)n − 4 = Ο(n) ? É verdade que (3/2)n2 + (7/2)n − 4 = Ο(n2) ?10. 
É verdade que n3−999999n2−1000000 = Ο(n2) ?11. 
Seja (nk) o número de combinações de n objetos tomados k a k. Mostre (
n
2) = Ο(n
2). Mostre
que (n3) = Ο(n
3). É verdade que, para qualquer número natural k ≤ n, tem-se (nk) = Ο(n
k) ? 
12. 
É verdade que 2n+1 está em Ο(2n) ? É verdade que 3n está em Ο(2n) ?13. 
É verdade que log2n = Ο(log3n) ? É verdade que log3n = Ο(log2n) ?14. 
É verdade que ⌈lg n⌉ = Ο(lg n) ? (Veja as definições de teto e lg no dicionário.)15. 
Prove que n = Ο(2n). (Sugestão: use indu ção matemática para provar que n ≤ 2n para todo n
suficientemente grande.)
16. 
Prove que lg n está em Ο(n).17. 
Prove que n é Ο(2n/4). (Sugestão: use indução matemática para provar que n ≤ 2n/4 para
todo n suficientemente grande.)
18. 
Prove que 4 lg n está em Ο(n).19. 
Prove que 100 lg n − 10n + 2n lg n está em Ο(n lg n).20. 
Ordem Omega
Notação assintótica http://www.ime.usp.br/~pf/analise_de_algoritmos/aulas/Oh.html
2 de 4 14/03/2015 13:16
A expressão “f = Ο(g)” tem o mesmo sabor que “f ≤ g”. Agora precisamos de um conceito que
tenha o sabor de “f ≥ g”.
DEFINIÇÃO: Dadas funções assintoticamente não negativas f e g, dizemos que f está na
ordem Omega de g e escrevemos f = Ω(g) se f(n) ≥ c · g(n) para algum c positivo e para
todo n suficientemente grande. Em outras palavras, existe um número positivo c e um
número n0 tais que f(n) ≥ c · g(n) para todo n maior que n0.
Exemplo: Se f(n) ≥ g(n)/100000 para todo n ≥ 888 então f = Ω(g). (Cuidado: a recíproca não é
verdadeira!)
Qual a relação entre Ο e Ω? Não é difícil verificar que f = Ο(g) se e somente se g = Ω(f).
Exercício
Seja (nk) o número de combinações de n objetos tomados k a k. Mostre (
n
2) = Ω(n
2). Mostre
que (n3) = Ω(n
3). É verdade que, para qualquer número natural k ≤ n, tem-se (nk) = Ω(n
k) ? 
1. 
Prove que 100 lg n − 10n + 2n lg n está em Ω(n lg n). 2. 
É verdade que 2n+1 está em Ω(2n) ? É verdade que 3n está em Ω(2n) ?3. 
Ordem Theta
Além dos conceitos que têm o sabor de “f ≤ g” e de “f ≥ g”, precisamos de um que tenha o sabor de
“f = g”.
DEFINIÇÃO: Dizemos que f e g estão na mesma e escrevemos f = Θ(g) se f = Ο(g) e 
f = Ω(g). Trocando em miúdos, f = Θ(g) significa que existe números positivos c e d tais
que c g(n) ≤ f(n) ≤ d g(n) para todo n suficientemente grande.
Exemplo: As funções abaixo pertencem todas à ordem Θ(n2):
n2 , (3/2)n2 , 9999n2 , n2/1000 , n2+100n .
Exercício
Quais das conjeturas abaixo são verdadeiras?
 (3/2)n2 + (7/2)n3 − 4 = Θ(n2)a. 
 9999 n2 = Θ(n2)b. 
 n2/1000 − 999n = Θ(n2)c. 
 log2n + 1 = Θ(log10n)d. 
 ⌊lg n⌋ = Ω(lg n) (confira a definição de piso)e. 
1. 
Onde as funções estão definidas?
A discussão acima supõe, implicitamente, que todas as funções estão definidas no conjunto dos
números naturais. Mas tudo continua funcionando se as funções estiverem definidas em algum
outro domínio. Eis alguns exemplos de domínios:
Notação assintótica http://www.ime.usp.br/~pf/analise_de_algoritmos/aulas/Oh.html
3 de 4 14/03/2015 13:16
números naturais maiores que 99,
potências inteiras de 2 (ou seja, 20, 21, 22, etc.),
potências inteiras de 1½,
números racionais maiores que ½.
A mesma notação Ο é usada para todos os domínios. Por exemplo, se f é uma função
assintoticamente não negativa definida nas potências inteiras de 2, dizer que f(n) = Ο(n2) é o
mesmo que dizer que existe um número positivo c tal que f(n) ≤ c n2 para todo n da forma 2k com k
suficientemente grande.
As mesmas observações se aplicam à notação Ω e à notação Θ.
Veja aula em video sobre notação assintótica no AcademicEarth
Lista de fórmulas "Know Thy Complexities": complexidade dealgoritmos básicos
URL of this site: http://www.ime.usp.br/~pf/analise_de_algoritmos/
Last modified: Mon Nov 3 07:20:22 BRST 2014
Paulo Feofiloff
Departamento de Ciência da Computação
Instituto de Matemática e Estatística da USP
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Notação assintótica http://www.ime.usp.br/~pf/analise_de_algoritmos/aulas/Oh.html
4 de 4 14/03/2015 13:16

Outros materiais