Análise Empírica Trabalho

Nota

Nome do Aluno: Douglas Montovoni Batista_____________________________ Data: 08/04/2022 Prof. Renan Rodrigues de Oliveira

Análise Empírica Trabalho

1. O custo de um algoritmo pode ser analisado de forma empírica, onde o algoritmo é executado em um computador real, sendo o tempo de execução medido diretamente. As medidas de tempo obtidas desta forma podem ser inadequadas e os resultados não devem ser generalizados. Cite no mínimo três vantagens e três desvantagens deste tipo de análise de algoritmos.

Vantagens Desvantagens

• Avaliar o desempenho em uma determinada configuração de computador/linguagem

• Comparar computadores

• Comparar linguagens • Custos não aparentes

• Necessidade de implementar o algoritimo, que depende da habilidade do programador

• Não permite comparações genéricas com outros ‘testes’.

2. Considere dois programas A e B com tempos de execução 100n2 e 5n2, respectivamente, qual é o mais eficiente?

Fazendo uma análise empírica constatei que enquanto n for menor que 200 o

programa mais eficiente é o B, quando n for igual a 200 os dois programas serão

equivalentes e quando n for maior que 200 o programa A é o mais eficiente.

3. Considerando a implementação parcial do programa em C disponível no Moodle, faça uma análise empírica dos seguintes algoritmos de ordenação: Bubble Sort, Quicksort e Insertion Sort. O código fonte já disponibiliza a implementação dos dois primeiros algoritmos e uma estratégia para contar a quantidade de trocas para realizar a ordenação e a determinação do tempo de execução dos algoritmos. Pesquise na Internet uma implementação do algoritmo Insertion Sort (não é necessário fazer sua própria implementação) e realize as alterações necessárias para realizar o experimento.

Plano para a Análise Empírica de Algoritmos

a) Descreva a configuração da máquina onde o experimento foi realizado.

Placa-mãe Asus P8H61-M LX3 R2.0

Intel(R) Core(TM) i5-2310 CPU @ 2.90GHz

Clock 100MHz

Memória Ram ddr3 16GB 1.333 MHz (0,8 ns)

Cache size 6144 KB

Sistema Operacional Ubuntu 16.04 x64

b) Descreva o objetivo do experimento.

Avaliar o desempenho dos algoritmos Bubble Sort, QuickSort e InsertSort.

c) Descreva a métrica de eficiência a ser medida e a unidade de medida

Amostra de entradas foram geradas por um algoritimo de geração de números

inteiros aleatórios.

d) Descreva