rethoricquotes: ALGORITMOS: Analise assintotica: O, Omega e Theta

Análise de Algoritmos | Livros | WWW | Dicionário | Índice

Análise assintótica: 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, valores próximos de zero. 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
n² ,   (3/2)n² ,   9999n² ,   n²/1000 ,   n²+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 N tal que f(n) ≥ 0 para todo n maior que N.
Agora podemos definir a ordem O. [Isto é uma letra O maiúscula. Segundo Knuth, trata-se do ômicron grego maiúsculo.]
Definição: Dadas funções assintoticamente não-negativas f e g, dizemos que f está na ordem O de g e escrevemos f = O(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 N tais que f(n) ≤ c·g(n) para todo n maior que N.
Exemplo: Se f(n) ≤ 9999 g(n) para todo n ≥ 1000 então f = O(g). (Cuidado: a recíproca não é verdadeira!)
Exemplo: Suponha que f(n) = 2n² + 3n + 4 e que g(n) = n². Observe que
2n² + 3n + 4   ≤   2n² + 3n² + 4n²   =   9n²
desde que n ≥ 1. Resumindo, f(n) ≤ 9·g(n) para todo n ≥ 1. Portanto, f(n) = O(g(n)).
Exemplo: Suponha que f(n) = 3 + 2/n e que g(n) = n⁰, ou seja, g(n) = 1. Então
3 + 2/n   ≤   3 + 1   =   4   =   4n⁰
desde que n ≥ 2. Resumindo, f(n) ≤ 4·g(n) para todo n ≥ 2. Portanto, f(n) = O(g(n)).
Exemplo: Suponha que f(n) = n³ e que g(n) = 200n². Não é verdade que f(n) = O(g(n)). De fato, se existissem c e N tais que f(n) ≤ c·g(n), teríamos
n   ≤   200c
para todo n ≥ N. Mas isso é absurdo!
Exercícios

Quais das conjecturas abaixo são verdadeiras? Justifique.
10n = O(n)         10n² = O(n)         10n⁵⁵ = O(2ⁿ )

É verdade que n² + 200n + 300 = O(n² ) ? Justifique.
É verdade que n² – 200n – 300 = O(n) ? Justifique.
Quais das conjecturas abaixo são verdadeiras? Justifique.
(3/2)n² + (7/2)n – 4 = O(n)          (3/2)n² + (7/2)n – 4 = O(n² )

É verdade que n³–999999n²–1000000 = O(n² ) ? Justifique.
Quais das conjecturas abaixo são verdadeiras? Justifique.
log₂n = O(log₃n)           log₃n = O(log₂n)

É verdade que   teto(lg(n)) = O(lg(n)) ? Justifique.

Ordem Omega

A expressão "f = O(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 N tais que f(n) ≥ c · g(n) para todo n maior que N.
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 O e Ω? Não é difícil verificar que f = O(g) se e somente se g = Ω(f).
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 ordem Theta e escrevemos f = Θ(g) se   f = O(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 Θ(n²):
n²   ,   (3/2)n²   ,   9999n²   ,   n²/1000   ,   n²+100n .
Exercício

Quais das conjecturas abaixo são verdadeiras? Justifique.

   (3/2)n² + (7/2)n – 4 = Θ(n²)
   9999 n² = Θ(n²)
   n²/1000 – 999n = Θ(n²)
   log₂n + 1 = Θ(log₁₀n)
   piso(lg(n)) = Ω(lg(n))

O domínio das funções

A discussão acima supõe, implicitamente, que todas as funções estão definidas no conjunto dos inteiros não negativos (0, 1, 2, 3, 4, …). Mas tudo continua funcionando se as funções estiverem definidas em algum outro domínio. Eis alguns exemplos de domínios:

inteiros maiores que 99,
potências de 2 (ou seja, 2⁰, 2¹, 2², etc.),
potências de 3/2,
números racionais maiores que 1/2.

A mesma notação O é usada para todos os domínios. Por exemplo, se f é uma função assintoticamente não-negativa definida nas potências de 2, dizer que f(n) = O(n²) é o mesmo que dizer que existe um número positivo c tal que f(n) ≤ c n² para todo n da forma 2^k com k suficientemente grande.
As mesmas observações se aplicam à notação Ω e à notação Θ.

URL of this page: http://www.ime.usp.br/~pf/analise_de_algoritmos/
Last modified: Thu Feb 12 08:41:34 BRST 2009
Paulo Feofiloff
DCC-IME-USP