pesquisa sequencial e binária

Prévia do material em texto

Algoritmos e Estruturas de Dados I
Análise de Complexidade de Algoritmos
Curso de Engenharia de Computação
CEFET-MG
2015/1
Análise de complexidade de algoritmos
 O problema da Pesquisa
 Verificar a presença ou não de um dado elemento em um 
conjunto
 Algoritmos para o problema da pesquisa
 Pesquisa sequencial em vetor não ordenado
 Pesquisa sequencial em vetor ordenado
 Pesquisa binária
 Soluções mais avançadas
Problema: busca/pesquisa/procura em vetor
 Problema
 dado um conjunto de elementos, verificar se um dado 
elemento ocorre no conjunto
 pesquisa ou busca ou procura – search
 Há vários algoritmos e estruturas de dados para este problema:
 pesquisa sequencial em vetor (array) não ordenado
 pesquisa sequencial em vetor ordenado
 pesquisa binária
 hashing 
 árvores de pesquisa (AEDS2)
Classificação dos resultados da pesquisa 
 Duas respostas possíveis
 o elemento está presente => sucesso
 o elemento não está presente => insucesso
 Dois casos para análise de complexidade
 pesquisa com sucesso
 o item procurado está presente no vetor ou arquivo
 pesquisa sem sucesso
 o item procurado não está presente no arquivo
 A análise de complexidade é feita separadamente para cada um 
destes casos
Algoritmos para o problema da pesquisa
 Pesquisa sequencial em vetor não ordenado
 Pesquisa sequencial em vetor ordenado
 Pesquisa binária
Pesquisa sequencial em vetor
 Vetor não ordenado: caso mais simples de pesquisa
 Entrada
 o vetor preenchido com os elementos do conjunto (registros ou 
estruturas)
 o item procurado: chave de um registro (estrutura)
 Algoritmo
 comparar sequencialmente cada elemento do vetor com o item 
procurado até que
 o item é encontrado: retornar o registro, a posição, etc.
 o fim do vetor é encontrado: indica pesquisa sem sucesso
Exemplo: pesquisar o elemento 22 no vetor
Sucesso: o elemento está presente
Algoritmo: pesquisa sequencial em vetor NÃO ordenado
       32      13       25        19     14       15       52      33       64      49      
Vetor não ordenado
Análise do algoritmo de pesquisa sequencial
 Pesquisa em vetor não ordenado
 Definição da operação relevante
 comparação do item procurado com os elementos do conjunto
 Seja f(n) o número de comparações realizado pelo algoritmo de 
pesquisa sequencial
 Análise dos casos: Pesquisa sem sucesso
 f(n) = n => todos os elementos precisam ser comparados 
para mostrar que o elemento procurado não está presente
       32      13       25        19     14       15       52      33       64      49      
Análise do algoritmo de pesquisa sequencial
 Pesquisa em vetor não ordenado
 Definição da operação relevante
 comparação do item procurado com os elementos do conjunto
 Seja f(n) o número de comparações realizado pelo algoritmo de 
pesquisa sequencial
 Análise dos casos: Pesquisa com sucesso
 Melhor caso: f(n) = 1 => o elemento está na 1a. posição
 Pior caso: f(n) = n => o elemento está na última posição
 Caso médio: média de todos os casos - a seguir
Análise do caso médio – pesquisa sequencial
 caso médio: é necessário conhecer a probabilidade de cada elemento do 
conjunto ser procurado
 Neste caso, expressamos a função f(n) da seguinte forma:
 onde p
i
 é a probabilidade do i-ésimo registro (elemento) ser procurado
 Portanto: precisamos conhecer a distribuição de probabilidades do conjunto
 Se cada elemento do conjunto tiver a mesma probabilidade de ser 
procurado, então 
Uso das probabilidades para melhoria da pesquisa
 Como encontrar as probabilidades?
 em geral é difícil conhecer as probabilidades de se pesquisar um elemento
 além disso, as probabilidades podem alterar-se com o tempo ou outros 
aspectos
 em muitas situações, mesmo não conhecendo a distribuição exata de 
probabilidades, sabemos que a probabilidade de busca de elementos no 
conjunto não é igual
 alguns elementos são muito mais procurados do que outros
 exemplos:
 as palavras mais procuradas no Google BR em 2014
 BBB 14, ENEM, eleições, Eduardo Campos, Amor à Vida, iPhone 6, Copa do 
Mundo, SISU, PROUNI, Lepo Lepo 
 A mais buscada no mundo: Robin Williams
 serviços mais usados pela população
 a sua lista de amigos: alguns são mais próximos
 tabelas: ex: imposto de renda
Uso das probabilidades para melhoria da pesquisa
 Listas auto-ajustáveis
 podemos usar as pesquisas com sucesso para alterar a lista e tornar ao 
caso médio mais rápido
 como?
 mover cada elemento encontrado para posições anteriores na lista
 abordagem conservativa: move uma posição para frente a cada hit
 Exemplo: lista => 1,2,3,4,5,6 => 1,2,4,3,5,6 após buscar o 4
 abordagem agressiva: move o elemento encontrado para a primeira posição
 Exemplo: lista => 1,2,3,4,5,6 => 4,1,2,3,5,6 após buscar o 4
 os elementos mais procurados contribuirão com menor peso para o caso médio
 na busca sequencial, o melhor é ter os elementos ordenados pela frequência de 
