Análise de Algoritmos e Estruturas de Dados: Introdução e Complexidade

Algoritmos e Estrutura de Dados Noções de análise de complexidade Parte Introdução Professor Alexandre Magno de Sousa Departamento de Computação e Sistemas Sumário Introdução Exemplos de análise de algoritmos Crescimento assintótico das funções Classes de complexidade Classes de algoritmos e medidas de tempo Funções típicas e estimativas Ogrande Referências bibliográficas Introdução O projeto de algoritmos é fortemente influenciado pelo estudo de seus comportamentos Depois que decisões de projetos são feitas o algoritmo deve ser implementado Vários algoritmos podem ser utilizados e devese estudar aspectos de tempo de execução e espaço Muitos destes algoritmos são encontrados em áreas como pesquisa operacional otimização teoria dos grafos estatística probabilidade entre outras Introdução Existem dois problemas bem distintos Análise de um algoritmos em particular Qual é o custo de usar um dado algoritmo para resolver um problema específico Análise de uma classe de algoritmos Qual é o algoritmo de menor custo para resolver um problema particular Introdução Determinando o custo temse a medida de dificuldade para resolver um dado problema Se o custo de um dado algoritmo é o menor podese concluir que o algoritmo é ótimo Podem existir vários algoritmos para resolver o mesmo problema e é necessário escolher o melhor Se a mesma medida de custo é aplicada é possível comparálos e escolher o mais adequado Introdução O custo de execução de um algoritmo pode ser medido de várias maneiras Uma delas é a medição do tempo de execução real de um algoritmo em um computador Objeções i resultados dependem do compilador ii resultados dependem do hardware iii resultados dependem do tamanho da memória Introdução Para medir o custo de execução é comum definir uma função de custo ou função de complexidade f fn é a medida de tempo necessário para executar um algoritmo para um problema de tamanho n Se fn é a medida da quantidade da memória necessária para executar um algoritmo então é chamada de função de complexidade de espaço Análise de algoritmos exemplo Considere um algoritmo para encontrar o maior elemento de um vetor de inteiros 1 2 3 4 5 6 7 8 9 10 Análise de algoritmos exemplo seja fn o custo do o número de comparações void max int v int n int max max v0 i for i 1 i n i if max vi max vi Análise de algoritmos exemplo seja fn o custo do o número de comparações void max int v int n int max max v0 i for i 1 i n i if max vi max vi f n 1 n1 1n1 1 n1 Análise de algoritmos exemplo seja fn o custo do o número de comparações void max int v int n int max max v0 i for i 1 i n i if max vi max vi f n n1 n0 f n 1 n1 1n1 1 n1 Análise de algoritmos Melhor caso menor tempo de execução Pior caso maior tempo de execução Caso médio ou caso esperado média dos tempos de execução de todas as entradas de tamanho n Uma distribuição de probabilidades sobre o conjunto de entradas de tamanho n é suposta e custo é obtido com base nessa distribuição Análise pesquisa sequencial seja fn o custo do o número de comparações Pesquisa sequencial examina registros na ordem em que eles aparecem no arquivo Caso Custo Melhor caso fn 1 Pior caso fn n Caso médio fn n 12 Análise de algoritmos seja fn o custo do o número de comparações void maxMin1 int v int n int max int min max v0 min v0 int i for i 1 i n i if vi max max vi if vi min min vi Análise de algoritmos seja fn o custo do o número de comparações void maxMin1 int v int n int max int min max v0 min v0 int i for i 1 i n i if vi max max vi if vi min min vi f n 1 n1 2 n122n2 Análise de algoritmos seja fn o custo do o número de comparações void maxMin1 int v int n int max int min max v0 min v0 int i for i 1 i n i if vi max max vi if vi min min vi f n 2 n1 n0 f n 1 n1 2 n122n2 Análise de algoritmos seja fn o custo do o número de comparações Caso Custo Melhor caso fn n 1 Pior caso fn 2n 1 Caso médio fn 3n232 void maxMin2 int v int n int max int min max v0 min v0 int i for i 1 i n i if vi max max vi else if vi min min vi Análise de algoritmos seja fn o custo do o número de comparações Para maxMin2 segue os seguintes cálculos Melhor caso vetor em ordem crescente Pior caso vetor em ordem decrescente Caso médio f n 1 n1 1n11n1 f n 1 n1 2 n122n2 f nn1n1 2 3n 2 3 2 void maxMin3 int v int n int max int min int i 2 fimDoLaco if n 2 0 vn vn 1 fimDoLaco n else fimDoLaco n 1 if v0 v1 max v0 min v1 else max v1 min v0 while i fimDoLaco if vi vi 1 if vi max max vi if vi 1 min min vi 1 else if vi min min vi if vi 1 max max vi 1 i i 2 f n i2 n2 31 i1 n2 2 31 3n6 2 13n 2 2 void maxMin3 int v int n int max int min int i 2 fimDoLaco if n 2 0 vn vn 1 fimDoLaco n else fimDoLaco n 1 if v0 v1 max v0 min v1 else max v1 min v0 while i fimDoLaco if vi vi 1 if vi max max vi if vi 1 min min vi 1 else if vi min min vi if vi 1 max max vi 1 i i 2 f n i2 n2 31 i1 n2 2 31 3n6 2 1 3n 2 2 2 comparações 2 comparações ou 1 comparação 1 comparação 3 comparações Análise de algoritmos comparação do custo de fn dos algoritmos Algoritmos Melhor caso Pior caso Caso médio maxMin1 2n 1 2n 1 2n 1 maxMin2 n 1 2n 1 3n2 32 maxMin3 3n2 2 3n2 2 3n2 2 Séries e somatórios j 0 n 2n2n 11 j0 n 1 2 j2 1 2n j 0 n a j an11 a1 a1 j1 n j2 nn 12n1 6 ji n cni1c ji n j ni1ni 2 j0 1 a j 1 11a j0 n 1 a j 11an 11a Notações Padrão exponenciais a01 a1a a11 a amnamn anmanm am anamn Notações padrão logaritmos lg n log2 n ln n loge n lg k nlg nk lglg n lglg n logaritmo binário logaritmo natural exponenciação composição Notações padrão logaritmos ablogb a log cab log c a logc b log bann logb a log ba logc a logc b Notações padrão logaritmos log b1 alogb a log ba 1 log ab alogb cclogb a bnaba blogb nna blogb bnab1na b Análise de algoritmos seja fn o custo do nº de atribuições for i soma 0 i n i soma ai Análise de algoritmos seja fn o custo do nº de atribuições for i 0 i n i for j 1 soma a0 j i j soma aj printfSoma de 0 até d é d i soma Análise de algoritmos seja fn o custo do nº de atribuições for i 4 i n i for j i 3 soma a i 4 j i j soma a j printfSoma de d até d é d i4 i soma Análise de algoritmos seja fn o custo do nº de atribuições for i 0 comprimento 1 i n 1 i for i1i2ki k n 1 ak ak1 ki2 if comprimento i2 i1 1 comprimento i2 i1 1 Análise de algoritmos seja fn o custo do nº de atribuições int buscaBinaria int arr int arrTamanho int chave int baixo 0 meio alto arrTamanho 1 while baixo alto meio baixo alto 2 if chave arr meio alto meio 1 else if arr meio chave baixo meio 1 else return meio retorna o índice da chave encontrada return 1 caso não encontrado retorna 1 indicando falha Notação OGrande O tempo exato de execução de um algoritmo é uma expressão complexa assim ele é apenas estimado A análise assintótica é uma estimativa utilizada para entender o tempo de execução quando executado sobre entradas grandes Notação OGrande Seja a função fn 6n3 2n2 20n 45 O termo de mais alta ordem é 6n3 Desconsiderando o coeficiente 6 dizemos que f é assintoticamente no máximo n3 A notação assintótica ou Ogrande para descrever esse relacionamento é fn On3 Notação OGrande DEFINIÇÃO Sejam f e g funções fg N R Digamos que fn Ogn se existem inteiros positivos c e n0 tais que para todo inteiro n n0 fn c gn Notação OGrande Quando fn Ogn dizemos que gn é um limitante superior para fn ou é limitante superior assintótico para fn Isso enfatiza que estamos suprimindo fatores constantes Notação OGrande exemplo Seja fn 5n3 2n2 22n 6 Termo de mais alta ordem 5n3 Desconsiderando seu coeficiente temse que fn On3 Notação OGrande exemplo Verificação da definição formal Tornando c 6 e n0 10 Então 5n3 2n2 22n 6 6n3 para todo n 10 Notação OGrande fn On4 porque n4 n3 portanto ainda é um limitante superior assintótico sobre f fn não é On2 porque independente dos valores que sejam atribuídos a c e n0 a definição permanece insatisfeita Como definir c e n0 para fn e Ogrande Notação OGrande Seja a função fn 2n² 3n 1 fn On² onde gn n² Então o valor de n0 e c é obtido resolvendo a desigualdade 2n 23n1cn 2 2n 2 n 2 3n n 2 1 n 2c 2 3 n 1 n2c Desigualdade com duas incógnitas diferentes pares de constantes n0 e c para a mesma função podem ser encontradas Notação OGrande Para escolher os melhores valores de n0 e c deve ser determinado para qual valor de n0 um certo termo em fn se torna o maior e permanece dessa forma Os dois únicos candidatos são 2n² e 3n 2n² 3n que é válida para n 1 Assim n0 2 e substituindo 2 3 n 1 n 2c 2 3 2 1 2 2c 375c n0 2 e c 375 Notação OGrande Qual o significado prático dos pares de c e n0 listados acima Para um gn fixo existe um número infinito de pares pode ser identificado A definição estabelece que quase sempre gn fn para todos n não menores do que n0 O valor de c depende do n0 escolhido c 6 375 311 281 264 253 245 2 n0 1 2 3 4 5 6 7 Tabela pares de valores de c e n0 calculados a partir de fn e Ogrande Notação opequeno A notação Ogrande diz que uma função é assintoticamente não mais que outra Podese dizer que uma função é assintoticamente menor que outra por meio da notação opequeno A diferença entre as notações Ogrande é o pequeno é análoga àquela entre e Notação opequeno DEFINIÇÃO Sejam f e g funções fg N R Digamos que fn ogn se se existem inteiros positivos c e n0 tais que para todo inteiro n n0 fn c gn e na medida em que n se aproxima do infinito limn fngn 0 Notação opequeno Em outras palavras fn ogn significa que para qualquer número real c 0 e n0 onde fn c gn para todo n n0 Notação opequeno exemplos 1 n on 2 n on log log n 3 n log log n on log n 4 n log n on2 5 n2 on3 6 fn nunca é ofn Notação Ωgrande DEFINIÇÃO Sejam f e g funções fg N R Digamos que fn Ωgn se existem inteiros positivos c e n0 tais que para todo inteiro n n0 0 c gn fn Notação ωpequeno DEFINIÇÃO Sejam f e g funções fg N R Digamos que fn ωgn se existem inteiros positivos c e n0 tais que para todo inteiro n n0 0 c gn fn e na medida em que n se aproxima do infinito limn fngn Notação Θgrande DEFINIÇÃO Sejam f e g funções fg N R Digamos que fn Θgn se existem inteiros positivos c1 c2 e n0 tais que para todo inteiro n n0 0 c1 gn fn c2 gn Analogia comparação das funções f e g com número reais a e b fn Ogn a b fn ogn a b fn Ωgn a b fn ωgn a b fn Θgn a b Operações com a notação Ogrande fn Ofn c X Ofn Ofn c constante Ofn Ofn Ofn OOfn Ofn Ofn Ogn O max fn gn Ofn Ogn Ofngn fnOgn Ofngn Técnicas de análise de algoritmos Comando Custo Atribuição leitura escrita condição O1 Sequência de comandos Determinado pelo maior tempo na sequência Decisão Tempo da sequência dentro do comando mais a condição Técnicas de análise de algoritmos Comando Custo Laços de repetição Soma do tempo da sequencia dentro do laço mais a condição de parada Multiplicado pelo número de iterações Procedimentos não recursivos Deve ser computado separadamente de acordo com as avaliações anteriores Técnicas de análise de algoritmos Comando Custo Laços de repetição Soma do tempo da sequencia dentro do laço mais a condição de parada Multiplicado pelo número de iterações Procedimentos não recursivos Deve ser computado separadamente de acordo com as avaliações anteriores Classe Nome Situação fn O1 Constante As instruções do algoritmo são executadas um nº fixo de vezes fn Olog n Logarítmica Algoritmos que resolvem um problema transformandoos em tempos menores fn On Linear Em geral um pequeno trabalho é realizado sobre cada elemento da entrada fn On log n n log n Um problema é transformado em problemas menores depois cada um é resolvido independentemente e depois juntamse as soluções fn On2 Quadrática Os itens de dados são processados aos pares em geral um laço dentro do outro fn On3 Cúbica Úteis para resolver problemas pequenos fn O2n Exponencial Uso de força bruta aplicado a um problema fn On Fatorial Uso de força bruta aplicado a um problema Divida sublistas em 2 até alcançar pares de valores Ordene os pares de valores se necessário Junte e ordene as sublistas e repita o processo até juntar a lista completa Ordenação de um vetor Mergesort Problema do Caixeiro Viajante c1 c3 c4 c2 8 5 3 4 9 8 menor percurso c1 c3 c4 c2 c1 E se fossem 50 cidades São 50 possibilidades que é aproximadamente 1064 Visitar n cidades iniciando e terminando em uma mesma cidade e cada cidade deve ser visitada apenas uma vez Classes de algoritmos e medidas de tempo Classe Nº de Complexidade de Operações e Tempos de Execução 1 instrμseg n 10 102 103 Constante O1 1 1 μseg 1 1 μseg 1 1 μseg Logarítimo Olog n 332 3 μseg 664 7 μseg 997 10 μseg Linear On 10 10 μseg 102 100 μseg 103 1 mseg n log n On log n 332 33 μseg 664 664 μseg 9970 10 mseg Quadrático On2 102 100 μseg 104 10 mseg 106 1 seg Cúbico On3 103 1 mseg 106 1 seg 109 167 min Exponencial O2n 1024 10 mseg 1030 317 1017 anos 10301 Classes de algoritmos e medidas de tempo Classe Nº de Complexidade de Operações e Tempos de Execução 1 instrμseg n 104 105 106 Constante O1 1 1 μseg 1 1 μseg 1 1 μseg Logarítimo Olog n 133 13 μseg 166 7 μseg 1993 20 μseg Linear On 104 10 mseg 105 01 seg 106 1 seg n log n On log n 133103 133 mseg 166104 16 seg 1993105 20 seg Quadrático On2 108 17 min 1010 167 min 1012 116 dias Cúbico On3 1012 116 dias 1015 317 anos 1018 31709 anos Exponencial O2n 103010 1030103 10301030 Funções Típicas e estimativas Ogrande Funções Típicas e estimativas Ogrande Referências bibliográficas Observação o conteúdo dos slides foram extraídos e montados a partir das referências bibliográficas SIPSER Michael Introdução a teoria da computação São Paulo Editora Thomson 2007 Capítulo 7 introdução à complexidade de tempo pág 261 268 ZIVIANI Nívio Projeto de algoritmos com implementação em Java e C 2a ed São Paulo Pioneira 2006 Capítulo 1 medida de tempo de execução comportamento assintótico classes assintóticas técnicas de análise de algoritmos CORMEN Thomas H et al Algoritmos Teoria e Prática Rio de Janeiro Campus 2002 Capítulo 3 e 4 crescimento de funções pág 32 e recorrências pág 50 DROZDEK Adam Estrutura de Dados e Algoritmos em C São Paulo Cengage 2002 Capítulo 2 exemplos de análise de algoritmos páginas 54 57 ROSEN Kenneth H Matemática discreta e suas aplicações 6a ed Porto Alegre McGrawHill 2009 Capítulo 3 revisão sobre somatórios páginas 149 158