Comparação assintótica de funções

We want a statement about software,
not hardware.

 

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) n29999 n2n2/1000,  n2+100n,  etc.

têm todas a mesma taxa de crescimento e portanto são todas equivalentes. (A expressão têm a mesma taxa de crescimento não significa que têm a mesma derivada!) Essa matemática, interessada somente em valores enormes de n, é chamada assintótica (= asymptotic). Nessa matemática, as funções são classificadas em ordens assintóticas.

Ordem O

Em termos muito grosseiros, uma função f está na ordem Ο de uma função g se existe um número c tal que f(n) ≤ cg(n) para todo n. Mas essa definição não é muito útil porque f(n) pode ser muito maior que g(n) quando n é pequeno.

Antes de dar uma definição útil e correta do conceito de ordem Ο, 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 Ó 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 existe um número positivo c tal que  f(n) c · g(n)  para todo n suficientemente grande. Em outras palavras, se existem números positivos c e n0 tais que f(n) ≤ c · g(n) para todo n maior que n0.

A expressão f = Ο(g) é útil e poderosa porque esconde informações irrelevantes: a expressão informa o leitor sobre a relação entre f e g sem desviar sua a atenção para o valor de c e o valor de n0, que são irrelevantes.

(A notação f = Ο(g) é conhecida como notação assintótica, ou notação de Landau. O uso do = nessa notação é um abuso pois não representa igualdade no sentido usual. Quem sabe é melhor dizer f está em Ο(g) ou f é Ο(g).)

Exemplo A.  Suponha que f(n) ≥ 0 e g(n) ≥ 0 para todo n positivo. Se f(n) ≤ 9999 g(n) para todo n ≥ 1000 então f = Ο(g).

Exemplo B.  Suponha que  f(n) = 2n2 + 30n + 400  e  g(n) = n2. Então f = Ο(g), como mostraremos a seguir. Observe que para todo n positivo temos

f(n) = 2n2 + 30n + 400
   ≤  2n2 + 30n2 + 400n2
   =  432n2
   =  432 g(n) .

Resumindo: f(n) ≤ 432 g(n) para todo n ≥ 1. (Eu deveria ter começado o exemplo verificando que f e g são assintoticamente não-negativas. Omiti essa parte porque ela é óbvia.) Portanto, f = Ο(g).  

Poderíamos chegar à mesma conclusão por um caminho ligeiramente diferente: observe que para n ≥ 30 temos

2n2 + 30n + 400 ≤ 2n2 + nn + nn = 4 n2.

Resumindo: f(n) ≤ 4 g(n) para todo n ≥ 30. Portanto, f = Ο(g).

Exemplo C.  É fato que 300 + 20/n = Ο(n⁰). (Poderíamos escrever Ο(1), mas a expressão Ο(n⁰) ajuda lembrar que a variável é n.) Eis a prova desse fato: para todo n ≥ 20, temos

300 + 20/n  ≤  300 + 1  =  301 .

Resumindo: 300 + 20/n ≤ 301 para todo n ≥ 20. Isso mostra que 300 + 20/n = Ο(n⁰).  (Não verifiquei explicitamente que 300 + 20/n e n⁰ são assintoticamente não-negativas, mas isso é óbvio.)

Exemplo D.  Considere as funções 20 n² + 2n + 100 e n³ − 10. Observe que ambas são não-negativas para todo n ≥ 3 e portanto assintoticamente não-negativas. Agora observe que para todo n ≥ 10 temos

20 n² + 2n + 100 20 n² + nn + n²
   =  22 n²
   ≤  22 n³
   ≤  44 (n³ − 10),

onde a última desigualdade vale porque n³ > 20 e portanto n³ ≤ 2n³ − 20. Resumindo: 20 n² + 2n + 100 ≤ 44 (n³ − 10) para todo n ≥ 10. Isso mostra que 20 n² + 2n + 100 está em Ο(n³ − 10).

Exemplo E.  A função n³ não está em Ο(n²). Veja a prova desse fato: Suponha por um momento que n³ = Ο(n²). Então existem números positivos c e n0 tais que n³ ≤ cn² para todo nn0. Logo,

nc

para todo nn0. Isso é contraditório. A contradição mostra que n³ não pode estar em Ο(n²).

Exemplo F.  A função n² − 100n não está em Ο(200 n). Segue a prova desse fato. Suponha por um momento n² − 100n = Ο(200 n). Então existem c > 0 e n0 > 0 tais que n² − 100nc 200 n para todo nn0. Logo,

n − 100 ≤ 200 c

