Atps classificação e pesquisa

Páginas: 13 (3021 palavras) Publicado: 27 de novembro de 2012
1 Método de busca com o melhor desempenho computacional
Considerando os parâmetros de testes definidos no ATPS, foi possível identificar que o melhor método de busca sem a ordenação dos dados é o linear com sentinela, porém se o valor procurado não estiver no vetor, o tempo e a quantidade de testes realizados serão exatamente iguais ao da busca linear, pois a chave será localizada apenas nofinal da base de dados.
O calculo de tempo foi realizado através da quantidade de ciclos do processador (clock), mas como a base utilizada nos testes é pequena o processo é muito rápido para realizar uma comparação precisa entre os algoritmos, além disso foi possível notar que os valores definidos para busca no ATPS não estão disponíveis após a geração dos números aleatórios e dessa forma osalgoritmos de busca não localizarão os valores o que forçara percorrer o vetor até o final.

2 Desempenho da busca binária x busca linear x busca linear com sentinela
Após a ordenação dos dados fica claro que o melhor método de busca é a binária como mostra a Figura 1, pois tanto o tempo quanto a quantidade de processamento é muito menor do que as outras técnicas de busca.
O principal pontoé se a ordenação da base de dados é viável para aplicar esse tipo de técnica, pois dependendo do tamanho da base a ordenação pode se tornar muito lenta e exigir muito processamento.
A ordenação através de algoritmos como bubblesort e seleção demonstraram bons resultados, mas ainda assim exigem mais processamento do que as buscas em bases que não foram ordenadas porem se a ordenação forrealizada periodicamente ou no momento em que os dados são inseridos a busca binária torna-se viável, pois a localização e o tempo de processamento são muito mais rápidos do que as demais técnicas.
Tipo de teste | Tamanho Vetor | Quantidade de testes |
Busca Linear | 1.000 | 1.000 |
BuscaLinear com Sentinela | 1.000 | 1.000 |
Busca Binária | 1.000 | 9 |
Bubble Sort | 1.000 | 244.968 |
Seleção | 1.000 | 56.738 |

Figura 1 – Resultados dostestes realizados com os algoritmos de busca após a ordenação da base

3 Conclusão
Após a realização das baterias de testes foi possível concluir que existem algoritmos de localização e ordenação mais eficientes do que outros, porém a aplicação e a utilização de cada um depende da situação e principalmente do tamanho da base de dados que será manipulada.
Considerando os parâmetros utilizadosnesses testes observamos que o melhor comportamento dos algoritmos de ordenação e seleção foram obtidos pelo método seleção e a busca binária, mas isso não significa que são os melhores para todas as situações, pois todos possuem suas particularidades e deficiências.

Anexo I
Código completo para realizar a bateria de testes descritas abaixo.
/*
Name: ATPS - Classificação e PesquisaDescription: Bateria de testes de busca linear, linear com sentinela e binária ordenação bubblesort e seleção
*/

#include
#include
#include
#include

#define tempo 2000
#define search_p 87
#define search_s 100001

//prototipos das funções
void bateria_testes(int tam, int t);
void linear(int n, int t, int *p_int, double *p);
void linear_sentinela(int n, int t, int *p_int, double *p);void binaria(int n, int t, int *p_int, double *p);
void bubblesort(int n, int t, int *p_int, double *p);
void selecao(int n, int t, int *p_int, double *p);
double unif(long int *seed, double low, double high);
int inteiros_unif(long int *seed, int low, int high);

main(){

//declaração de variaveis
int op=0, tipo;

while (op!=5){

system("cls");...
Ler documento completo

Por favor, assinar para o acesso.

Estes textos também podem ser interessantes

  • Atps Classificacao E Pesquisa
  • atps classificação e pesquisa
  • ATPS Classificação e Pesquisa
  • Atps classificação e pesquisa
  • Atps classificação e pesquisa
  • ATPS CLASSIFICAÇÃO E PESQUISA
  • 215741614 ATPS Classificacao e Pesquisa
  • classificação e pesquisa atps

Seja um membro do Trabalhos Feitos

CADASTRE-SE AGORA!