Aula 07 - Caso Médio da Busca Linear

SAVE OFFLINE

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 C:M: = Complexidade do aso medio =

X m

i=1

p(Ei )t(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 X 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 − 2qn + qn + q =n−q·n+ · = = n 2 2

2n qn + q 2

Casos Particulares q = 1 ( a chave sempre se encontra na lista) C.M. =

n+1 n ≈ 2 2

q = 0 ( a chave nunca se encontra na lista) C.M. = n

7.7

Caso Médio da Busca Linear Ordenada Representemos uma entrada genérica E com n elementos da seguinte forma: E y1

y2

y3

...

yn-1

yn

Observe que a chave procurada x pode satisfazer 2n + 1 casos possíveis, a saber : x < y1 x = y1 y1 < x < y2 x = y2 y2 < x < y3 x = y3 .. . x = yn-1 yn-1 < x < yn x = yn x > yn

7.8

Busca Linear Ordenada: Descrição do Conjunto de Entradas As 2n + 1 entradas distintas podem ser descritas como: Ek = entrada em que x = yk , 1 ≤ k ≤ n E’0 = entrada em que x < y1 E’k = entrada em que yk < x < yk+1 , 1 ≤ k ≤ n-1 E’n = entrada em que x > yn

Observe o Diagrama: E3

E’0

y1

E’1

y2

E’2

y3

En-1

...

En

{

E2

{ {

E1

yn-1

E’n-1

yn

O conjunto de entradas é, portanto: E = { E’0, E1, E’1, E2, E’2, E3, E’3, ... , En-1, E’n-1, En, E’n }

E’n

7.9

Busca Linear Ordenada: Número de Passos de Cada Entrada t(Ek) = k, 1 ≤ k ≤ n

Observe que

t(E’k) = k + 1, 0 ≤ k ≤ n Exemplo: Suponha que deseja-se procurar a chave x = 7 numa lista com n = 6 elementos. Então: Uma entrada que representa E3 é -1

6

7

9

11

12

t(E3) = 3 (A busca faz 3 comparações neste caso)

Uma entrada que representa E’3 é 0

4

6

8

11

15

t(E’3) = 4 (A busca faz 4 comparações neste caso)

7.10

Busca Linear Ordenada: Probabilidades das Entradas Seja q (0 ≤ q ≤ 1) a probabilidade de sucesso da busca. Supondo que as entradas E1, ... , En sejam equiprováveis, temos: p(Ek )

=

q n

;

(1

  k

n)

Além disso, supondo que as entradas E’0, ... , E’n sejam equiprováveis, temos: 0

p(Ek )

=

1

q

n

+1

;

(0

  k

n)

7.11

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

n X k=1

p(Ek )t(Ek ) +

n X k=0

p(Ek′ )t(Ek′ )

n 1−q q X ·k+ · (k + 1) = k=1 n k=0 n + 1

Efetuando os cálculos, vem:

n X

CM = :

:

n

q

2

+2

Observação: O valor da C.M. para a Busca Linear Ordenada é tal que n

ou seja,

2

C:M:

n

+1  2

C:M:

 +2 2 n

para qualquer valor de q

Verifique a validade dos cálculos acima para a C.M. Tempo: 5 minutos

7.12

Solução n 1−q q X C.M. = ·k+ · (k + 1) = k=1 n k=0 n + 1 n X

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

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

=

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

=

qn + q + n + 2 − qn − 2q = 2

=

n−q+2 2

7.13

Exercício

Determinar a expressão da complexidade média de uma busca não ordenada de n chaves (n par), em que as probabilidades de busca das chaves de ordem ímpar são iguais entre si, sendo esse valor igual ao dobro da probabilidade de qualquer chave par. Supor, ainda, que a probabilidade de a chave se encontrar na lista é igual a q . Tempo: 20 minutos

7.14

Solução De acordo com o enunciado do problema, temos: p(E1 )

p

=2

=

p(E3 )


p(E2 )

Logo,

=

=2

p(E2 )

=

:::

=

p(En


p(E4 )

p(E4 )

=

=

1) =

=2

:::

:::

=

(pois n é par)

p


p(En )

p(En )

=

p

2

Calculando o valor de p :

X n

i=1

)

p(Ei )

n

=

q

)

n p

p(E1 )

2 p+ 2 2 =q





+

)

p(E2 )

4 q p= 3n

+

:::

+

p(En

1) +

p(En )

=

q

7.15

Solução

Calculando o valor de C.M. : C:M: =

p(E0 )t(E0 )

C:M: = (1

q )n

pE

tE

pE tE

+ p(E1)t(E1) + p(E2 )t(E2) + : : : + ( n 1) ( n 1) + ( n) ( n )

+

4q 3n


1+3
2+ 2q

n

:::

+

4q 3n


(

n

1) +

Complete os cálculos finais e encontre:

CM = +3 :

:

n

q

qn

2

2q 3n




n

7.16

Exercício Final

Determinar a expressão da complexidade média de uma busca não ordenada, supondo que a probabilidade da busca de qualquer chave, exceto a última, é igual a metade da probabilidade da chave seguinte na lista. Supor também que a probabilidade de a chave se encontrar na lista é igual a q .