"An algorithm is a set of rules for getting a specific output from a specific input. Each step must be so precisely defined that it can be translated into a computer language and executed by machine."
-- Donald Knuth
Esta é a melhor definição de algoritmo que conheço. Tipicamente, os algoritmos servem para resolver problemas. Na aula passada vimos um algoritmo de ordenação que consistia numa sequência de 5 passos. É importante salientar que o conceito de algoritmo é independente da linguagem de programação em que ele é programado e executado. Aliás, um algoritmo não tem que ser necessáriamente executado por um computador, pode ser executado "à mão" por uma pessoa.
Existe uma área da computação que se chama análise de algoritmos. No decorrer do vosso curso vão aprofundar esta matéria noutras disciplinas. Para já, apenas vos vou dar um "cheirinho" sobre o assunto.
O objectivo desta aula é convencer-vos de que este tópico é muito importante para as pessoas que escrevem programas de computador. Posto isto, chega de conversa e vamos ao que interessa.
Dada uma colecção de n elementos, pretende-se saber se um determinado elemento x existe nessa colecção. Para efeitos práticos, vamos supor que essa colecção é implementada como sendo um array a[0...n-1] de n elementos inteiros.
Solução 1
Uma solução possível é percorrer o array desde a primeira posição até à última. Para cada posição i, comparamos a[i] com x. Se forem iguais dizemos que x existe. Se chegarmos ao fim do array dizemos que x não existe. Vamos traduzir estas palavras para um algoritmo.
Algoritmo 1: pesquisa sequencial
(1) i <-- 0
(2) Se i = n, escreve "não existe" e termina.
(3) Se x = a[i], escreve "existe" e termina.
(4) i <-- i+1. Volta ao passo 2.
(nota: <-- significa o sinal de atribuição em ling. de programação.)
Este algoritmo chama-se algoritmo de pesquisa sequencial porque varre os elementos da nossa colecção sequencialmente um após outro. O algoritmo é independente da linguagem de programação em que possa vir a ser implementado. Se quisermos implementar este algoritmo em C teríamos de escrever qualquer coisa deste estilo:
i = 0;
do
{
if( i == n ) { printf("não existe"); break; }
if( x == a[i] ) { printf("existe"); break; }
i++;
}
while( 1 );
Pergunta
Resposta
Vamos supor agora que o array inicial estava ordenado por ordem crescente (se fosse por ordem decrescente o raciocínio era semelhante). Será que é possível resolver o problema de modo mais eficiente?
A resposta é positiva. O problema que estamos a ver é semelhante ao problema de encontrar o telefone de uma pessoa numa lista telefónica. Se a lista não estivesse ordenada, não teríamos outra hipótese senão percorrer a lista do principio até ao fim (uma tarefa em tudo semelhante a encontrar uma agulha num palheiro). Esse algoritmo seria o equivalente à pesquisa sequencial que vimos à pouco.
Conhecem alguém que procura a lista telefónica do principio até ao fim? Claro que não. Como a lista está ordenada alfabéticamente, conseguimos descobrir rapidamente o telefone de uma pessoa. Abrimos a lista no meio e depois decidimos pelo lado esquerdo ou pelo lado direito. E assim sucessivamente até encontrarmos o nome da pessoa. A cada passo vamos eliminando grande parte das páginas da lista.
Se o array estiver ordenado podemos implementar um algoritmo semelhante ao da lista telefónica. A ideia é manter duas variáveis, esq e dta, que significam os limites esquerdo e direito do array. A ideia é que se o elemento x existe numa posição a[i] do array, então i tem de estar compreendido entre esq e dta (esq <= i <= dta).
Algoritmo 2: pesquisa binária
(1) esq <-- 0 , dta <-- n-1
(2) Se esq > dta, escreve "não existe" e termina.
(3) i <-- parte inteira de (esq+dta)/2
(4) Se x = a[i], escreve "existe" e termina.
Se x < a[i], dta <-- i-1. Volta ao passo 2.
Se x > a[i], esq <-- i+1. Volta ao passo 2.
Vamos programar o algoritmo de pesquisa binária em C.
esq = 0;
dta = n-1;
do
{
if( esq > dta )
{
printf("nao existe");
break;
}
i = (esq+dta)/2;
if( x == a[i] )
{
printf("existe");
break;
}
else if( x < a[i] )
dta = i-1;
else
esq = i+1;
}
while( 1 );
Pergunta
Resposta
Vejamos um exemplo. Se n=1000, o algoritmo de pesquisa sequencial irá executar 1000 comparações no pior caso. Por sua vez, o algoritmo de pesquisa binária irá executar 10 comparações no pior caso. O logaritmo de base 2 aparece porque estamos sempre a dividir o intervalo ao meio: 1000, 500, 250, 125, 63, 32, 16, 8, 4, 2, 1. E se n=1000000000 (1 bilião) ? Aqui vai a resposta:
Nas disciplinas de Programação II, PED e Algoritmos vão aprofundar estas matérias. Já agora, acham que é possível resolver o problema que vimos nesta aula mais rapidamente do que com a pesquisa binária? A resposta é positiva e para tal é necessário utilizar uma técnica chamada hashing, mas isso fica para outras núpcias.
O estudo de algoritmos e de estrutura de dados é fundamental para se fazer programas eficientes. Por exemplo, os motores de pesquisa da Web (ex: google) utilizam algoritmos semelhantes aos da pesquisa binária de modo a descobrir rapidamente quais são as webpages que contêm uma determinada palavra. A pesquisa binária é efectuada numa espécie de array gigantesco contendo todas as palavras que existem na Web. Obviamente que eles não fazem uma pesquisa sequencial. Se assim fosse, as respostas às vossas pesquisas demorariam 1 mês em vez de 0.2 segundos!
Acabei de vos dizer uma mentira! Os motores de pesquisa não utilizam a pesquisa binária, utilizam a tal técnica de hashing que vocês vão aprender na disciplina de PED.
Dei-vos um artigo do prof. Donald Knuth que foi publicado originalmente na revista Scientific American em Abril de 1977. Leiam esse artigo e fixem o nome deste senhor. Donald Knuth é um dos grandes pioneiros da informática. Inventou diversos algoritmos e foi a pessoa que sistematizou o estudo e a análise de algoritmos.