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) n2, 9999 n2, n2/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
.
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) ≤ c g(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, de acordo com 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.
(No lugar de
f está na ordem Ó de g
,
há quem diga
f é da ordem de no máximo g
.)
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 atenção para os valores de c
e n0.
(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 , CQD.
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³ ≤ c n² para todo n ≥ n0. Logo,
n ≤ c
para todo n ≥ n0. Isso é contraditório. A contradição mostra que n³ não pode estar em Ο(n²), CQD.
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² − 100n ≤ c 200 n para todo n ≥ n0. Logo,
n − 100 ≤ 200 c
para todo n ≥ n0. Chegamos ao seguinte absurdo: todo n ≥ n0 satisfaz a desigualdade n ≤ 200 c + 100. Esse absurdo mostra que n² − 100n não pode estar em Ο(200 n), CQD.
Exemplo G. Para qualquer número a maior que 1 temos loga n = Ο(lg n), sendo lg o logaritmo na base 2. Isso é assim porque
| loga n = | 1 | lg n |
| lg a |
para todo n ≥ 1. (Veja a página Exercícios de aquecimento.) Além disso, loga n 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.)
f(n) está em Ο(n²) para n ≥ 10?
f(n) = Ο(n²) com c = 10 e n0 = 100? Como reformular isso?
Se 3n² + 7n ≤ c n² então 3n + 7 ≤ c n, supondo n > 0. Logo, c ≥ 3 + 7/n. Logo, c ≥ 3 + 7 é suficiente. Logo, c ≥ 10 e n > 0. CQD.
n suficientemente grandena definição da classe Ο é supérflua quando estamos lidando com funções estritamente positivas.
A derivada de 4n² + 2n é 8n + 2. A derivada de n² é 2n. Como 8n+2 > 2n, podemos concluir que 4n²+2n cresce mais que n² e portanto 4n²+2n não é Ο(n²).Critique o seguinte raciocínio:
A derivada de 4n² + 2n é 8n + 2. A derivada de 9n² é 18n. Como 8n+2 ≤ 18n para n ≥ 1, podemos concluir que 4n²+2n é Ο(9n²).
A expressão f = Ο(g)
tem sabor de 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 Ô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.
(No lugar de
f está na ordem Ômega de g
,
há quem diga
f é da ordem de pelo menos g
.)
(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, CQD.
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.
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 f e g 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 c g(n) ≤ f(n) ≤ d g(n) para todo n suficientemente grande.
Exemplo K. As funções n2, (3/2) n2, 9999 n2, n2/1000 e n2+100n pertencem todas à ordem Θ(n2).
Exemplo L. Para quaisquer números a e b maiores que 1, a função loga n está em Θ(logb n).
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) ≤ c n² para todo n da forma 2k com k suficientemente grande.
As mesmas observações se aplicam à notação Ω e à notação Θ.
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 A e B, 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 |