Notação Big O
Como o tempo ou a memória de um algoritmo crescem com a entrada, com exemplos de cada complexidade.
6 min de leitura · Iniciante · Revisado em
A ideia em uma frase
A notação Big O descreve como o custo de um algoritmo cresce quando a entrada aumenta. O custo pode ser tempo (quantidade de operações) ou espaço (memória extra). Ela não mede segundos: compara tendências.
Formalmente, Big O é um limite superior de crescimento. No dia a dia e em entrevistas, ele costuma ser usado para o pior caso: a entrada que mais faz o algoritmo trabalhar.
As complexidades mais comuns
constante: O(1)
O custo não depende do tamanho da entrada.
acessar uma posição de um array ou uma chave de um Map.
const notas = [7, 9, 6, 10];
console.log(notas[3]);logarítmica: O(log n)
A cada passo, o problema cai pela metade. Dobrar a entrada acrescenta só um passo.
busca binária em uma lista ordenada.
for (let i = 1; i <= n; i = i * 2) {
console.log(i);
}linear: O(n)
O custo cresce na mesma proporção da entrada.
percorrer todos os itens de um array uma vez.
for (let i = 0; i < lista.length; i++) {
console.log(lista[i]);
}linearítmica: O(n log n)
Um pouco pior que linear. É o custo dos bons algoritmos de ordenação.
Array.prototype.sort, merge sort, heap sort.
const ordenada = [...lista].sort((a, b) => a - b);quadrática: O(n²)
Para cada item, o código percorre todos os itens de novo. Dobrar a entrada quadruplica o custo.
um loop dentro de outro sobre a mesma lista.
for (const a of lista) {
for (const b of lista) {
comparar(a, b);
}
}exponencial: O(2ⁿ)
Cada item a mais dobra o custo. Fica inviável muito rápido.
Fibonacci recursivo sem memória, gerar todos os subconjuntos.
function fib(n) {
if (n <= 1) return n;
return fib(n - 1) + fib(n - 2);
}Como chegar ao Big O de um código
Conte os passos que dependem da entrada
Loops sobre a entrada contam como
n. Loops aninhados sobre a mesma entrada multiplicam:n × n.Some partes em sequência
Um trecho
O(n)seguido de outroO(n²)custaO(n + n²).Fique só com o termo dominante
Para entradas grandes, o termo que cresce mais rápido manda:
O(n + n²)viraO(n²).Descarte constantes
Percorrer a lista duas vezes é
O(2n), que se escreveO(n). Big O compara formas de crescimento, não multiplicadores.
Exemplo: O(1) + O(n) + O(n²) = O(n²)
function temDuplicado(lista) {
if (lista.length < 2) return false; // O(1)
const total = lista.reduce((s, x) => s + x, 0); // O(n)
for (let i = 0; i < lista.length; i++) { // O(n²)
for (let j = i + 1; j < lista.length; j++) {
if (lista[i] === lista[j]) return true;
}
}
return false;
}O que Big O não diz
- Para entradas pequenas, um algoritmo
O(n²)simples pode ser mais rápido que umO(n log n)complexo. - Chamadas de biblioteca têm custo:
includes,indexOfespliceem arrays sãoO(n). - Rede, disco e banco de dados costumam dominar o tempo real de uma aplicação. Meça antes de otimizar.