Mathematics">
Algoritmos de Busca
Algoritmos de Busca
Algoritmos de Busca
Algoritmos de Busca
T1530A, T7043A
Sumário
IV.1. Introdução ......................................................................................... 3
IV.2. Busca Seqüencial ............................................................................. 4
IV.3. Busca Binária.................................................................................... 6
IV.4. Árvore de Busca Binária ................................................................. 10
Projeto e Análise de Algoritmos
Algoritmos de Busca
IV.1. INTRODUÇÃO
Conceitos básicos:
Exemplos:
Banco
chave: número da conta
registro de interesse: informação sobre o cliente
responsável pela conta (incluindo dados pessoais e
transações).
Métodos de busca:
• busca seqüencial
• busca binária
• busca em árvore binária
• busca em árvore balanceada
• hashing
página 3
Projeto e Análise de Algoritmos
Algoritmos de Busca
página 4
Projeto e Análise de Algoritmos
Algoritmos de Busca
Observação:
1 + 2 + 3 + ... + ( N − 1) + N ( N + 1)
=
N 2
página 5
Projeto e Análise de Algoritmos
Algoritmos de Busca
Tudo o que foi discutido até o momento diz respeito a uma busca (ou
seja, a busca de um cartão correspondende a uma transação). Se
tivermos M transações, o tempo total, utilizando a busca seqüencial é
proporcional a MN (média e pior caso).
Avaliação:
Hipótese: comparação é executada em c microsegundos.
Tem-se N = 106 e M = 109.
N
tempo médio é = M c (µs)
2
M
= c segundos
2
10 9
= c segundos
2
109 segundos ≅ 3 décadas
log 2 N
6 78
Propriedade: Busca binária nunca examina mais do que [ ln N ] + 1
números.
página 6
Projeto e Análise de Algoritmos
Algoritmos de Busca
N = 2n ⇒ n = log2N
TN ≡ T2 n = T2n + 1 = T2 n − 1 + 1
2
= T2 n − 2 + 1 + 1 = T2 n − 2 + 2
= T2 n − 3 + 3
M
= T20 + n = T1 + log 2 N
∴ O ( ln N )
Algoritmo (pseudocódigo)
fim
página 7
Projeto e Análise de Algoritmos
Algoritmos de Busca
Avaliação
M transações (109)
N = 106 elementos na lista
cada verificação: c µs
ordem da busca: O ( ln N )
log10 10 1
log 2 10 6 = 6 log 2 10 = 6 ≅6 ≅ 6 ∗ 3,3
log10 2 0,3
página 8
Projeto e Análise de Algoritmos
Algoritmos de Busca
1) CN = CN-1 + N , N ≥ 2 e C1 = 1
CN = CN-1 + N
= CN-2 + N + (N-1) = CN-2 + 2N-1
= CN-3 + N + (N-1) + (N-2) = CN-3 + 3N-3
M
= C1 + N + (N-1) + (N-2) + ... + 2
= 1 + 2+ 3 + ...+ (N-2) + (N-1) + N
= (1+N) + (2+ (N-1)) + (3+ (N-2)) + ... } N/2 vezes
N ( N + 1)
=
2
N
CN = ( N + 1) ⇒ CN é O (N2)
2
página 9
Projeto e Análise de Algoritmos
Algoritmos de Busca
Exemplo
valor 12 25 33 37 48 57 86 92
48
33 86
25 37 57 92
12
Algoritmos e Desempenho
Ver exercícios.
IV.5. BIBLIOGRAFIA
página 10
Projeto e Análise de Algoritmos
Algoritmos de Busca
página 11