para todo nn0. Chegamos ao seguinte absurdo: todo nn0 satisfaz a desigualdade n ≤ 200 c + 100. Esse absurdo mostra que n² − 100n não pode estar em Ο(200 n).

Exemplo G.  Para qualquer número a maior que 1 temos logan = Ο(lg n), sendo lg o logaritmo na base 2. Isso é assim porque

logan =  1  lg n
lg a

para todo n ≥ 1. (Veja a página Exercícios preliminares.) Além disso, logan e lg a são assintoticamente não-negativas, pois ambas são positivas para n ≥ 2.

Exemplo H.  A função n/2⌉ + 10 está em Ο(n). De fato, temos n/2⌉ + 10 ≤ n/2 + 1 + 10 = n/2 + 11 ≤ 20 n para todo n ≥ 1.  Veja outra maneira de provar a mesma coisa:

n/2⌉ + 10 n/2 + 11
   ≤  n/2 + n/2
   =  n

para todo n ≥ 22. (Além disso, é evidente que as funções são assintoticamente não-negativas.)

Exercícios 1

  1. Qual a diferença entre assintótico e assintomático?
  2. Suponha que funções f e g são assintoticamente não-negativas. Critique as seguintes tentativas de definição da classe Ο:  "Dizemos que f está em Ο(g) se …
    1. f(n) ≤ cg(n) para algum n suficientemente grande e todo c positivo."
    2. … para todo n suficientemente grande existe c positivo tal que f(n) ≤ cg(n)."
    3. f(n) ≤ cg(n) para todo n positivo e algum c positivo."
    4. … existem números positivos c, n0 e n ≥ n0 tais que f(n) ≤ cg(n)."
    5. … existe um número positivo n0 tal que f(n) ≤ cg(n) para algum número positivo c e para todo n ≥ n0."
  3. Faz sentido dizer f(n) está em Ο(n²) para n ≥ 10?
  4. Fica bem dizer f(n) = Ο(n²) com c = 10 e n0 = 100?  Como reformular isso?
  5. ★ Mostre que a cláusula n suficientemente grande na definição da classe Ο é supérflua quando estamos lidando com funções estritamente positivas.
  6. 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).
  7. É verdade que 100n = Ο(n)?  É verdade que n2/100 = Ο(n)?
  8. É verdade que 10n2 + 200n + 500/n = Ο(n2)?
  9. É verdade que n2 − 200n − 300 = Ο(n)?
  10. ★ Seja C(n, k) o número de combinações de n objetos tomados k a k. Mostre que C(n, 2) = Ο(n2). Mostre que C(n, 3) = Ο(n3). É verdade que, para qualquer número natural k ≤ n, tem-se C(n, k) = Ο(nk)?
  11. ★ É verdade que 2n+1 está em Ο(2n)?  É verdade que 2n está em Ο(2n/2)?
  12. ★ É verdade que 3n está em Ο(2n)?  É verdade que 2n está em Ο(3n)?
  13. ★ É verdade que lg n = Ο(log3n)?  É verdade que log3n = Ο(lg n)?
  14. ★ É verdade que ⌈lg n = Ο(lg n)?
  15. Prove que n lg n + 10n3/2 está em Ο(n lg n).
  16. Prove que 2 n lg n − 10n + 100 lg n está em Ο(n lg n).
  17. Mostre que lg (100n³ + 200n + 300)² = Ο(lg n).
  18. ★ Prove que n = Ο(2n). (Sugestão: veja a página Exercícios preliminares.) Prove que lg n está em Ο(n).
  19. Prove que n é Ο(2n/4). (Veja exercício anterior.)
  20. É verdade que 2n1024 = Ο(2n)?
  21. É verdade que n2/3 está em Ο(√n)?
  22. Qual o maior número natural k tal que n1/k = Ο(lg n)?
  23. Transitividade. Suponha que f = Ο(g) e g = Ο(h). Prove que f = Ο(h).
  24. Coloque as seguinte funções em ordem crescente de Ο( )nnlog n,  2nn / (log n)2nlog log nlog² nn.

Ordem Ômega

A expressão f = Ο(g) tem sabor de fg. Agora precisamos de um conceito que tenha o sabor de fg.

Definição: Dadas funções assintoticamente não-negativas fg, dizemos que f está na ordem Ômega de g e escrevemos  f = Ω(g)  se existe um número positivo c tal que f(n) c · g(n) para todo n suficientemente grande.

(O sinal = na notação de Landau f = Ω(g) é um abuso pois não representa igualdade no sentido usual. Provavelmente melhor dizer f está em Ω(g) ou f é Ω(g).)

