O que é um algoritmo

O método para achar o máximo divisor comum do Livro VII dos Elementos de Euclides, escrito há cerca de 2300 anos, ainda roda nos computadores hoje.

Um método que sempre funciona

Imagine que você precisa do maior número que divide tanto 1071 quanto 462. Você poderia testar todos os números de 462 até 1 e parar no primeiro que dividisse os dois. Funciona, mas pode levar centenas de tentativas. Há um jeito mais curto. Divida 1071 por 462 e guarde o resto, 147. Agora divida 462 por 147 e guarde o resto, 21. Divida 147 por 21: o resto é 0, então a resposta é 21. Três divisões em vez de várias centenas.

Esse jeito mais curto é um algoritmo: uma lista finita de passos precisos que recebe uma entrada e produz a saída certa. Este é o algoritmo de Euclides para o máximo divisor comum, e ele aparece no Livro VII dos Elementos, escrito por volta de 300 a.C. Euclides o descreveu com subtrações repetidas de comprimentos em vez de divisões, mas a ideia é a mesma, e a versão com restos é a que os programas usam hoje.

function gcd(a, b) {
  while (b !== 0) {
    const r = a % b;   // resto
    a = b;
    b = r;
  }
  return a;
}
console.log(gcd(1071, 462)); // mostra 21

O que faz de uma lista de passos um algoritmo

Livros didáticos como o de Cormen, Leiserson, Rivest e Stein descrevem um algoritmo como um procedimento bem definido que transforma uma entrada numa saída. Há três coisas guardadas nessa descrição, e cada uma importa quando você escreve código.

• Preciso. Cada passo quer dizer uma coisa só. "Divida a por b e guarde o resto" é preciso; "faça os números ficarem menores de algum jeito" não é.
• Finito. Ele precisa parar. No algoritmo de Euclides, o resto é sempre menor que o número pelo qual você dividiu, então ele diminui a cada volta e tem de chegar a 0.
• Correto. Para toda entrada permitida, a saída é a resposta certa, não só nos exemplos que você testou.

Uma receita de cozinha costuma ser dada como exemplo do dia a dia, e é um exemplo justo: os ingredientes são a entrada, o prato é a saída e os passos estão em ordem. A diferença é o quanto quem lê completa sozinho. Um cozinheiro decide o que é "uma pitada". Um computador não decide nada, e é por isso que os algoritmos para computadores são escritos com cada passo explicado.

Mesmo problema, algoritmos diferentes

Um problema costuma ter muitos algoritmos corretos, e eles podem diferir enormemente na quantidade de trabalho que fazem. Para o máximo divisor comum de 1071 e 462, testar todos os números de 462 para baixo exige 442 tentativas até chegar a 21, enquanto o método de Euclides precisa de 3 divisões. Os dois estão corretos. Só um é rápido. Boa parte deste curso trata dessa segunda pergunta: depois que um método está correto, quantos passos ele leva, e como esse número cresce quando a entrada aumenta?

Para responder, os cientistas da computação contam passos básicos (uma comparação, uma troca, uma divisão) em vez de segundos. Os segundos dependem da máquina. Uma contagem de passos depende só do algoritmo e da entrada, então permite comparar dois métodos com justiça. O laboratório abaixo conta as comparações para você enquanto ordena uma fileira de barras. Experimente a mesma ordem inicial com dois métodos diferentes e observe os contadores.

Entradas, saídas e os passos entre elas

Antes de escrever um algoritmo, anote exatamente o que entra e o que precisa sair. Para o máximo divisor comum: a entrada são dois números inteiros positivos, e a saída é um número inteiro que divide os dois, sem que nenhum número maior faça o mesmo. Essa descrição diz como testar o resultado, e muitas vezes dá pistas dos passos. Ela também revela os casos extremos: e se um dos números for 0? (O laço acima devolve o outro número, que é a resposta certa.) E se os dois números forem iguais? Pensar nos casos extremos antes de rodar o código pega muitos erros.