A maior rede de estudos do Brasil

Grátis
259 pág.
apostila

Pré-visualização | Página 31 de 50

foi exigido no enunciado que fossem localizadas
todas as ocorreˆncias (este e´ outro problema). Enta˜o podemos modificar o co´digo para
a versa˜o apresentada na figura 10.16, simplesmente trocando-se o for por um while
que termina a execuc¸a˜o ta˜o logo o elemento seja encontrado (se for encontrado).
Este algoritmo e´ mais ra´pido, na me´dia, do que o anterior, embora o nu´mero de
comparac¸o˜es feitas possa ser a mesma no caso do elemento na˜o estar presente no
vetor. Mas, se dermos sorte, o elemento pode estar no in´ıcio do vetor e terminar bem
ra´pido. Na me´dia, espera-se que ele pare mais ou menos na metade do vetor, isto e´,
considerando-se uma distribuic¸a˜o uniforme dos elementos.
Mas como o lac¸o faz dois testes, no caso do elemento na˜o ser encontrado ele sera´
um pouco mais lento. Notem que o duplo teste no lac¸o e´ necessa´rio pois deve parar
ou porque achou o elemento ou porque o vetor terminou. Este segundo teste so´ vai
dar true uma u´nica vez, o que e´ um desped´ıcio.
Se pudesse haver garantia de que sempre o elemento procurado estivesse presente,
enta˜o poder´ıamos construir um teste simples, o que pode nos economizar alguma
computac¸a˜o. Esta garantia na˜o pode existir, certo? Mais ou menos. Digamos que o
programador deliberadamente coloque o elemento no vetor. Neste caso, ha´ a garantia
140 CAPI´TULO 10. ESTRUTURAS DE DADOS
function busca (x: real ; var v: vetor r ; n: integer) : integer ;
var i : integer ;
achou: boolean;
begin
achou:= false ;
i := 1;
while ( i <= n) and not achou do
begin
if v[ i ] = x then
achou:= true ;
i := i + 1;
end;
i f achou then
busca:= i − 1;
end;
Figura 10.16: Busca em vetores, segunda versa˜o.
de que ele esta´ presente. Mas algue´m pode perguntar: assim na˜o vale, se eu coloco
na˜o significa que ele ja´ estava presente, eu vou sempre encontrar o elemento “falso”.
Novamente, depende de onde o programador coloque o elemento. Digamos que ele
o coloque logo apo´s a u´ltima posic¸a˜o. Enta˜o, das duas uma: ou o elemento na˜o estava
no vetor original, e neste caso a busca pode terminar pois o elemento sera´ encontrado
apo´s a u´ltima posic¸a˜o; ou o elemento estava presente e sera´ encontrado antes daquele
que foi adicionado. Um teste final resolve a du´vida. Se for encontrado em posic¸a˜o
va´lida, e´ porque estava presente, sena˜o, na˜o estava.
Este elemento adicionado logo apo´s o final do vetor e´ denominado sentinela e seu
uso e´ ilustrado na versa˜o apresentada na figura 10.17.
function busca (x: real ; var v: vetor r ; n: integer) : integer ;
var i : integer ;
begin
v[n+1]:= x;
i:= 1;
while v[ i ] <> x do
i := i + 1;
i f i <= n then
busca:= i
else
busca:= 0;
end;
Figura 10.17: Busca em vetores com sentinela.
Apesar da melhoria, este algoritmo sempre faz um nu´mero de comparac¸o˜es que
pode atingir n no pior caso, isto e´, quando o elemento na˜o esta´ presente no vetor.
O caso o´timo e o caso me´dio na˜o mudam, embora o algoritmo, conforme explicado,
10.1. VETORES 141
fac¸a metade das comparac¸o˜es quando comparado com a versa˜o anterior. Desta forma
ele e´ apenas ligeiramente melhor do que o anterior.
Ainda, o programador deve garantir que a posic¸a˜o usada pelo sentinela nunca seja
usada como sendo um elemento va´lido, pois na˜o e´. O programador colocou o elemento
ali de maneira controlada, mas na˜o se trata de um elemento va´lido. Isto significa que
o nu´mero de elementos u´teis do vetor agora na˜o e´ mais max r (ou max i), mas sempre
um a menos. Normalmente se modifica a definic¸a˜o do tipo para prever este espac¸o
adicional para o programador.
const min r=0; max r=50;
min i=1; max i=10;
type vetor r= array [min r . .max r+1] of real ;
vetor i= array [ min i . . max i+1] of integer ;
E´ poss´ıvel tornar o algoritmo mais eficiente?
A resposta e´ sim2. Mas, para tornar a busca mais eficiente e´ preciso impor algumas
restric¸o˜es extra na forma como os dados sa˜o organizados em memo´ria..
Esta maneira consiste em considerar que os dados esta˜o de alguma forma respei-
tando uma ordem lexicogra´fica em memo´ria. Por exemplo, se forem nomes, esta˜o
em ordem alfabe´tica. Se forem nu´meros, esta˜o em ordem crescente (ou descrescente).
Porque isto e´ necessa´rio? Pois pode-se explorar a informac¸a˜o de ordenac¸a˜o para tornar
o me´todo mais eficiente.
No caso, podemos modificar a soluc¸a˜o anterior para que o algoritmo termine a
busca sempre que encontrar um elemento que ja´ e´ maior do que aquele que se esta´
procurando, pois o vetor esta´ ordenado. O programa da figura 10.18 foi implementado
com esta ideia.
function busca (x: real ; var v: vetor r ; n: integer) : integer ;
var i : integer ;
begin
v[n+1]:= x;
i:= 1;
while v[ i ] < x do
i := i + 1;
i f (v[ i ] = x) and ( i <= n) then
busca:= i
else
busca:= 0;
end;
Figura 10.18: Busca em vetores ordenados.
Apesar de termos explorado uma propriedade adicional que faz com que no caso
2Em disciplinas avanc¸adas de algoritmos se estudam me´todos bastante eficientes para este pro-
blema. No nosso caso veremos apenas um deles.
142 CAPI´TULO 10. ESTRUTURAS DE DADOS
me´dio a busca seja mais eficiente, no pior caso, aquele em que o elemento procurado
na˜o pertence ao vetor, ainda temos um algoritmo que faz tantas comparac¸o˜es quanto
o tamanho do vetor. E´ poss´ıvel fazer melhor? A resposta novamente e´ sim.
Como exemplo, considere o problema de se encontrar um verbete no diciona´rio.
Sabemos que estes verbetes se encontram em ordem alfabe´tica. Por este motivo,
ningue´m em sa˜ conscieˆncia procura um nome em ordem sequencial desde o in´ıcio, a
menos que esteja procurando algo que comec¸a com a letra “A”.
Suponha que o verbete inicia com a letra “J”. Normalmente se abre o diciona´rio
mais ou menos no meio. Se o nome presente no in´ıco da pa´gina for “menor” lexico-
graficamente falando do que aquele que se busca, por exemplo, algo comec¸ando com
a letra “D”, enta˜o, pode-se tranquilamente rasgar o diciona´rio, eliminando-se tudo o
que esta´ antes do “D” e continuar o processo com o que restou.
Na segunda tentativa abre-se novamente mais ou menos na metade do que sobrou.
Suponha que ca´ımos na letra “M”. Como estamos procurando o “J”, pode-se sem
problemas rasgar novamente o diciona´rio eliminando-se tudo o que segue o “M”, ate´
o fim. Resta procurar “apenas” entre o “D” e o “M”.
Aplicando-se consistentemente este processo repetidas vezes, sempre teremos um
diciona´rio dividido mais ou menos por 2. Se ele tinha 500 pa´ginas no in´ıcio, na segunda
vez tera´ 250 e na terceira 125, na quarta algo pro´ximo de 70 pa´ginas. E assim por
diante. Por isto que costumamos localizar rapidamente verbetes em um diciona´rio.
O algoritmo mostrado na figura 10.20, denominado de busca bina´ria, implementa
esta ideia. Procura-se o elemento no meio do vetor. Se encontrou, enta˜o pode parar.
Se na˜o encontrou, basta verificar se o valor encontrado e´ maior ou menor do que o
procurado. Se for maior, joga-se a metade superior fora e trabalha-se apenas com
a metade inferior. Se for menor, joga-se fora a metade inferior e trabalha-se apenas
com a metade superior. Novamente procura-se na metade do que sobrou e assim por
diante, ate´ que se encontre o elemento ou ate´ que se determine que na˜o e´ mais poss´ıvel
encontra´-lo.
Vamos agora comparar estas u´ltimas quatro verso˜es para o algoritmo de busca.
A tabela 10.19 resume o nu´mero de comparac¸o˜es feitas para diversos tamanhos de
entrada, sempre analisando o pior caso. O caso me´dio exige um pouco mais de cui-
dado para se calcular e na˜o sera´ estudado aqui. O caso o´timo e´ sempre uma u´nica
comparac¸a˜o para os casos: o algoritmo acha o elemento na primeira tentativa.
Versa˜o n = 10 n = 102 n = 104 n = 108
Busca simples (fig. 10.16) 20 200 20000 200000000
Busca com sentinela (fig. 10.17) 10 100 10000 100000000
Busca em vetor ordenado (fig.

Crie agora seu perfil grátis para visualizar sem restrições.