Pular para o conteúdo
</> Entendendo Algoritmos

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!)
05010015020015101520

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

Para n = 10, supondo 1 ms por operação
CustoExemploOperaçõesTempo
O(log n)Busca binária3,33 ms
O(n)Busca simples1010 ms
O(n log n)Quicksort (caso médio)33,233 ms
O(n²)Ordenação por seleção100100 ms
O(n!)Caixeiro-viajante (força bruta)3.628.8001,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.