Como o custo cresce com o tamanho

O teste de dobrar os dados

Existe um teste mental que revela a eficiência de um algoritmo na hora: pergunte o que acontece com o custo se os dados dobrarem de tamanho. A resposta classifica o algoritmo numa de poucas famílias, e cada família tem um destino bem diferente quando os dados ficam grandes. Se o custo não muda ao dobrar os dados, o algoritmo é de crescimento constante, o melhor de todos: ele é indiferente ao tamanho. Se o custo dobra quando os dados dobram, é linear: o esforço acompanha o tamanho, o que é razoável. Se o custo quadruplica ao dobrar os dados, é quadrático: começa a assustar, porque cresce rápido demais. E há um caso quase mágico, o logarítmico: dobrar os dados adiciona apenas um passo ao custo, um crescimento tão suave que parece indiferente ao tamanho.

Você já conheceu exemplos de cada família ao longo do curso, sem o nome. Acessar um item de lista pela posição, ou buscar um valor num dicionário pela chave, é constante: não importa o tamanho, custa um passo. A busca linear é linear: percorre até n itens, então dobrar a lista dobra o trabalho. Dois laços aninhados sobre a mesma lista, como na ordenação da bolha, são quadráticos: dobrar os dados quadruplica as operações. E a busca binária é logarítmica: corta pela metade a cada passo, então dobrar a lista só adiciona um corte. Reconhecer a família de um algoritmo é prever seu futuro: o quadrático que voa com mil itens pode travar com um milhão, enquanto o logarítmico nem sente a diferença.

Por que a forma importa mais que o número

Pode parecer estranho ignorar os números exatos e olhar só a forma do crescimento, mas há uma razão profunda para isso. Com dados grandes, a forma do crescimento domina qualquer detalhe. Imagine dois algoritmos: um linear que faz cem vezes n passos, e um quadrático que faz n ao quadrado passos. Para n pequeno, o linear parece pior, porque cem é um número grande. Mas conforme n cresce, o quadrático dispara e ultrapassa o linear, e a partir de um certo tamanho o linear vence com folga cada vez maior. A forma sempre vence o número quando os dados são grandes o bastante. É por isso que a análise de eficiência classifica algoritmos pela forma, não pela contagem exata: a forma é o que decide quem aguenta a escala. Um algoritmo de forma melhor sempre vence um de forma pior, dado um volume grande de dados.

A hierarquia do crescimento

Vale guardar uma pequena hierarquia das formas, da melhor para a pior, porque ela orienta muitas decisões de programação. No topo, a mais desejada, está a constante: o custo não muda com o tamanho. Logo abaixo, quase tão boa, a logarítmica: cresce tão devagar que aguenta volumes enormes. Depois a linear: razoável, o custo acompanha o tamanho de forma justa. Mais abaixo, a quadrática: aceitável para dados pequenos, perigosa para grandes. E existem formas ainda piores, que crescem tão rápido que se tornam inviáveis até com poucas dezenas de itens, mas essas são raras no dia a dia. Sempre que você puder trocar um algoritmo quadrático por um linear ou logarítmico, ou uma busca linear por uma consulta constante de dicionário, você está subindo nessa hierarquia, e é aí que moram os maiores ganhos de desempenho de um programa.