apostila
259 pág.

apostila


DisciplinaAlgoritmos e Estrutura de Dados I702 materiais7.921 seguidores
Pré-visualização50 páginas
foi exigido no enunciado que fossem localizadas
todas as ocorre\u2c6ncias (este e´ outro problema). Enta\u2dco podemos modificar o co´digo para
a versa\u2dco apresentada na figura 10.16, simplesmente trocando-se o for por um while
que termina a execuc¸a\u2dco ta\u2dco 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\u2dces feitas possa ser a mesma no caso do elemento na\u2dco estar presente no
vetor. Mas, se dermos sorte, o elemento pode estar no in´\u131cio 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\u2dco uniforme dos elementos.
Mas como o lac¸o faz dois testes, no caso do elemento na\u2dco 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´\u131cio.
Se pudesse haver garantia de que sempre o elemento procurado estivesse presente,
enta\u2dco poder´\u131amos construir um teste simples, o que pode nos economizar alguma
computac¸a\u2dco. Esta garantia na\u2dco 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 \u2212 1;
end;
Figura 10.16: Busca em vetores, segunda versa\u2dco.
de que ele esta´ presente. Mas algue´m pode perguntar: assim na\u2dco vale, se eu coloco
na\u2dco significa que ele ja´ estava presente, eu vou sempre encontrar o elemento \u201cfalso\u201d.
Novamente, depende de onde o programador coloque o elemento. Digamos que ele
o coloque logo apo´s a u´ltima posic¸a\u2dco. Enta\u2dco, das duas uma: ou o elemento na\u2dco estava
no vetor original, e neste caso a busca pode terminar pois o elemento sera´ encontrado
apo´s a u´ltima posic¸a\u2dco; 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\u2dco
va´lida, e´ porque estava presente, sena\u2dco, na\u2dco estava.
Este elemento adicionado logo apo´s o final do vetor e´ denominado sentinela e seu
uso e´ ilustrado na versa\u2dco 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\u2dces que
pode atingir n no pior caso, isto e´, quando o elemento na\u2dco esta´ presente no vetor.
O caso o´timo e o caso me´dio na\u2dco mudam, embora o algoritmo, conforme explicado,
10.1. VETORES 141
fac¸a metade das comparac¸o\u2dces quando comparado com a versa\u2dco anterior. Desta forma
ele e´ apenas ligeiramente melhor do que o anterior.
Ainda, o programador deve garantir que a posic¸a\u2dco usada pelo sentinela nunca seja
usada como sendo um elemento va´lido, pois na\u2dco e´. O programador colocou o elemento
ali de maneira controlada, mas na\u2dco se trata de um elemento va´lido. Isto significa que
o nu´mero de elementos u´teis do vetor agora na\u2dco e´ mais max r (ou max i), mas sempre
um a menos. Normalmente se modifica a definic¸a\u2dco 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´\u131vel tornar o algoritmo mais eficiente?
A resposta e´ sim2. Mas, para tornar a busca mais eficiente e´ preciso impor algumas
restric¸o\u2dces extra na forma como os dados sa\u2dco organizados em memo´ria..
Esta maneira consiste em considerar que os dados esta\u2dco de alguma forma respei-
tando uma ordem lexicogra´fica em memo´ria. Por exemplo, se forem nomes, esta\u2dco
em ordem alfabe´tica. Se forem nu´meros, esta\u2dco em ordem crescente (ou descrescente).
Porque isto e´ necessa´rio? Pois pode-se explorar a informac¸a\u2dco de ordenac¸a\u2dco para tornar
o me´todo mais eficiente.
No caso, podemos modificar a soluc¸a\u2dco 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\u2dco pertence ao vetor, ainda temos um algoritmo que faz tantas comparac¸o\u2dces quanto
o tamanho do vetor. E´ poss´\u131vel 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\u2dc conscie\u2c6ncia procura um nome em ordem sequencial desde o in´\u131cio, a
menos que esteja procurando algo que comec¸a com a letra \u201cA\u201d.
Suponha que o verbete inicia com a letra \u201cJ\u201d. Normalmente se abre o diciona´rio
mais ou menos no meio. Se o nome presente no in´\u131co da pa´gina for \u201cmenor\u201d lexico-
graficamente falando do que aquele que se busca, por exemplo, algo comec¸ando com
a letra \u201cD\u201d, enta\u2dco, pode-se tranquilamente rasgar o diciona´rio, eliminando-se tudo o
que esta´ antes do \u201cD\u201d 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´\u131mos na letra \u201cM\u201d. Como estamos procurando o \u201cJ\u201d, pode-se sem
problemas rasgar novamente o diciona´rio eliminando-se tudo o que segue o \u201cM\u201d, ate´
o fim. Resta procurar \u201capenas\u201d entre o \u201cD\u201d e o \u201cM\u201d.
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´\u131cio, 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\u2dco pode parar.
Se na\u2dco 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\u2dco e´ mais poss´\u131vel
encontra´-lo.
Vamos agora comparar estas u´ltimas quatro verso\u2dces para o algoritmo de busca.
A tabela 10.19 resume o nu´mero de comparac¸o\u2dces 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\u2dco sera´ estudado aqui. O caso o´timo e´ sempre uma u´nica
comparac¸a\u2dco para os casos: o algoritmo acha o elemento na primeira tentativa.
Versa\u2dco 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.