Pular para o conteúdo
</> Entendendo Algoritmos

Constantes escondidas

A notação Big O descarta a constante: O(n) significa "n vezes algum tempo fixo". Quase sempre isso basta, mas às vezes a constante decide quem vence. Imagine uma busca simples que gasta 1 ms por item e uma busca binária que gasta 1 s por passo (porque, por exemplo, cada passo exige uma operação muito mais pesada). Para listas pequenas, a "pior" busca ganha.

Explicação do algoritmo: escolha um nível para ler.

Busca simples
1,0 s
Busca binária
10,0 s
Mais rápida aqui
Busca simples
A busca binária só passa a compensar a partir de cerca de 13.747 itens. Abaixo disso, a constante maior pesa mais que o crescimento mais lento.
Busca simples Busca bináriaeixo vertical em escala logarítmica
10 ms1,0 s1,7 min2,8 h11,6 dias1010^210^310^410^510^610^710^810^910^10

Arraste para os lados para ver o gráfico inteiro.

Por que isso importa

O mesmo raciocínio explica por que o quicksort e a ordenação por mesclagem, ambos O(n log n) em média, não têm o mesmo desempenho na prática: segundo o livro, o quicksort costuma ter uma constante menor e por isso costuma ser mais rápido. Isso depende da implementação e do hardware, então vale medir em vez de supor. Escolher bem o pivô evita o pior caso do quicksort.

A lição do livro: Big O diz como o custo cresce, não quanto tempo leva. Use-o para comparar algoritmos com crescimentos diferentes e, quando o crescimento é o mesmo, olhe também para as constantes.