busca
Algoritmos para o problema da pesquisa
✔ Pesquisa sequencial em vetor não ordenado
 Pesquisa sequencial em vetor ordenado
 Pesquisa binária
Pesquisa sequencial em VETOR ORDENADO
 a pesquisa sequencial pode ser feita em vetor ordenado
      2        3         5          9         14       15       21      33      45       49      
Exemplos de busca: 1, 2, 4, 9, 50
Análise do algoritmo de pesquisa sequencial
 Pesquisa em VETOR ORDENADO
 Definição da operação relevante
 comparação do item procurado com os elementos do conjunto
 Seja f(n) o número de comparações realizado pelo algoritmo de 
pesquisa sequencial
 Benefício da ordenação ocorre apenas no caso de pesquisa SEM 
sucesso
 No caso de pesquisa COM sucesso:os custos são iguais ao caso 
do vetor não ordenado
Análise do algoritmo de pesquisa sequencial
 Pesquisa em VETOR ORDENADO
 Análise dos casos: Pesquisa sem sucesso => custo para descobrir 
que o elemento procurado não está presente
 Melhor caso: f(n) = 1 
 Pior caso: f(n) = n 
 Caso médio: média de todos os casos - a seguir
      2        3         5          9         14       15       21      33      45       49      
Análise do caso médio – pesquisa sequencial
 caso médio para pesquisa sem sucesso: o elemento procurado é um valor 
que não está presente no vetor.
 Neste caso, expressamos a função f(n) da seguinte forma:
 onde p
i
 é a probabilidade do elemento procurado ser menor do que vetor[i]
 Portanto: precisamos conhecer a distribuição de probabilidades do conjunto
 Se cada elemento no intervalo tiver a mesma probabilidade de ser 
procurado, então 
Busca linear em vetor
 Vantagens 
 Algoritmo simples e fácil de entender
 Vetor pode estar ordenado ou não ordenado
 Desvantagem
 Ineficiência: algoritmo lento
 Custo linear no pior caso e no caso médio O(n)
 Caso médio: examina em média n/2 elementos
Algoritmos para o problema da pesquisa
✔ Pesquisa sequencial em vetor não ordenado
✔ Pesquisa sequencial em vetor ordenado
 Pesquisa binária
Pesquisa binária
 Requer conjuntos ordenados de elementos
 familiar a todos que consultam listas telefônicas e dicionários
 algoritmo básico
 compare a chave pesquisada com o elemento do meio do conjunto
 se a chave for igual: ok, pesquisa com sucesso!
 se a chave for menor, repita o procedimento para a primeira metade do conjunto
 se a chave for maior, repita o procedimento para a segunda metade do conjunto
 até encontrar o elemento ou a posição onde ele deveria estar
 Requisitos
 o conjunto deve estar ordenado pela chave de pesquisa
 o conjunto deve estar em vetor poiso acesso é aleatório
 Pesquisa binária
A cada passo metade dos dados é eliminada da pesquisa
Etapas da busca pelo número 22
Pesquisa binária: algoritmo
      2        3         5          9         14       15       21      33      45       49      
1        2        3         4          5        6        7         8        9         10
Exemplo de 
algoritmo elegante
Etapas da busca pelo número 33
Desenhando o vetor como uma árvore binária
altura da
árvore é o número
de comparações
necessário 
para a busca
Pesquisa binária: análise do pior caso
 A cada comparação, eliminamos metade do conjunto
N
N/2
N/4
N/8
1
………… 1 comparação
………… 1 comparação
………… 1 comparação
………… 1 comparação
………… 1 comparação
...
Número máximo de 
comparações é 
O(log2 n)
Pesquisa binária: análise de complexidade
 Inicialmente suponha que n é uma potência de 2 => n = 2k
 Cada iteração do laço elimina metade do conjunto 
 n = 2k-1 n = 2k-2 n = 2k-3 … n = 2k-k = 20 = 1
 Número máximo de iterações = k + 1
 Em cada iteração: número constante de operações c
 f(n) = c
1
 * log
2
(n) + c
2
 Se n não for potência de 2: arredonde n para a próxima 
potência de 2: 
 N = 1000 => 210 => 10 comparações para buscar em 1000
Pesquisa em vetor: síntese
 encontrar o maior elemento de um conjunto de n elementos 
 Custo mínimo: n-1 => O(n)
 encontrar o maior e o menor elementos
 Custo mínimo: (3n -2 ) / 2 => O (n)
 encontrar um dado elemento em um conjunto: pesquisa ou busca
 Pesquisa linear 
 Melhor caso O(1)
 Pior caso O(n)
 Pesquisa binária 
 Melhor caso O(1)
 Pior caso O(log n) 
Diferença 
muito significativa
Aulas anteriores
Exercício
Calcule o número de comparações para buscar um elemento no conjunto
 acima para: (a) o melhor caso; (b) o pior caso; (c) o caso médio. Considere 
que todas as buscas são igualmente prováveis.
	Computabilidade
	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
	Slide 24
	Slide 25
	Slide 26
	Slide 27
	Slide 28
	Slide 29
	Slide 30