2.10 um Algoritmo Computacional Melhorado

EXERCÍCIO 2.16

Procure valores mais precisos para π e e. Substitua no Programa 2.12 e execute, anotando o resultado. Você consegue colocar

dígitos su cientes para que o erro desapareça e Python dê como resultado zero?

EXERCÍCIO 2.17

Escreva um programa que calcule o quadrado da hipotenusa de um triângulo de lados 3 e 4, usando o teorema de Pitágoras.

EXERCÍCIO 2.18

Escreva um programa que calcule a área de uma esfera de raio 5.

2.10 UM ALGORITMO COMPUTACIONAL MELHORADO

No início do capítulo apresentei um algoritmo de busca de palavras em um dicionário. Ainda era um algoritmo ruim. Apesar dos computadores serem rápidos, isso não justifica usarmos a primeira solução que achamos, contando com a velocidade de processamento para esconder a deficiência do nosso código.

Vamos tentar melhorar. Primeiro, apresento uma rápida análise do desempenho do algoritmo.

A língua portuguesa tem cerca de 400 mil vocábulos. Este não é um número exato, mas vamos

usá-lo como base de nosso exemplo. Diremos que as 400 mil palavras são o nosso “universo de busca”. Assim, em um dicionário completo, no pior caso, ou seja, da palavra não existir no dicionário e caso não soubéssemos nada sobre a organização do dicionário, em ordem crescente de palavras, teríamos de ler 400 mil vocábulos. Se estivéssemos procurando uma palavra em uma língua com 800 mil vocábulos, dobraríamos o tempo de busca no pior dos casos.

Sempre é bom pensar no pior caso quando testamos a eficiência de um algoritmo. Qual é o “pior

caso” para uma busca de palavras? É a palavra não existir!

Mas, como você já deve ter percebido, este método de busca não é o mais inteligente. Podemos

fazer melhor e você o faria de maneira bem mais inteligente se tivesse um dicionário à mão. Mas como poderíamos ensinar um método sistemático a uma máquina para que fizesse a busca por nós?

Vamos pensar “algoritmicamente”.

Uma maneira seria começar abrindo o dicionário ao meio, na sua parte central. Olhamos a palavra

que se encontra no topo dessa página. Se for alfabeticamente “menor” que a palavra procurada, o que fazemos? Sabemos que, por conta da organização do dicionário, a palavra que buscamos não pode estar antes desta página, e que só pode estar depois. Deste modo, podemos ignorar todas as palavras da parte do dicionário que estão antes desta página. Observe que se tínhamos um universo de busca de 400 mil palavras, agora nosso universo de busca se reduziu a 200 mil palavras, a metade do universo original. Um ganho considerável!

Após esse primeiro passo, repetimos o processo de abrir o dicionário na página central. Novamente

fazemos a escolha. Se a palavra da página for menor alfabeticamente, descartamos a metade anterior. Se for maior, devemos descartar a metade posterior. Vamos repetindo este processo até encontrar a palavra ou reduzirmos nosso universo de busca a apenas uma página e não a encontrarmos.

Note que, segundo este algoritmo, cada vez que olhamos uma palavra, nosso universo de busca se

reduz à metade do universo de busca anterior. Esse algoritmo é tão bom que tem até um nome: busca binária! Seu nome vem do fato de que a cada passo o universo de busca é dividido por 2.

Quão melhor é esse algoritmo em relação ao algoritmo anterior que lia cada nome em sequência?

Vamos fazer um cálculo simples. Se meu computador lesse cada nome em sequência, teria de ler 400 mil nomes, no pior caso, para decidir se a palavra existe ou não. E em nosso algoritmo de busca binária? A tabela a seguir mostra quantas comparações são necessárias para atingir o objetivo, arredondando sempre para o inteiro imediatamente superior.

Tabela 2.6 Número de passos de uma busca binária

Passo Universo Passo Universo

0 400.000 10 391

1 200.000 11 196

2 100.000 12 98

3 50.000 13 49

4 25.000 14 25

5 12.500 15 13

6 6250 16 7

7 3125 17 4

8 1563 18 2

9 782 19 1

Desse modo, com 19 passos podemos ter certeza se a palavra existe ou não. Certamente um

grande progresso em relação aos 400 mil passos anteriores!

Um pouco de Matemática para entendermos como podemos chegar a este número, sem termos de

fazer a tabela anterior: a relação entre o número de passos e o universo de busca para a busca binária é uma relação logarítmica. Mas, como dividimos por 2, a base do nosso logaritmo é a base 2, ou seja, procuramos o logaritmo de 400 mil na base 2. Os passos são inteiros, quer dizer, não existe fração de passo. Cada passo implica uma divisão do nosso universo de busca pela metade. Como 19 2 = 524288 ou seja, pegando o número inteiro superior mais próximo log2 400000 = 19

A descrição do algoritmo foi feita com uma prosa, como em uma conversa normal. Temos uma ideia

de solução, agora devemos pensar em como podemos escrever essa solução de maneira mais formal, mais algorítmica.

Vamos tentar reescrever nosso algoritmo de uma maneira mais formal.