LISTA 3

Belo Horizonte

LISTA 3

Trabalho apresentado a disciplina
Algoritmo e Estruturas de Dados, curso de graduação em Sistemas de Informação

Belo Horizonte

Exercícios
1. Considere as técnicas de pesquisa seqüencial, pesquisa binária e a pesquisa baseada em hashing.
a) Descreva as vantagens e desvantagens de cada uma das técnicas acima, dando um exemplo de situação na qual você usaria cada uma delas.

Pesquisa seqüencial
Algoritmo que procura em todo o conjunto de dados.
Vantagem: simplicidade
Desvantagem: Se o conjunto de dados for muito grande esta pesquisa fica inviável.

Pesquisa Binária
Seu algoritmo minimiza o numero de operações ao particionar o conjunto a cada passo.
Vantagem: busca mais rápida
Desvantagem: Quando o elemento não é encontrado.

Pesquisa baseada em hashing
Método que realiza um endereçamento direto de um valor em uma tabela.
Vantagem: O método de armazenar os dados é basicamente o mesmo de localizar.
Desvantagem: Há possibilidades de ocorrer colisões de endereço.

b) Dê a ordem do pior caso e do caso médio de tempo de execução para cada método

Pesquisa seqüencial
Pior caso: O(1)
Caso médio: O(n)

Pesquisa Binária
Pior caso: O(1)
Caso médio: O(logn)

Pesquisa baseada em hashing
Pior caso:
Caso médio:

2. Desenhe a árvore binária de pesquisa que resulta da