Baixe o app para aproveitar ainda mais
Prévia do material em texto
1 Aula 02 – Custos de um algoritmo e funções de complexidade MC3305 Algoritmos e Estruturas de Dados II Prof. Jesús P. Mena-Chalco jesus.mena@ufabc.edu.br 2Q-2014 2 Custo de um algoritmo e funções de complexidade Introdução baseada nas aulas do Prof. Antonio A. F. Loureiro (UFMG) 3 Algoritmos Os algoritmos fazem parte do dia-a-dia das pessoas: Receita culinária. Indicações de como montar um aparelho. Instruções para o uso de medicamento. Algoritmo: Sequência de passos ou ações executáveis para a obtenção de uma solução para um determinado tipo de problema. 4 Estrutura de dados Estrutura de dados e algoritmos estão intimamente ligados: Não se pode estudar ED sem considerar os algoritmos associados a elas; Asssim como a escolha dos algoritmos (em geral) depende da representação e da ED. 5 Programas Programar é basicamente: Estruturar dados, e Construir algoritmos. Programas: Representam uma classe especial de algoritmos capazes de serem seguidos por computadores. 6 Medida do tempo de execução de um programa Algoritmos são encontrados em todas as áreas de Computação. O projeto de algoritmos é influenciado pelo estudo de seus comportamentos. Os algoritmos podem ser estudados considerandos, entre outros, dois aspectos: Tempo de execução. Espaço ocupado (quantidade de memória). 7 (1) Análise de um algoritmo particular Qual é o custo de usar um dado algoritmo para resolver um problema específico? Características que devem ser investigadas: Tempo de execução. Quantidade de memória. 8 (2) Análise de uma classe de algoritmos Qual é o algoritmo de menos custo possível para resolver um problema particular? Toda uma familia de algoritmos é investigada. Procura-se identificar um que seja o melhor possível. Colocam-se limites para a complexidade computacional dos algoritmos pertencentes à classe. 9 Custo de um algoritmo Se conseguirmos determinar o menor custo possível para resolver problemas de uma dada classe, então teremos a medida da dificuldade inerente para resolver o problema. 10 Custo de um algoritmo Se conseguirmos determinar o menor custo possível para resolver problemas de uma dada classe, então teremos a medida da dificuldade inerente para resolver o problema. Quando um algoritmo é igual ao menor custo possível, o algoritmo é ótimo para a medida de custo considerada. 11 Custo de um algoritmo Se conseguirmos determinar o menor custo possível para resolver problemas de uma dada classe, então teremos a medida da dificuldade inerente para resolver o problema. Quando um algoritmo é igual ao menor custo possível, o algoritmo é ótimo para a medida de custo considerada. Podem existir vários algoritmos para resolver um mesmo problema. 12 Custo de um algoritmo Se conseguirmos determinar o menor custo possível para resolver problemas de uma dada classe, então teremos a medida da dificuldade inerente para resolver o problema. Quando um algoritmo é igual ao menor custo possível, o algoritmo é ótimo para a medida de custo considerada. Podem existir vários algoritmos para resolver um mesmo problema. → Se a mesma medida de custo é aplicada a diferentes algoritmos então é possível compará-los e escolher o mais adequado. 13 Medida de custo pela execução de um programa em uma plataforma real 14 (1) medida de custo pela execução de um programa em uma plataforma real Tais medidas são bastante inadequadas e os resultados jamais devem ser generalizados: Os resultados são dependentes do compilador que pode favorecer algumas construções em detrimento de outras; Os resultados dependem de hardware; Quanto grandes quantidades de memória são utilizadas, as medidas de tempo podem depender deste aspecto. 15 (1) medida de custo pela execução de um programa em uma plataforma real Tais medidas são bastante inadequadas e os resultados jamais devem ser generalizados: Os resultados são dependentes do compilador que pode favorecer algumas construções em detrimento de outras; Os resultados dependem de hardware; Quanto grandes quantidades de memória são utilizadas, as medidas de tempo podem depender deste aspecto. Apesar disso, há argumentos a favor de se obterem medidas reais de tempo: Exemplo: Quando há vários algoritmos distintos para resolver o problema; Assim, são considerados tanto os custos reais das operações como os custos não aparentes, tais como alocação de memória, indexação, carga, dentre outros. 16 Medida de custo por meio de um modelo matemático 17 (2) medida de custo por meio de um modelo matemático Usa um modelo matemático baseado em um computador idealizado. Deve ser especificado o conjunto de operações e seus custos de execuções. É mais usual ignorar o custo de algumas das operações e considerar apenas as mais significantes. Em algoritmos de ordenação: Consideramos o conjunto de comparações entre os elementos do conjunto a ser ordenado e ignoramos as operações aritméticas, de atribuição e manipulação de índices, caso existam. 18 Função de complexidade 19 Função de complexidade Para medir o custo de execução de um algoritmo, é comum definir uma função de custo ou função de complexidade f. 20 Função de complexidade Para medir o custo de execução de um algoritmo, é comum definir uma função de custo ou função de complexidade f. Função de complexidade de tempo: mede o tempo necessário para executar um algoritmo para um problema de tamanho n. Função de complexidade de espaço: mede a memória necessária para executar um algoritmo para um problema de tamanho n. 21 Função de complexidade Para medir o custo de execução de um algoritmo, é comum definir uma função de custo ou função de complexidade f. Função de complexidade de tempo: mede o tempo necessário para executar um algoritmo para um problema de tamanho n. Função de complexidade de espaço: mede a memória necessária para executar um algoritmo para um problema de tamanho n. Utilizaremos f para denotar uma função de complexidade de tempo daqui para frente. Na realidade, f não representa tempo diretamente, mas o número de vezes que determinada operação (considerada relevante) é realizada. 22 Exemplo: Maior elemento Considere o algoritmo para encontrar o maior elemento de um vetor de inteiros 23 Exemplo: Maior elemento 24 Exemplo: Maior elemento Seja f uma função de complexidade tal que é o número de comparações entre os elementos de A. Logo: 25 Exemplo: Maior elemento 26 Tamanho da entrada de dados A medida do custo de execução de um algoritmo depende principalmente do tamanho de entrada dos dados. É comum considerar o tempo de execução de um programa como uma função do tamanho de entrada. 27 Tamanho da entrada de dados A medida do custo de execução de um algoritmo depende principalmente do tamanho de entrada dos dados. É comum considerar o tempo de execução de um programa como uma função do tamanho de entrada. → No caso da função para determinar o máximo, o custo é unifome (n-1) sobre todos os problemas de tamanho n. → Já para um algoritmos de ordenação isso não ocorre: se os dados de entrada estiverem quase ordenados, então o algoritmo pode ter que trabalhar menos. 28 Melhor caso, pior caso e caso médio Melhor caso: Menor tempo de execução sobre todas as entradas de tamanho n. Pior caso: Maior tempo de execução sobre todas as entradas de tamanho n. Caso médio (caso esperado): Média dos tempos de execução de todas as entradas de tamanho n. Aqui supoe-se uma distribuição de probabilidades sobre o conjunto de entradas de tamanho n. 29Exemplo: Busca de um registro Considere o problema de acessar os registros de um arquivo (cada registro tem chave única). O problema: Dada uma chave qualquer, localize o registro que contenha esta chave → Considere o algoritmo de busca/pesquisa sequencial 30 Exemplo: Busca de um registro 31 Exemplo: Busca de um registro 32 Exemplo: Busca de um registro Seja f uma função de complexidade tal que f(n) é o número de registros consultados. Melhor caso: Quando o elemento procurado é o primeiro consultado 33 Exemplo: Busca de um registro Seja f uma função de complexidade tal que f(n) é o número de registros consultados. Melhor caso: Pior caso: Quando o elemento procurado é o primeiro consultado Quando o elemento procurado é o último consultado 34 Exemplo: Busca de um registro Seja f uma função de complexidade tal que f(n) é o número de registros consultados. Melhor caso: Pior caso: Caso médio: Quando o elemento procurado é o primeiro consultado Quando o elemento procurado é o último consultado 35 Exemplo: Busca de um registro (caso médio) Consideremos que toda pesquisa recupera um elemento. Para recuperar o i-ésimo elemento são necessárias i comparações. 36 Exemplo: Busca de um registro (caso médio) Consideremos que toda pesquisa recupera um elemento. Para recuperar o i-ésimo elemento são necessárias i comparações. Seja a probabilidade de que o i-ésimo elemento seja procurado: 37 Exemplo: Busca de um registro (caso médio) Consideremos que toda pesquisa recupera um elemento. Para recuperar o i-ésimo elemento são necessárias i comparações. Seja a probabilidade de que o i-ésimo elemento seja procurado: Se cada elemento tiver a mesma probabilidade de ser escolhido que todos os outros, então Uma pesquisa examina aproximadamente metade dos elementos 38 Maior e Menor elementos Consideremos diferentes versões para o maior e o menor elemento de um vetor de n inteiros, para n>=1. A:= 0 1 2 3 4 5 6 39 Maior e Menor elementos (versão 1) Identifique a função de complexidade f(n) para o vetor A de n elementos: - Melhor caso: - Pior caso: - Caso médio: 40 Maior e Menor elementos (versão 1) Identifique a função de complexidade f(n) para o vetor A de n elementos: - Melhor caso: - Pior caso: - Caso médio: 41 Maior e Menor elementos (versão 2) Identifique a função de complexidade f(n) para o vetor A de n elementos: - Melhor caso: - Pior caso: - Caso médio: 42 Maior e Menor elementos (versão 2) Identifique a função de complexidade f(n) para o vetor A de n elementos: - Melhor caso: - Pior caso: - Caso médio: Quando os elementos estão em ordem crescente. 43 Maior e Menor elementos (versão 2) Identifique a função de complexidade f(n) para o vetor A de n elementos: - Melhor caso: - Pior caso: - Caso médio: Quando os elementos estão em ordem crescente. Quando os elementos estão em ordem decrescente. 44 Maior e Menor elementos (versão 2) Identifique a função de complexidade f(n) para o vetor A de n elementos: - Melhor caso: - Pior caso: - Caso médio: Quando os elementos estão em ordem crescente. Quando os elementos estão em ordem decrescente. Quando metade das vezes max>=A[i] 45 Maior e Menor elementos (versão 3) A:= 0 1 2 3 4 5 6 46 Maior e Menor elementos (versão 3) A:= 0 1 2 3 4 5 6 7 3 0 1 2 3 4 5 6 Min = 3 Max = 7 47 Maior e Menor elementos (versão 3) A:= 0 1 2 3 4 5 6 7 3 0 1 2 3 4 5 6 60 5 0 1 2 3 4 5 6 > Min = 3 Max = 7 Min = 3 Max = 60 48 Maior e Menor elementos (versão 3) A:= 0 1 2 3 4 5 6 7 3 0 1 2 3 4 5 6 60 5 0 1 2 3 4 5 6 > Min = 3 Max = 7 Min = 3 Max = 60 1 90 0 1 2 3 4 5 6 < Min = -1 Max = 90 49 Maior e Menor elementos (versão 3) A:= 0 1 2 3 4 5 6 7 3 0 1 2 3 4 5 6 60 5 0 1 2 3 4 5 6 > Min = 3 Max = 7 Min = 3 Max = 60 1 90 0 1 2 3 4 5 6 < Min = -1 Max = 90 2 0 1 2 3 4 5 6 2 Min = -2Max = 90 50 Maior e Menor elementos (versão 3) A:= 0 1 2 3 4 5 6 7 3 0 1 2 3 4 5 6 60 5 0 1 2 3 4 5 6 > Min = 3 Max = 7 Min = 3 Max = 60 1 90 0 1 2 3 4 5 6 < Min = -1 Max = 90 2 0 1 2 3 4 5 6 2 Comparações =10 1 3 3 3 Min = -2 Max = 90 51 Versão 3 Identifique a função de complexidade f(n) para o vetor A de n elementos: - Melhor caso - Pior caso - Caso médio 52 Versão 3 Identifique a função de complexidade f(n) para o vetor A de n elementos: - Melhor caso - Pior caso - Caso médio 1 comparação (n-2)/2comparações (n-2)/2 + (n-2/2) comparações 53 Versão 3 Identifique a função de complexidade f(n) para o vetor A de n elementos: - Melhor caso - Pior caso - Caso médio 1 comparação (n-2)/2comparações (n-2)/2 + (n-2/2) comparações 54 Maior e Menor elementos 55 Maior e Menor elementos 0 500 1000 1500 2000 2500 maxmin1 maxmin2 maxmin3 n f(n ) Melhor caso 56 Funções de complexidade Não existe algoritmo que identifique o maior e o menor elemento de um vetor de n elementos com uma função menor a: 57 Comportamento assintótico de funções O parâmetro n fornece uma medida da dificuldade para se resolver o problema. A escolha de um algoritmo não é um problema crítico para problemas de tamanho pequeno. A análise de algoritmos é realizada para valores grandes de n. 58 Comportamento assintótico de funções Estudaremos o comportamento assintótico das funções de custo (comportamento de suas funções de custo para valores grande de n). O comportamento assintótico de f(n) representa o limite do comportamento de custo, quando n cresce. 59 Notação assintótica de funções 60 Atividade para casa: Hierarquia de funções Estabelecer uma herarquia de funções, para um valor de n muito grande. 61 Slide 1 Slide 2 Slide 3 Slide 4 Slide 5 Slide 6 Slide 7 Slide 8 Slide 9 Slide 10 Slide 11 Slide 12 Slide 13 Slide 14 Slide 15 Slide 16 Slide 17 Slide 18 Slide 19 Slide 20 Slide 21 Slide 22 Slide 23 Slide 24 Slide 25 Slide 26 Slide 27 Slide 28 Slide 29 Slide 30 Slide 31 Slide 32 Slide 33 Slide 34 Slide 35 Slide 36 Slide 38 Slide 39 Slide 40 Slide 41 Slide 42 Slide 43 Slide 44 Slide 51 Slide 52 Slide 54 Slide 55 Slide 56 Slide 57 Slide 58 Slide 59 Slide 60 Slide 61
Compartilhar