Aula 07 Caso M dio da Busca Linear

7.1

Aula 7: Caso Médio da Busca Linear

Distribuição das entradas
Caso médio da busca linear não ordenada
Caso médio da busca linear ordenada

7.2

Definição de Complexidade do Caso Médio
(recordação)

A: algoritmo
E = { E1, ..., Em } : conjunto de todas as entradas de A t(Ei) : número de passos efetuados por A quando a entrada é Ei p(Ei) : probabilidade de ocorrência da entrada Ei
Å

ÓÑÔÐ Ü

Ó ×Ó Ñ

Ó

Ñ

½

Ô´

µØ´

µ

7.3

Caso Médio da Busca Linear Não Ordenada
(pelo Método 1)
Observação Fundamental: entradas distintas que tenham a chave procurada na mesma posição podem ser consideradas como idênticas.
Exemplo: Sejam E e E’ as seguintes entradas:
E
6

-1

4

7

3

9

3

-2

8

7

1

10

E’
Observe que para a Busca Linear, E e E’ são entradas idênticas (indistingüíveis) quando a chave procurada é x = 7.

7.4

Caso Médio da Busca Linear Não Ordenada
(pelo Método 1)
Conclusão: A Busca Linear não ordenada numa lista com n elementos só reconhece n+1 entradas distintas, a saber:
- entradas em que a chave procurada está na posição 1
- entradas em que a chave procurada está na posição 2
.
.
.

- entradas em que a chave procurada está na posição n
- entradas em que a chave não se encontra na lista

Sejam: - Ei, 1 ≤ i ≤ n, uma entrada em que a chave procurada ocupa a i-ésima posição da lista
- E0 entrada que corresponde à busca sem sucesso

O conjunto de entradas é, portanto:
E = { E0, E 1, ... , En }

7.5

Busca Linear Não Ordenada:
Número de Passos de Cada Entrada
Observe que

t(Ek ) = k ,1≤ k ≤ n t(E0) = n

Probabilidades das Entradas:
Seja q (0 ≤ q ≤ 1) a probabilidade de sucesso da busca.
Supondo que as entradas E1, ... , En tenham a mesma probabilidade, temos: q p(Ek ) = , 1 ≤ k ≤ n n p(E0) = 1 − q

7.6

Cálculo Final da Complexidade Média da
Busca Linear Não Ordenada
C.M. =

n k=0 p(Ek )t(Ek ) = p(E0)t(E0) + p(E1)t(E1) + . . . + p(En)t(En) =

q q q
· 1 + · 2 + ... + · n = n n n q
= (1 − q) · n + (1 + 2 + . . . + n) = n = (1 − q) · n +

q n(n + 1) 2n −