PAA-9-analiseEmpirica

Prévia do material em texto

Profa. Thaís Alves Burity Rocha 
EFICIÊNCIA DE ALGORITMOS 
Agenda 
 Introdução 
 Objetivos 
 Plano geral 
 Caso médio 
 Representação dos resultados 
 Tabela 
Gráfico 
 Vantagens e desvantagens 
 
 
 
Introdução 
 As técnicas de análise assintótica podem ser 
aplicadas com sucesso para algoritmos pequenos 
 
 Porém, mesmo para alguns problemas simples, a 
análise assintótica pode ser muito difícil 
 Em particular, para a análise do caso médio 
 
 A principal alternativa à análise assintótica é a 
análise empírica (ou experimental) 
 
 
Introdução 
 A análise empírica de um algoritmo é feita através 
da coleta de dados sobre a execução de um 
programa que implementa o algoritmo 
 
 É uma forma dinâmica de avaliar o desempenho 
do algoritmo 
 
 Capaz de avaliar o algoritmo no “caso médio”, ao 
invés de se ater ao “pior caso” 
 Análise do pior caso é pessimista 
 
 
Análise empírica: Objetivos 
 Testar algoritmo, procurando achar erros 
 A ausência de erros não prova que o algoritmo está 
correto 
 A presença de erros prova que o algoritmo está 
errado 
 
 Comparar a eficiência de diferentes algoritmos 
 Tomada de decisão 
 
Análise empírica: Objetivos 
 Comparar implementações alternativas do mesmo 
algoritmo 
 Identificar “gargalos”, ou seja, as operações mais 
“caras” 
 Encontrar uma implementação mais eficiente 
 
 Estimar a complexidade do algoritmo 
 
 Conclusão: O projeto do experimento depende 
diretamente do seu objetivo! 
 
 
Análise empírica: Plano geral 
 Entender o propósito do experimento 
 
 Escolher uma métrica de eficiência M a ser medida e a 
unidade de medida 
 Unidade de tempo: Contar quanto tempo cada parte do 
algoritmo demora para executar 
 Em Java, usar System.currentTimeMillis() antes e depois da 
chamada de um método e calcular fim - início 
 
 Número de operações básicas: Contar quantas vezes cada 
ação é executada 
 
Análise empírica: Plano geral (cont.) 
 Escolher as características da amostra de entrada 
 O tamanho da amostra 
 
 A faixa de tamanhos de entrada 
 Pode seguir um padrão 
 Exemplo: n, 10n, 102n, 103n, 104n, 105n… 
 
 Um procedimento para gerar amostras no intervalo 
escolhido 
 Incluindo entradas aleatórias 
 Pensar em entradas que caracterizam pior/melhor caso 
 
Análise empírica: Plano geral (cont.) 
 Escrever um programa que implementa o algoritmo a 
ser avaliado 
 Implementação deve ser propícia para análise 
 Isolar o algoritmo 
 
 Gerar amostra de entrada 
 
 Executar o algoritmo sobre a amostra e guardar 
resultados 
 
 Analisar resultados 
 
Análise empírica: Caso médio 
 Utilizar entradas típicas (representativas) 
 
 Utilizar várias entradas de um mesmo tamanho 
 
 Calcular a média dos resultados para cada 
tamanho 
Análise empírica: Caso médio 
 Exemplo 
 
 
 
Resultados para 
entradas de tamanho 
10 
Resultados para 
entradas de tamanho 
102 
Resultados para 
entradas de tamanho 
103 
Resultado 1 x1 y1 z1 
Resultado 2 x2 y2 z2 
.... ... ... .... 
Resultado n xn yn zn 
Média dos 
resultados 
(x1+x2+...+xn)/n (y1+y2+....+yn)/n (z1+z2+...+zn)/n 
Representação dos resultados 
 Os resultados podem ser representados através 
duas formas: 
 Tabela 
 
Gráfico: 
 Scatterplot (pontos em um sistema de coordenadas 
cartesianas) 
 
Representação dos resultados: Tabela 
 A partir de dados na tabela podemos: 
 Calcular a relação M(n)/g(n), onde g(n) é a classe (de 
eficiência) candidata e M(n) é o resultado. Neste caso, 
os dados devem convergir para uma constante à 
medida que n cresce 
 
 Calcular a relação M(2n)/M(n) e verificar como o 
tempo de execução muda dobrando o tamanho da 
entrada 
Representação dos resultados: Gráfico 
 A partir dos dados em gráficos, podemos: 
 
Observar a forma das curvas e estimar a classe de 
eficiência mais provável 
tempo 
tamanho (n) 
Representação dos resultados: Gráfico 
Resultados 
Curva da classe 
provável 
Análise empírica: Vantagens 
 Aplicável a qualquer algoritmo 
 
 Permite ter uma “noção” da ordem de 
complexidade do algoritmo 
 Notação O 
 
 Permite identificar pontos de melhoria no algoritmo, 
sem o custo da análise matemática 
Análise empírica: Desvantagens 
 Depende das características específicas do 
ambiente de teste 
 Não permite comparações genéricas com algoritmos 
cujos testes foram realizados em outro ambiente 
Exercício 
 Planejar e executar experimentos para fazer análise 
comparativa da eficiência dos algoritmos de 
ordenação 
 Selection Sort 
 Insertion Sort 
 Bubble Sort 
 Merge Sort 
 Shell Sort 
 Quicksort 
 
 Dica: Para gerar gráfico, em Java, usar JFreeChart 
Conteúdo da primeira VA 
 Corretude de algoritmos 
 Corretude de algoritmos recursivos 
 Indução matemática 
 
 Corretude de algoritmos iterativos 
 Invariantes de laço 
Conteúdo da primeira VA 
 Eficiência de Algoritmos 
 Notação assintótica 
 Análise assintótica 
 
 Eficiência de algoritmos iterativos 
 Somatório (detalhado ou simplificado) 
 
 Eficiência de algoritmos recursivos 
 Recorrências 
 Substituições retrógadas 
 Árvore de recursão 
 Teorema mestre