engenharia mecanica
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:/