engenharia mecanica

in

Trabalho de Probabilidade e Estatística
- Teste de Hipóteses -

ufr gs. br/
~la
bia nch Algoritimos de ordenação, em ciência da computação, são algoritimos que efetuam uma ordenação sobre um conjunto de dados.
Para o escopo desse trabalho, foi implementado um modelo na lingugem Java que faz a avaliação de desempenho sobre algoritimos de ordenação. Para isso, utiliza-se determinado algoritimo para ordenar 10.000 elementos aleatórios e mede-se o tempo gasto no processo
(em milisegundos). Esse processo é repetido 20 vezes para cada algoritimo e sobre os resultados são calculados a média e desvio padrão.

INFORMAÇÕES INICIAIS

Tema: Comparação de dois algoritimos de ordenação (QuickSort e HeapSort).
Variável a ser medida: Tempo médio de execução.

Grupos amostrais comparados: 20 ordenações de 10.000 elementos aletórios para cada algoritimo. Nível de significância: 0,05 ou 5%

Amostra: Tempos obtidos em cada ordenação (em milisegundos):

* QuickSort (1):
Tempos Obtidos: [ 4, 4, 3, 3, 4, 4, 4, 6, 3, 20, 4, 4, 3, 3, 3, 4, 4, 29, 3, 3 ]
Média: 5,75
Desvio Padrão: 6,7845

htt p:/ /in
f.

* HeapSort (2):
Tempos Obtidos: [ 2, 2, 1, 2, 2, 2, 2, 2, 17, 2, 2, 1, 2, 2, 7, 2, 2, 3, 1, 2 ]
Média: 2,90
Desvio Padrão: 3,6282

Hipótese: HeapSort é mais eficiente do que o QuickSort, isto é, possui menor tempo de execução. DESENVOLVIMENTO

Tem-se as seguintes hipóteses

in ufr gs. br/ ~la bia nch

Estatística Tabelada:

t-tab = 1,70

Estatística Calculada:

t-calc = 1,65

Relação entre o p-valor e o nível de significância: p-valor = 0,054 significância = 0,05

htt p:/ /in
f.

Decisão: Temos que,

Logo, H0 foi aceita.

Conclusão: Com 95% de confiança, não se pode afirmar que o algoritimo Heap Sort é mais eficiente que o algoritimo Quick Sort conforme o tempo de execução.
Entretanto, percebe-se que se fosse escolhida uma significância superior a 0,054 (p-valor),
H0 seria rejeitada.

htt
p:/