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

  1. Conte os passos que dependem da entrada

    Loops sobre a entrada contam como n. Loops aninhados sobre a mesma entrada multiplicam: n × n.

  2. Some partes em sequência

    Um trecho O(n) seguido de outro O(n²) custa O(n + n²).

  3. Fique só com o termo dominante

    Para entradas grandes, o termo que cresce mais rápido manda: O(n + n²) vira O(n²).

  4. Descarte constantes

    Percorrer a lista duas vezes é O(2n), que se escreve O(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 um O(n log n) complexo.
  • Chamadas de biblioteca têm custo: includes, indexOf e splice em arrays são O(n).
  • Rede, disco e banco de dados costumam dominar o tempo real de uma aplicação. Meça antes de otimizar.

Referências

Trilhas relacionadas