Análise de Algoritmos de Busca

Prévia do material em texto

Análise de Algoritmos
ANÁLISE DE ALGORITMOS DE BUSCAANÁLISE DE ALGORITMOS DE BUSCA
Bacharelado em Ciências da Computação
Flávia Coelho
flaviacoelho@ufersa.edu.br
Atualizado em Agosto de 2016
 
Sumário
● Introdução
● Busca Sequencial 
● Busca Binária
● Árvores Binárias de Pesquisa
● Transformação de chave (Hashing)
 
Algoritmos de Busca
● Trata a recuperação da informação, a partir de uma grande 
massa de dados previamente armazenados
● Dados são organizados em registros, cada um possuindo uma 
chave a ser usada na pesquisa
● Um conjunto de registros é chamado de tabela ou arquivo
– Tabela é associado a entidades de vida curta (memória interna)
– Arquivo é associado a entidades de vida longa (memória externa)
● Objetivo da busca é recuperar uma ou mais ocorrências de 
registros com chaves iguais à chave de pesquisa
 
Sumário
● Introdução
● Busca Sequencial 
● Busca Binária
● Árvores Binárias de Pesquisa
● Transformação de chave (Hashing)
 
Busca Sequencial
● É o método mais simples
● A partir do primeiro registro, pesquise 
sequencialmente até encontrar a 
chave procurada; então pare
● Este método é adequado para buscas 
em tabelas com um pequeno número 
de registros
 
Algoritmo de Busca Sequencial
buscaSequencial(vetor[], n, valor){
  para(i = 0; i < n; i++) 
    se (vetor[i] == valor)
      retorne i 
  retorne ­1 //não encontrado
} 
Ω(1)
Θ(n)
O(n)
 
Sumário
● Introdução
● Busca Sequencial 
● Busca Binária
● Árvores Binárias de Pesquisa
● Transformação de chave (Hashing)
 
Busca Binária
● A busca pode ser muito mais eficiente 
se os registros forem mantidos em 
ordem
● Para saber se uma chave está presente 
na tabela, compare a chave com o 
registro que está na posição do meio da 
tabela
 
Algoritmo de Busca Binária
buscaBinaria(v[], n, valor){
  inf = 0   //primeiro elemento do vetor
  sup = n­1 //ultimo elemento do vetor
  enquanto(inf <= sup){
    meio = inf + (sup­inf)/2; 
    se(chave == v[meio]) retorne meio
    contrario se(valor < v[meio]) sup = meio­1
    contrario inf = meio+1
  }
  retorne ­1 //não encontrado
} 
Ω(1)
Θ(lgn)
O(lgn)
 
Sumário
● Introdução
● Busca Sequencial 
● Busca Binária
● Árvores Binárias de Pesquisa
● Transformação de chave (Hashing)
 
Árvores Binárias de Pesquisa
● Estrutura de dados eficiente para armazenar 
(e recuperar dados)
● Árvore consiste de um nodo “raiz” mais 0 ou 2 
subárvores binárias distintas
● Vantagens
● Acesso direto e sequencial eficientes
● Facilidade de inserção e retirada de registros
● Boa taxa de utilização de memória
● Utilização de memória primária e secundária
 
Árvores Binárias de Pesquisa sem 
Balanceamento
● Quando um nodo tem 2 filhos, eles são chamados 
filhos à esquerda e à direita do nodo
● O número de subárvores de um nodo é chamado 
grau daquele nodo
● Um nodo de grau zero é chamado de nodo externo 
ou folha
● Os outros nodos são chamados nodos internos
 
Árvores Binárias de Pesquisa sem 
Balanceamento
● Uma árvore binária de pesquisa é uma árvore 
binária em que todo nodo interno contém um 
registro e, para cada nodo, a seguinte 
propriedade é verdadeira
● Registros com chaves menores estão na subárvore 
esquerda e todos os registros com chaves maiores 
estão na subárvore direita
● A altura de um nodo é o comprimento do caminho 
mais longo deste nodo até um nodo folha
 
Árvores Binárias de Pesquisa sem 
Balanceamento
estrutura ArvoreBinaria{  
  subestrutura No{
    valor
    esq
    dir
  }
  /*omitidas funções de   
    inserção, exclusão,   
    caminhamento,etc.*/ 
}
algoritmo pesquisa(valor, no){
  se (no == nulo) 
    retorne null; //não encontrou
  contrario se(valor < no.valor) 
    retorne pesquisa(valor, no.esq)
  contrario se(valor > no.valor)
    retorne pesquisa(valor, no.dir)
  contrario
    retorne valor 
}
Ω(1)
Θ(lgn)
O(n)
ENTRADA EM ORDEM 
CRESCENTE OU DECRESCENTE
 
Sumário
● Introdução
● Busca Sequencial 
● Busca Binária
● Árvores de Pesquisa
● Transformação de chave (Hashing)
 
Hashing
● Matematicamente, é uma função de 
espalhamento (isto é, do inglês hash), h(k), a 
qual associa uma chave k a um endereço
● Permite armazenar e recuperar rapidamente 
dados por chave
 
Visão Geral
● Conceitos centrais
● Tabela de Hashing, estrutura que permite o acesso aos 
subconjuntos
● Função de Hashing, função que realiza um mapeamento entre 
valores de chaves e entradas na tabela
● Possui uma série de limitações em relação às árvores
● Não permite recuperar/imprimir todos os elementos em ordem de 
chave nem outras operações que exijam sequência dos dados
● Não permite operações do tipo recuperar o elemento com a 
maior ou a menor chave
 
Hashing
Exemplo
 
Hashing
Exemplo
Colisões
 
Funções Hash e Colisões
 
Exemplo
● h(k) = k mod 10
● Entrada: 9877, 2007, 1000, 9530, 3013, 9879 e 1057
h(1000) = 1000 mod 10 
h(1000) = 0
 
h(1057) = 1057 mod 10 
h(1000) = 7
 
Hashing
Complexidade Computacional
● Melhor caso é Ω(1)
● Pior e médio casos dependem da 
solução aplicada para o tratamento de 
colisões
 
Leitura Recomendada
N. Ziviani. Projeto de Algoritmos com 
Implementações em Java e C++. 
Thompson Learning, 2007, pp.171-215
M. T. Goodrich, R. Tamassia. Estruturas 
de Dados e Algoritmos em Java. 
Quarta Edição, Bookman, 2006, pp. 
335-348, 373-382
	Slide 1
	Slide 2
	Slide 3
	Slide 4
	Slide 5
	Slide 6
	Slide 7
	Slide 8
	Slide 9
	Slide 10
	Slide 11
	Slide 12
	Slide 13
	Slide 14
	Slide 15
	Slide 16
	Slide 17
	Slide 18
	Slide 19
	Slide 20
	Slide 21
	Slide 22
	Slide 23