É comum medir a eficiência de um algoritmo, através do número de passos que uma máquina precisa dar para executá-lo. Dois algoritmos construídos para executar uma mesma tarefa, podem apresentar diferenças significativas, como exemplificaremos a seguir.
O Minidicionário Aurélio da Lingua Portuguesa, editado em fevereiro de 1985, tem aproximadamente 25.000 palavras. Uma maneira de procurar uma palavra neste dicionário, ou concluir que ela não se faz presente, é ler o dicionário palavra por palavra da página inicial em direção à final, até encontrá-la, ou notar que ela não se faz presente. Este método não usa a ordem alfabética em que as palavras são colocadas, e é conhecido como busca sequencial. Você sempre terá resposta à sua pergunta, mas isso pode exigir do algoritmo 25.000 passos.
Uma outra maneira de executar a mesma tarefa é ir direto ao meio da lista de palavras, se necessário subtraia algumas. Se não achar a palavra, vá para o meio da metade que a contém e elimine a outra metade (lembre que o dicionário é ordenado alfabeticamente). Este algoritmo já no passo inicial, elimina aproximadamente 12.500 palavras. A partir daí, prossiga com esta lógica, isto é, vá na metade que contém a palavra, e divida novamente ao meio, e se não encontrar continue com este procedimento tantas vezes, até que nenhuma palavra tenha sobrado. Para o caso, com no máximo 15 divisões, temos a resposta, pois
o que ganha das 26 mil tentativas. Este método que acabamos de descrever é conhecido como busca binária.
Generalizando, suponhamos uma lista de tamanho n e k o número de divisões necessárias para convergir a lista para uma única palavra. Temos,
portanto 
Assim,
, isto é, o menor inteiro maior que 
. Logo uma busca sequencial é de ordem n , e a binária de ordem , e n cresce mais rapidamente que 
; como já indicava o exemplo.
Nenhum comentário:
Postar um comentário