Contar passos, não segundos

Por que o cronômetro engana

Como saber se um algoritmo é eficiente? A tentação é cronometrar: rode o programa e veja quanto demora. Mas o cronômetro engana, e por um motivo simples. O mesmo código roda mais rápido num computador potente e mais devagar num celular antigo; roda diferente se a máquina está ocupada com outras tarefas; roda diferente conforme a linguagem. Se você compara dois algoritmos pelo tempo, pode estar medindo a máquina, não o algoritmo. É como comparar dois corredores cronometrando um no plano e outro na subida: o relógio não conta a história justa. Para medir o algoritmo em si, você precisa de algo que não dependa de onde ele roda.

Esse algo é a contagem de passos. Em vez de perguntar quantos segundos, você pergunta quantas operações básicas o algoritmo executa: quantas comparações, quantas somas, quantas trocas. Esse número não muda de um computador para outro; ele é uma propriedade do algoritmo. Uma busca linear numa lista de mil itens faz até mil comparações, seja num supercomputador, seja num celular. O supercomputador faz essas mil comparações mais rápido, claro, mas são mil comparações nos dois. Contando passos, você compara algoritmos de forma justa, isolando a esperteza do método da força bruta da máquina. É assim que a computação fala de eficiência: em passos, não em segundos.

Contando passos na prática

Contar passos é mais simples do que parece: você olha o algoritmo e conta quantas vezes as operações principais rodam. Um laço que percorre uma lista de n itens fazendo uma comparação em cada volta faz n comparações. Dois laços aninhados, cada um de n voltas, fazem n vezes n operações, ou seja, n ao quadrado, exatamente o que você viu no módulo de laços aninhados. Uma busca binária faz cerca de vinte passos num milhão de itens, porque corta pela metade. Repare que, ao contar, a gente não se importa tanto com os detalhes miúdos (se são exatamente n ou n mais três comparações); o que importa é a forma geral do crescimento: cresce como n, como n ao quadrado, como o logaritmo? Essa forma é o coração da eficiência, e é o assunto da próxima aula.

lista tem 5 itens
soma <- 0
para i de 0 até 4 faça
  para j de 0 até 4 faça
    soma <- soma + 1
  fim
fim

O que realmente importa na contagem

Ao contar passos, um detalhe muda a mentalidade: o que importa é o comportamento com dados grandes, não com dados pequenos. Para uma lista de cinco itens, qualquer algoritmo é instantâneo, então a eficiência não faz diferença ali. A eficiência começa a importar quando os dados crescem, e é aí que as diferenças entre algoritmos explodem. Por isso a análise de eficiência foca em como o número de passos cresce conforme o tamanho aumenta, e ignora os detalhes que não mudam essa tendência. Um algoritmo que faz n mais dez passos e outro que faz n mais mil passos têm, no fundo, o mesmo comportamento quando n é gigante: os dois crescem como n. Essa forma de olhar, focada na tendência de crescimento e não nos números exatos, é o que torna a análise de eficiência poderosa e simples ao mesmo tempo.