Melhor, médio e pior caso
E a análise amortizada, que explica por que 'append' é O(1).
Big-O sozinho é ambíguo: o quicksort é O(n²) e O(n log n) ao mesmo tempo, dependendo de qual caso se fala.
Os três casos#
action procurar(xs, alvo):
cycle i, x in enumerate(xs):
given x is alvo:
yield i
yield -1| Caso | Quando | Custo |
|---|---|---|
| melhor | o alvo é o primeiro item | O(1) |
| médio | o alvo está em posição qualquer | O(n/2) = O(n) |
| pior | o alvo não existe | O(n) |
Por convenção, Big-O sem qualificação significa pior caso. É o que dá garantia: o programa nunca vai custar mais que isso.
Quando o médio é o que importa#
| Algoritmo | Melhor | Médio | Pior |
|---|---|---|---|
| busca linear | O(1) | O(n) | O(n) |
| busca binária | O(1) | O(log n) | O(log n) |
| quicksort | O(n log n) | O(n log n) | O(n²) |
| merge sort | O(n log n) | O(n log n) | O(n log n) |
| busca em vault | O(1) | O(1) | O(n) |
| bubble sort | O(n) | O(n²) | O(n²) |
O quicksort é usado na prática apesar do pior caso O(n²), porque o médio é O(n log n) e a constante é menor que a do merge sort. O pior caso só aparece com entrada já ordenada e pivô mal escolhido.
O vault é O(n) no pior caso — quando todas as chaves colidem. Na prática nunca acontece com uma função de espalhamento decente, e por isso se fala em O(1).
Análise amortizada#
xs.append(x) é O(1), mas nem sempre: quando o cluster enche, ele realoca e copia tudo, o que é O(n). Por que dizemos O(1)?
Porque a realocação dobra a capacidade. Partindo de 1, para chegar a n itens houve realocações em 1, 2, 4, 8, …, n — que somam menos de 2n cópias. Espalhando esse custo pelas n inserções, dá menos de 2 por inserção: O(1) amortizado.
// n appends custam O(n) no total, não O(n²)
action montar(n):
saida := []
cycle i from 1 to n:
saida.append(i)
yield saida
assert len(montar(1000)) is 1000Onde isso muda a decisão#
- Sistema de tempo real: o pior caso é o que conta. Um O(1) amortizado com picos O(n) pode estourar o prazo.
- Serviço web: o percentil 95 é o que o usuário sente. Por isso
Crucible.benchmarkreporta p95, não só a média. - Processamento em lote: o médio domina; picos ocasionais se diluem.
Ver Crucible: benchmark para medir isso no seu código.