Java

Disponível somente no TrabalhosFeitos
  • Páginas : 7 (1522 palavras )
  • Download(s) : 0
  • Publicado : 6 de dezembro de 2012
Ler documento completo
Amostra do texto
Classificação e Pesquisa

Ciência da Computação

Prof. Walter Gima
walter.gima@aedu.com

1

https://sites.google.com/a/aedu.com/site-unidadefa5/home/cursos/graduacao/ciencia-da-computacao/4a-serie/classificacao-epesquisa?pli=1

2

Agenda Aula 4

• Pesquisa Sequencial
• Desempenho da Pesquisa Sequencial
• Melhorar Algoritmo
• Exercícios

3

Pesquisa de Dados – Sequencial•

No presente contexto, o termo busca de dados e o termo
classificação de dados tem o mesmo significado: a
recuperação de informações a partir de uma grande massa
de informações previamente armazenadas.



A pesquisa de dados é uma operação presente e necessária
em praticamente qualquer sistema, seja ele computacional
ou não.

4

Pesquisa de Dados – Sequencial



Emespecial os sistemas computadorizados necessitam de
métodos de pesquisa cada vez mais eficientes, pois a
quantidade de dados armazenados pelos sistemas cresce
muito à medida que a complexidade destes sistemas cresce
também.

5

Pesquisa de Dados – Sequencial



O processamento de uma aplicação usualmente envolve a
manipulação de um grande número de tabelas ou arquivos,
que podem serdefinidos como uma coleção de registros,
cada um deles composto por um conjunto de campos.



Usualmente uma tabela armazena informações sobre vários
objetos de um mesmo tipo, a cada objeto correspondendo
uma entrada.

6

Pesquisa de Dados – Sequencial

7

Pesquisa de Dados – Sequencial
Principais Algoritmos de Pesquisa

8

Pesquisa de Dados – Sequencial


A PesquisaSequencial ou Linear é o método mais simples de
pesquisa e consiste em uma varredura serial da tabela,
durante a qual um argumento de pesquisa é comparado com
a chave de cada entrada até que seja encontrada uma que
seja igual, ou ser atingido o final da tabela, caso a chave
procurada não esteja presente na tabela.

9

Pesquisa de Dados – Sequencial



A pesquisa Sequencial pode seraplicada em tabelas
representadas por arrays, arquivos ou listas ligadas. Abaixo é
apresentada uma função que executa pesquisa Sequencial
em uma tabela representada por um array contendo 10
valores inteiros:

10

Pesquisa de Dados – Sequencial
#define MAX 10
int buscaSequencial(int argumento, int tabela[]){
int indice, Retorna;
indice = 0;
while((tabela[indice] != argumento) && (indice< MAX)){
indice++;
}
if(indice < MAX){
Retorna = 1;
}
else{
Retorna = 0;
}
return (Retorna);
}

11

Pesquisa de Dados – Sequencial
main(){
int tabela[MAX];
int indice, argumento;
for(indice = 0; indice < MAX; indice++){
printf("\nDigite o %io termo: ",indice);
scanf("%i", &tabela[indice]);
}
printf("\nDigite um valor para buscar: ");
scanf("%i", &argumento);if(buscaSequencial(argumento, tabela)){
printf("\nO argumento %i existe\n", argumento);
}
else{
printf("\nO argumento %i NAO existe\n", argumento);
}
}

12

Pesquisa Sequencial - Desempenho



O desempenho do algoritmo de pesquisa Sequencial é
sofrível, já que o número médio de comparações para a
localização de uma entrada qualquer na tabela é dado pela
fórmula abaixo, considerando quetodas as entradas
possuem a mesma possibilidade de serem solicitadas.

13

Pesquisa Sequencial - Desempenho







caso médio : NC = (n + 1) /2
onde:
» NC = número de comparações para o caso médio
» n = número de elementos da tabela
Para o exemplo anterior:
» n = 10 elementos na tabela
NC caso médio = (10 + 1) / 2
NC caso médio = 5,5

14

Pesquisa Sequencial -Desempenho


pior caso : NC = n



Já o desempenho na busca para o pior caso é sempre
proporcional ao tamanho da tabela, ou seja, se a tabela tem
100 elementos, então a busca para o pior caso demandará
100 comparações.





Resumidamente pode-se dizer que:
pior caso NC = n
onde:
» NC = número de comparações para o pior caso
» n = número de elementos da tabela

15

Pesquisa...
tracking img