Análise e Projeto de Algoritmos

Análise e Projeto de Algoritmos Márcia Cappelle e Hebert Coelho com slides dos Profs Humberto Longo e Hugo Nascimento Instituto de Informática Universidade Federal de Goiás 2022 INFUFG APA 20221 M Cappelle H Coelho 1 1 de 828 Motivação Dados dois algoritmos como decidir qual é melhor Opções 1 Implementar ambos os algoritmos e executálos com o mesmo conjunto de instâncias de teste Caro e propenso a erros O algoritmo foi implementado corretamente Existem erros na implementação O conjunto de instâncias de teste é adequado Quanto mais rápido pode ser o algoritmo 2 Analisálos matematicamente INFUFG APA 20221 M Cappelle H Coelho Notação Assintótica 82 136 de 828 Motivação Análise Quantitativa Qualitativa Qualitativa referese à comparação de qualidades por exemplo mais rápido menos memória Quantitativa referese à determinação dos custos reais memória tempo dinheiro envolvidos com os algoritmos em questão INFUFG APA 20221 M Cappelle H Coelho Notação Assintótica 83 136 de 828 Análise assintótica Em geral sempre vamos analisar algoritmos com respeito a uma ou mais variáveis Uma variável O número n de itens já armazenados em uma matriz ou outra estrutura de dados O número de artigos previsto para ser armazenado em alguma estrutura de dados As dimensões de uma matriz n n Diversas variáveis Lidar com n objetos armazenados em m locais de memória Multiplicar uma matriz de dimensão m k por outra de dimensão k n Lidar com matrizes esparsas de dimensão n n com apenas m elementos diferentes de zero INFUFG APA 20221 M Cappelle H Coelho Notação Assintótica 84 136 de 828 Análise assintótica Busca linear binária 1 i n t l i n e a r s e a r c h i n t key i n t M i n t n 2 f o r i n t i 0 i n i 3 i f M i key 4 r e t u r n i 5 6 7 8 r e t u r n 1 9 INFUFG APA 20221 M Cappelle H Coelho Notação Assintótica 85 136 de 828 Análise assintótica Busca linear binária 1 i n t binarysearch i n t key i n t M i n t n 2 i n t l 0 3 i n t r n 1 4 5 w h i l e l r 6 i n t c l r 2 7 8 i f M c key 9 r e t u r n c 10 e l s e 11 i f M c key 12 l c 1 13 e l s e 14 r c 1 15 16 17 r e t u r n 1 18 INFUFG APA 20221 M Cappelle H Coelho Notação Assintótica 86 136 de 828 Análise assintótica Busca linear binária Existem algoritmos que são significativamente mais rápidos à medida que o tamanho da instância cresce Nr de comparações para encontrar um elemento em uma matriz unidimensional ordenada 10 20 30 10 20 30 n fn lgn n INFUFG APA 20221 M Cappelle H Coelho Notação Assintótica 87 136 de 828 Análise assintótica Dado um algoritmo Precisamos ser capazes de descrever matematicamente as variáveis associadas ao algoritmo É necessário um meio sistemático de utilizar a descrição do algoritmo em conjunto com as propriedades de uma estrutura de dados associada Precisamos fazer isso de modo independente da máquina em que será utilizada uma implementação computacional do algoritmo Para isso precisamos dos símbolos de Landau e a análise assintótica associada INFUFG APA 20221 M Cappelle H Coelho Notação Assintótica 88 136 de 828 Análise assintótica Notação assintótica OΩΘow A criação da notação O é creditada ao matemático alemão Paul Bachmann em 1894 na publicação da segunda versão da sua obra Analytische Zahlentheorie Outro alemão Edmund Landau adotou a notação O e inspirado na mesma introduziu em 1909 a notação o Por causa disso ambas são chamadas de Símbolos de Landau As notações O Ω e Θ foram popularizadas na Ciência da Computação por Donald Knuth o qual também observou que a notação Ω tinha sido introduzida por Hardy e Littlewood com um significado diferente o não é o de Essas notações são como sinônimos de da ordem de INFUFG APA 20221 M Cappelle H Coelho Notação Assintótica 89 136 de 828 Análise assintótica Crescimento de funções As funções fn n2 e gn n2 3n 2 parecem muito diferentes quando próximas de n 0 05 1 15 2 25 3 5 10 n fn n2 n2 3n 2 INFUFG APA 20221 M Cappelle H Coelho Notação Assintótica 90 136 de 828 Análise assintótica Crescimento de funções No intervalo n 0 10 as funções parecem mais similares 2 4 6 8 10 50 100 n fn n2 n2 3n 2 INFUFG APA 20221 M Cappelle H Coelho Notação Assintótica 91 136 de 828 Análise assintótica Crescimento de funções Ao ampliar o intervalo para n 0 100 a semelhança aumenta 20 40 60 80 100 5000 10000 n fn n2 n2 3n 2 INFUFG APA 20221 M Cappelle H Coelho Notação Assintótica 92 136 de 828 Análise assintótica Crescimento de funções Para o intervalo n 0 1000 as diferenças são quase indistinguíveis 200 400 600 800 1000 500000 1000000 n fn n2 n2 3n 2 INFUFG APA 20221 M Cappelle H Coelho Notação Assintótica 93 136 de 828 Análise assintótica Crescimento quadrático Há diferenças absolutas nas funções fn n2 e gn n2 3n 2 f1000 1000000 g1000 997002 A diferença relativa é muito pequena e tende a zero à medida que n cresce n INFUFG APA 20221 M Cappelle H Coelho Notação Assintótica 94 136 de 828 Análise assintótica Crescimento polinomial As funções fn n6 e gn n6 23n5 193n4 729n3 1206n2 648n são muito diferentes quando próximas de n 0 3 2 1 1 2 3 4 5 1000 2000 n fn n6 n6 23n5 193n4 729n3 1206n2 648n INFUFG APA 20221 M Cappelle H Coelho Notação Assintótica 95 136 de 828 Análise assintótica Crescimento polinomial Mesmo ao estender o intervalo para n 0 10 elas não parecem ter muita semelhança 2 2 4 6 8 10 10000 20000 n fn n6 n6 23n5 193n4 729n3 1206n2 648n INFUFG APA 20221 M Cappelle H Coelho Notação Assintótica 96 136 de 828 Análise assintótica Crescimento polinomial À medida que o intervalo para n é estendido elas parecem ser mais semelhantes 20 40 60 80 100 05 1 1012 n fn n6 n6 23n5 193n4 729n3 1206n2 648n INFUFG APA 20221 M Cappelle H Coelho Notação Assintótica 97 136 de 828 Análise assintótica Crescimento polinomial Próximo a n 1000 a diferença relativa é inferior a 3 200 400 600 800 1000 05 1 1018 n fn n6 n6 23n5 193n4 729n3 1206n2 648n INFUFG APA 20221 M Cappelle H Coelho Notação Assintótica 98 136 de 828 Análise assintótica Crescimento polinomial A justificativa para os dois pares de polinômios serem semelhantes é que em ambos os casos cada um tem o mesmo termo de maior grau n6 O que acontece se os coeficientes dos termos principais são diferentes Neste caso ambas as funções podem apresentar a mesma taxa de crescimento No entanto uma delas sempre poderia ser proporcionalmente maior INFUFG APA 20221 M Cappelle H Coelho Notação Assintótica 99 136 de 828 Análise assintótica Crescimento polinomial 05 1 15 2 25 3 35 4 45 5 55 500 1000 1500 2000 2500 n fn n4 3n 2 n6 23n5 193n4 729n3 1206n2 648n INFUFG APA 20221 M Cappelle H Coelho Notação Assintótica 100 136 de 828 Análise assintótica Crescimento polinomial 1 2 3 4 5 6 7 8 9 10 11 5000 10000 15000 20000 25000 n fn n4 3n 2 n6 23n5 193n4 729n3 1206n2 648n INFUFG APA 20221 M Cappelle H Coelho Notação Assintótica 101 136 de 828 Análise assintótica Crescimento polinomial 20 40 60 80 100 02 04 06 08 1 12 1012 n fn n4 3n 2 n6 23n5 193n4 729n3 1206n2 648n INFUFG APA 20221 M Cappelle H Coelho Notação Assintótica 102 136 de 828 Notação assintótica Algumas considerações Qualquer problema requer pelo menos uma instrução e um byte de memória para ser resolvido Funções que descrevem o tempo ou a memória necessária para resolver um problema de tamanho n definidos para n 0 estritamente positivas para todos os valores de n fn c para algum valor c 0 crescentes monótonas INFUFG APA 20221 M Cappelle H Coelho Notação Assintótica 103 136 de 828 Notação assintótica Notação O Uma função fn Ogn se existem constantes positivas c e n0 tais que fn cgn sempre que n n0 A função fn tem uma taxa de crescimento que não é maior do que a taxa de crescimento de gn INFUFG APA 20221 M Cappelle H Coelho Notação Assintótica 104 136 de 828 Exemplo 14 1 2n2 3n On2 pois 1 2n2 3n cn2 se c 1 2 3 n o que é válido para c 1 2 e n 1 Para k1 0 k1n2 k2n k3 On2 pois k1n2 k2n k3 k1 k2 k3n2 Logo para c k1 k2 k3 e n 1 k1n2 k2n k3 cn2 Para k1 0 k1n2 k2n k3 On3 pois k1n2 k2n k3 k1 k2 k3n3 Logo para c k1 k2 k3 e n 1 k1n2 k2n k3 cn3 INFUFG APA 20221 M Cappelle H Coelho Notação Assintótica 105 136 de 828 Notação assintótica Notação Ω Uma função fn Ωgn se existem constantes positivas c e n0 tais que fn cgn sempre que n n0 A função fn tem uma taxa de crescimento que não é menor do que a taxa de crescimento de gn INFUFG APA 20221 M Cappelle H Coelho Notação Assintótica 106 136 de 828 Exemplo 15 1 2n2 3n Ωn2 pois 1 2n2 3n cn2 se 0 c 1 2 3 n o que é válido para c 1 14 e n 7 INFUFG APA 20221 M Cappelle H Coelho Notação Assintótica 107 136 de 828 Notação assintótica Notação Θ Uma função fn Θgn se existem constantes positivas c1 c2 e n0 tais que c1gn fn c2gn sempre que n n0 A função fn tem uma taxa de crescimento igual à taxa de crescimento de gn INFUFG APA 20221 M Cappelle H Coelho Notação Assintótica 108 136 de 828 Notação assintótica Notação Θ fn n2 2 3n e gn n2 fn Θgn Queremos mostrar que existem constantes c1 c2 n0 0 tais que c1n2 n2 2 3n c2n2 n n0 1 Considerando n 0 c1 1 2 3 n c2 Os valores c1 1 14 c2 1 2 e n0 7 tornam a inequação 1 verdadeira 6n3 Θn2 INFUFG APA 20221 M Cappelle H Coelho Notação Assintótica 109 136 de 828 Notação assintótica Notação Θ fn 6n log n n log2 n Θn log n Queremos mostrar que existem constantes c1 c2 n0 0 tais que c1n log n 6n log n n log2 n c2n log n n n0 2 Considerando n 1 c1n log n 6n log n n log2 n c1 6 log n n 6n log n n log2 n c2n log n 6 log n n c2 Notese que log n n se n 2 Portanto para os valores c1 6 c2 7 e n0 2 a inequação 2 é verdadeira INFUFG APA 20221 M Cappelle H Coelho Notação Assintótica 110 136 de 828 Notação assintótica Notação Θ Dadas as funções fn e gn como determinar se fn Θgn INFUFG APA 20221 M Cappelle H Coelho Notação Assintótica 111 136 de 828 Notação assintótica Notação Θ Dadas as funções fn e gn como determinar se fn Θgn Se fn e gn são polinômios de mesmo grau expoentes positivos nos termos do polinômio lim n fn gn c onde 0 c INFUFG APA 20221 M Cappelle H Coelho Notação Assintótica 112 136 de 828 Notacdo assintotica Notacdo Da definicdo de limites dado c 0 existe um no 0 tal que n ae Ey gn sempre que 2 no Logo n CEX fn ETE gn gne fn gne eS 9 INFUFG APA 20221 M Cappelle H Coelho Notacdo Assintotica 113 136 de 828 Notação Assintótica Notação o Uma função fn ogn se para qualquer constante positiva c existe uma constante positiva n0 tal que fn cgn sempre que n n0 Notação ω Uma função fn ωgn se para qualquer constante positiva c existe uma constante positiva n0 tal que fn cgn sempre que n n0 INFUFG APA 20221 M Cappelle H Coelho Notação Assintótica 114 136 de 828 Notação assintótica Limites Se lim n fn gn c para 0 c então fn Θgn Se lim n fn gn c para c então fn Ogn Se lim n fn gn 0 então fn ogn A função fn tem uma taxa de crescimento menor do que a taxa de crescimento de gn A função fn tem uma taxa de crescimento maior do que a taxa de crescimento de gn A função fn tem uma taxa de crescimento maior ou igual à taxa de crescimento de gn INFUFG APA 20221 M Cappelle H Coelho Notação Assintótica 115 136 de 828 Notação assintótica Limites Resumo lim n fn gn 0 fn ogn lim n fn gn fn Ogn 0 lim n fn gn fn Θgn lim n fn gn 0 fn Ωgn lim n fn gn fn ωgn INFUFG APA 20221 M Cappelle H Coelho Notação Assintótica 116 136 de 828 Limites e notação assintótica Regra de LHopital Se as funções f e g são diferenciáveis lim n fn lim n gn e o limite lim n fn gn existe então lim n fn gn lim n fn gn Exemplo 16 Se fn lgn e gn n então fn ogn lim n lgn n lim n lnn ln2 n lim n 1 n ln2 0 INFUFG APA 20221 M Cappelle H Coelho Notação Assintótica 117 136 de 828 Limites e notacdo assintotica Pm Se fn Ogn nem sempre lim ff noo 97 n se 7 par P Ex fn Pn on sen é impar Pm Se gn n entao o limite lim fa nao existe nco Claramente fn On eS 9 INFUFG APA 20221 M Cappelle H Coelho Notacdo Assintotica 118 136 de 828 Propriedades da notação assintótica Transitividade fn Θgn e gn Θhn fn Θhn fn Ogn e gn Ohn fn Ohn fn Ωgn e gn Ωhn fn Ωhn fn ogn e gn ohn fn ohn fn ωgn e gn ωhn fn ωhn INFUFG APA 20221 M Cappelle H Coelho Notação Assintótica 119 136 de 828 Propriedades Reflexividade fn Θfn fn Ofn fn Ωfn Simetria fn Θgn gn Θfn Simetria Transposta fn Ogn gn Ωfn fn ogn gn ωfn INFUFG APA 20221 M Cappelle H Coelho Notação Assintótica 120 136 de 828 Livros Texto T H Cormen C E Leiserson e R L Rivest Introduction to Algorithms McGrawHill New York 1990 C H Papadimitriou U V Vazirani e S Dasgupta Algoritmos McgrawHill Brasil 2009 U Manber Algorithms A Creative Approach AddisonWesley 1989 D E Knuth The Art of Computer Programming Volume 1 Fundamental Algorithms Addison Wesley 1998 D E Knuth The Art of Computer Programming Volume 2 Sorting and Searching Addison Wesley 1998 N Ziviani Projeto de Algoritmos com Implementações em Pascal e C Editora Thomson 2a Edição 2004 INFUFG APA 20221 M Cappelle H Coelho Bibliografia 828 828 de 828