Baixe o app para aproveitar ainda mais
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
Compartilhar