Relatório técnico de analise experimental da complexidade de algoritmos em classificação de dados em tempo linear

UNIVERSIDADE FEDERAL DO TOCANTINS Programa de Pós-Graduação em Modelagem Computacional de Sistemas Mestrado Profissional Interdisciplinar em Modelagem Computacional de Sistemas Campus Universitário de Palmas

Paulo Augusto Valéria Mota

RELATÓRIO TÉCNICO DE ANALISE EXPERIMENTAL DA COMPLEXIDADE DE ALGORITMOS EM CLASSIFICAÇÃO DE DADOS EM TEMPO LINEAR

Palmas 2012

SUMÁRIO

1.

INTRODUÇÃO .............................................................................................................................. 6 1.1 1.2 Justificativas ............................................................................................................................ 6 Objetivos ................................................................................................................................. 6

2.

FUNDAMENTAÇÃO TEÓRICA .................................................................................................. 6 2.1 Counting Sort .......................................................................................................................... 7 Analise de Complexidade de Algoritmo .......................................................................... 8

2.1.1 2.2

Brucket Sort ............................................................................................................................ 8 Analise de Complexidade de Algoritmo .......................................................................... 9

2.2.1 2.3

Radix Sort................................................................................................................................ 9 Analise de Complexidade de Algoritmo ........................................................................ 10

2.3.1 3. 4. 5. 6.

METODOLOGIA ......................................................................................................................... 10 RESULTADOS EXPERIMENTAIS