A constante que decide
Big-O ignora a constante de propósito — e é ela que decide qual código é mais rápido no tamanho que você realmente tem.
O(n) e O(n²) dizem como o custo cresce. Nenhum dos dois diz quanto o custo é. Entre um O(n) com constante mil e um O(n²) com constante um, o segundo ganha até n = 1000 — e muito sistema nunca passa de mil.
Essa página é o contrapeso das outras: ela existe para que a análise não vire superstição.
Uma medição que prova o ponto#
A ordenação por contagem é O(n + k); a ordenação por comparação é O(n log n). A primeira é assintoticamente melhor. Com 200 mil inteiros de 0 a 999:
comparacao (n log n): 13.5 ms
contagem (n + k): 381.3 msA melhor no papel perdeu por 28x. O motivo não é o algoritmo: sorted é um Timsort escrito em C, e a contagem está escrita em DataForge, interpretada. A constante de "uma volta de laço no interpretador" é centenas de vezes maior que a de "uma comparação em C".
E uma em que a classe ganha, com folga#
O mesmo par de forças, invertido: aqui os dois lados pagam a mesma constante, e só a classe separa.
adopt Arcane.Time as T
N := 50000
BUSCAS := 2000
xs := [i cycle i in range(0, N)]
v := {}
cycle i in xs:
v[i] := yes
// procura itens AUSENTES: o pior caso da busca linear, e o caso
// honesto — um item no começo da lista sai rápido por sorte.
inicio := T.monotonic()
cycle k from 1 to BUSCAS:
given (N + k) in xs:
out "achou"
cluster_ms := (T.monotonic() - inicio) * 1000
inicio := T.monotonic()
cycle k from 1 to BUSCAS:
given (N + k) in v:
out "achou"
vault_ms := (T.monotonic() - inicio) * 1000
out $"cluster: {round(cluster_ms, 1)} ms"
out $"vault: {round(vault_ms, 1)} ms"
out $"razao: {round(cluster_ms / vault_ms, 1)}x"cluster: 255.8 ms
vault: 2.2 ms
razao: 118.5x118x, e essa distância cresce com n — é a diferença entre O(n) e O(1). Nenhuma constante salva a busca linear aqui, porque não há constante: há uma classe.
Como um benchmark mente#
A primeira versão da medição acima dizia o contrário — que o cluster era 3x mais rápido que o vault. Dois erros, os dois comuns:
| O erro | O que ele fez | A correção |
|---|---|---|
| procurar itens que estão no começo | in de cluster achava na posição 1, 2, 3… e nunca percorria nada | procurar itens ausentes, ou sorteados |
| medir a montagem junto da busca | construir o vault de 50 mil dominou o tempo | montar antes, cronometrar só a busca |
Um benchmark que confirma o que você esperava é o mais perigoso de todos — é o que ninguém revisa. Quando o número contrariar a teoria, desconfie do número e da teoria, nessa ordem.
Os quatro custos que o Big-O não conta#
| Custo | Por que ele some na notação | Quando ele decide |
|---|---|---|
| a constante | some na definição de O | sempre que n é pequeno |
| localidade de memória | não é uma operação | percorrer um cluster contíguo é muito mais rápido que seguir ponteiros, com a mesma classe |
| alocação | conta como O(1) | um algoritmo que aloca por item perde de um que trabalha no lugar |
| partida | não depende de n | criar 5 threads custa mais que 60 ms de trabalho — ver paralelismo |
Medir: as três ferramentas#
| Ferramenta | Responde | Quando usar |
|---|---|---|
| `dataforge big-o` | como o custo cresce | antes de escrever, e no CI |
| `dataforge profile` | onde o tempo está indo hoje | quando já está lento e você não sabe onde |
| `Arcane.Bench` | quanto custa este trecho | para comparar duas implementações |
As três respondem perguntas diferentes, e nenhuma substitui as outras. O big-o não sabe que você só tem 200 itens; o profile não sabe que amanhã serão 200 mil.
A ordem em que vale a pena mexer#
- Meça. O gargalo quase nunca está onde a intuição aponta — este interpretador já teve sete otimizações feitas assim, e nenhuma delas no lugar esperado.
- Troque a classe primeiro.
O(n²)paraO(n)ganha de qualquer ajuste de constante, sencrescer. - Depois ataque a constante, e só no trecho que o profile apontou.
- Meça de novo. Uma otimização que não foi medida depois é uma hipótese, não um ganho.