Qual a relação entre Ο e Ω?  Não é difícil verificar que  f = Ο(g) se e somente se g = Ω(f).

Exemplo I.  É fato que n/2 − 100 = Ω(n). Confira a prova: Para todo n ≥ 400, tem-se

n/2 − 100 ≥ n/2 − n/4 = (1/4) n.

Além disso, é evidente que as duas funções são assintoticamente não-negativas.

Exemplo J.  A função n²/2 − 100 n − 300 está em Ω(n). De fato, para todo n ≥ 500, tem-se

n²/2 − 100 n − 300 n²/2 − n²/4 − n²/8
   =  (1/2 − 1/4 − 1/8) n²
   =  (1/8) n²
   ≥  (500/8) n
   ≥  80 n.

Além disso, n²/2 − 100 n − 300 > 30000 > 0 para todo n ≥ 400 e portanto as duas funções em discussão são assintoticamente não-negativas.

Exercícios 2

  1. Sejam fg duas funções assintoticamente não negativas. Prove que f = Ο(g) se e somente se g = Ω(f).
  2. Seja C(n, k) o número de combinações de n objetos tomados k a k. Mostre que C(n, 2) = Ω(n2). Mostre que C(n, 3) = Ω(n3). É verdade que, para qualquer número natural k ≤ n, tem-se C(n, k) = Ω(nk)?
  3. Prove que 2n² − 20 n − 50 = Ω(2n).
  4. Prove que 2n² − 20 n − 50 = Ω(n3/2).
  5. Prove que n² + n + 10 = Ω(n lg n).
  6. É verdade que 100n² + 10000 = Ω(n² lg n)?
  7. Prove que 100 lg n 10n + 2 n lg n está em Ω(n lg n).
  8. É verdade que 2n−2 está em Ω(2n)?   É verdade que 3n/2 está em Ω(2n)?

Ordem Theta

Além dos conceitos que têm os sabores de f ≤ g e de f ≥ g, precisamos de um que tenha o sabor de f = g.

Definição: Dizemos que duas funções assintoticamente não negativas fg são da mesma ordem 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  cg(n) ≤ f(n) ≤ dg(n)  para todo n suficientemente grande.

Exemplo K.  As funções  n2(3/2) n29999 n2n2/1000  e  n2+100n pertencem todas à ordem Θ(n2).

Exemplo L.  Para quaisquer números a e b maiores que 1, a função logan está em Θ(logbn).

Exercícios 3

  1. Mostre que f = Θ(g) se e somente se g = Θ(f).
  2. Quais das afirmações abaixo estão corretas?
    • (3/2) n2 + (7/2) n − 4 = Θ(n2)
    • 9999 n2 = Θ(n2)
    • n2/1000 − 999 n = Θ(n2)
    • lg n + 1 = Θ(log10n)
    • ⌊lg n = Θ(lg n)

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. Veja alguns exemplos de domínios:

A notação Ο pode ser usada em qualquer desses domínios. Por exemplo, se f é uma função assintoticamente não-negativa definida nas potências inteiras de 2, dizer que f(n) = Ο(n²) é o mesmo que dizer que existe um número positivo c tal que f(n) ≤ cn² para todo n da forma 2k com k suficientemente grande.

As mesmas observações se aplicam à notação Ω e à notação Θ.

Análise de algoritmos

A análise de algoritmos procura estimar o consumo de tempo de um algoritmo em função do tamanho, digamos n, de sua entrada.

Suponha que f(n) é o consumo de tempo de um algoritmo A para um certo problema e g(n) é o consumo de tempo de um algoritmo B para o mesmo problema. Para comparar as eficiências de AB, a análise de algoritmos estuda o comportamento de f e g para valores grandes de n. Se f = Ο(g), o algoritmo A é considerado pelo menos tão eficiente quanto B. Se, além disso, f não está em Θ(g), o algoritmo A é considerado mais eficiente que B.

As funções mais comuns na análise de algoritmos são lg n, n, n lg n, n² e n³. A seguinte tabela mostra os valores dessas funções para n entre 103 e 107. Para simplificar, a tabela mostra o logaritmo na base 10. Cada função da tabela é dominada pela seguinte e esse efeito cresce com o valor de n.

log n 3 4 5 6 7
n 1000 10000 100000 1000000 10000000
n log n 3000 40000 500000 6000000 70000000
n² 1000000 100000000 10000000000 1000000000000 100000000000000
n³ 1000000000 1000000000000 1000000000000000 1000000000000000000 1000000000000000000000