Notação Big O
Big O não mede segundos: mede como o número de operações cresce quando a entrada cresce. Um algoritmo mais rápido para entradas pequenas pode perder feio para uma entrada grande.
Explicação do algoritmo: escolha um nível para ler.
Operações para n de 1 a 20 (eixo cortado em 200)
O(log n)O(n)O(n log n)O(n²)O(n!)
Arraste para os lados para ver o gráfico inteiro.
Para n = 10, supondo 1 ms por operação
| Custo | Exemplo | Operações | Tempo |
|---|---|---|---|
| O(log n) | Busca binária | 3,3 | 3 ms |
| O(n) | Busca simples | 10 | 10 ms |
| O(n log n) | Quicksort (caso médio) | 33,2 | 33 ms |
| O(n²) | Ordenação por seleção | 100 | 100 ms |
| O(n!) | Caixeiro-viajante (força bruta) | 3.628.800 | 1,0 h |
Experimente n = 100: a busca binária precisa de cerca de 7 operações, enquanto uma busca simples precisa de 100. Já o O(n!) é impraticável a partir de n ≈ 20.