Algoritmo e Estrutura de Dados

Big O Notation: Explicação completa.

·15 min de leitura

Introdução

Tempo e espaço são relativos. O mesmo algoritmo pode demorar 2s em um servidor e em outro 500ms. Isso pode acontecer a performance de um algoritmo depende muito do hardware que está sendo rodado.

Com isso posto, como podemos "medir" um algoritmo já que o tempo é relativo ao hardware em alguma medida?

Para resolver isso tempos o famoso: Big O Notation. Na pergunta eu coloquei a palavra medir entre aspas, pois na verdade o Big O não mede nada. Na prática o que fazemos é classificar, é dizer como esse algoritmo se comporta em relação ao tempo e espaço.

Deixa eu exemplificar para ficar claro. Em um cenário na qual precisamos ordenar um array na cada de dezenas, na prática, qualquer algoritmo é suficiente. Mas no cenário que estamos lidando com centenas ou milhares de itens a converda muda. Nesse cenário, o algoritmo que você escolher fazer total diferença. Se você usar um algoritmo como o Bubble Sort, que para ordenar ele faz o que chamamos de "Força Bruta", onde ele percorre e compara repetidamente todos os itens. Esse tipo classificado como O(n²). Já o algoritmo Merge Sort é mais eficiênte pois tem a classificação O(n log n), pois ele tem a filosófia de "dividir para conquistar". E na hierarquia do Big O, um algoritmo com a notação O(n log n) é melhor que o O(n²). E em ambiente com "dados reais", essa é a diferença de um sistema travar e outro não.

Antes de mostrar como classificar um algoritmo, preciso deixar algo claro. No exemplo anterior eu falei sobre escolher o "Melhor" algoritmo. Mas quando estamos analisando com Big O, não estamos olhando necessariamente a sua implementação. Nós queremos saber como ele se comporta no pior cenário. Ou seja, procuramos analisar como esse algoritmo se comporta se os dados começarem a crescer. Lógico que com mais dados o algoritmo provavelmente vai demorar mais, tirando o cenário de algoritmos O(1), mas o que queremos saber é como esse crescimento de tempo acontece. Isso é o que chamamos de Complexidade Temporal.

Pode suar um pouco repetitivo, mas é necessário.

Agora vamos entender como classificar um algoritmo.

Classificando um algoritmo

O primeiro passo é fixar o que chamamos de tamanho da entrada. Em geral usamos a letra n: pode ser o número de elementos de um array, o tamanho de uma string, a quantidade de nós de um grafo, e assim por diante. A ideia do Big O não é dizer "quantos milissegundos" o código vai levar; é dizer como o custo cresce quando n fica grande.

Na prática, quase sempre estamos interessados no pior caso (ou em um caso representativo), porque é ele que nos protege quando os dados são adversários: entradas grandes, já ordenadas, já bagunçadas, etc. Existem também análises de melhor caso e caso médio, mas o pior caso é o ponto de partida mais útil para comparar algoritmos de forma conservadora.

Tempo e espaço

Você pode classificar o algoritmo em relação ao tempo (quantas operações “relevantes” o fluxo faz em função de n) e em relação ao espaço (memória extra além da própria entrada — variáveis, pilhas de recursão, estruturas auxiliares). As duas dimensões importam: um algoritmo pode ser rápido em tempo O(n) mas usar O(n) de memória extra, ou ser O(n log n) no tempo e O(1) extra no espaço, dependendo do problema.

Diferença entre as classificações

O(1) — Tempo Constante

O que significa: não importa se a entrada tem 1 elemento ou 1 bilhão, o algoritmo sempre executa o mesmo número de operações. O custo é fixo.

Por que acontece: porque o código acessa diretamente o que precisa, sem precisar percorrer ou comparar nada. O caminho até o resultado tem comprimento fixo, independentemente de n.

Exemplos típicos:

  • Acessar um índice de array: arr[42] — o endereço de memória é calculado diretamente.
  • Inserir ou remover o primeiro elemento de uma linked list com ponteiro para o head.
  • Verificar se um mapa/hash table contém uma chave (caso médio).
  • Empilhar (push) ou desempilhar (pop) de uma stack.
function primeiroDobrado(arr) {
  return arr[0] * 2; // sempre uma operação, não importa o tamanho do array
}

Visualização do crescimento:

n operações
11
1001
1.0001
1.000.0001

Resumo: ideal. Se você consegue resolver um problema em O(1), não existe nada melhor.

O(log n) — Tempo Logarítmico

O que é logarítmico?: É o inverso da exponencial. Enquanto a exponencial aumenta a cada interação, igual juros compostos que a cada mês a porentagem do juros é sobre a dívida atual. Em pouco tempo a divida dobra e continua crescendo desenfreadamente. Já o logarítmico é o inverso disso, ele diminui a cada interação.

O que significa: a cada passo, o algoritmo descarta uma fração do problema, geralmente a metade. Isso faz o número de operações crescer de forma extremamente lenta mesmo quando n explode.

Por que acontece: o mecanismo central é a divisão repetida. Se você divide n ao meio sucessivamente, em quantos passos chega a 1? Exatamente log₂ n passos. Com n = 1.000.000, são apenas ~20 passos. Com n = 1.000.000.000, são ~30 passos.

Exemplos típicos:

  • Busca Binária em array ordenado.
  • Operações em Árvore Binária de Busca balanceada (inserção, remoção, busca).
  • Operações em Heap (subir/descer um elemento).
  • Algoritmo de exponenciação rápida.
// Busca binária — a cada iteração o espaço de busca cai pela metade
function buscaBinaria(arr, alvo) {
  let esq = 0;
  let dir = arr.length - 1;

  while (esq <= dir) {
    const meio = Math.floor((esq + dir) / 2);

    if (arr[meio] === alvo) {
      return meio;
    } else if (arr[meio] < alvo) {
      esq = meio + 1; // descarta metade esquerda
    } else {
      dir = meio - 1; // descarta metade direita
    }
  }

  return -1;
}

Visualização do crescimento:

n operações (~log₂ n)
83
1.000~10
1.000.000~20
1.000.000.000~30

Resumo: extremamente eficiente. Qualquer algoritmo que "corta" o problema ao meio em cada passo provavelmente é O(log n).

O(n) — Tempo Linear

O que significa: o número de operações cresce de forma diretamente proporcional ao tamanho da entrada. Dobrou n, dobrou o trabalho.

Por que acontece: porque o algoritmo precisa visitar cada elemento pelo menos uma vez. Não há como escapar: se você precisa olhar para todos, o custo mínimo é proporcional à quantidade.

Exemplos típicos:

  • Percorrer um array para encontrar o maior/menor elemento.
  • Somar todos os elementos de uma lista.
  • Busca linear (quando o array não está ordenado).
  • Copiar um array.
  • Verificar se uma string é palíndromo.
function maiorElemento(arr) {
  let maior = arr[0];
  for (const v of arr) { // percorre todos os n elementos
    if (v > maior) {
      maior = v;
    }
  }
  return maior;
}

Visualização do crescimento:

n operações
11
100100
1.0001.000
1.000.0001.000.000

Resumo: é o "custo mínimo" para a maioria dos problemas que exigem processar toda a entrada. É considerado eficiente para volumes grandes.

O(n log n) — Tempo Linearítmico

O que significa: um pouco pior que linear, mas muito melhor que quadrático. É o resultado de fazer uma operação O(log n) para cada um dos n elementos — ou, equivalentemente, dividir o problema em log n níveis com trabalho total O(n) em cada nível.

Por que acontece: é a assinatura de algoritmos que usam a estratégia de dividir para conquistar (divide and conquer). O problema é dividido ao meio recursivamente (gera log n níveis de divisão), e em cada nível é feito trabalho linear para combinar as partes (merge, por exemplo).

Exemplos típicos:

  • Merge Sort — divide o array ao meio, ordena cada metade recursivamente e une os resultados.
  • Heap Sort — constrói uma heap (O(n)) e extrai o máximo n vezes (O(log n) por extração).
  • Quick Sort — no caso médio, as partições ficam balanceadas, resultando em O(n log n).
  • FFT (Transformada Rápida de Fourier).
function mergeSort(arr) {
  if (arr.length <= 1) return arr;

  const meio = Math.floor(arr.length / 2);
  const esq = mergeSort(arr.slice(0, meio)); // divide ao meio → log n níveis
  const dir = mergeSort(arr.slice(meio));

  return merge(esq, dir); // une em O(n) — trabalho linear por nível
}

function merge(esq, dir) {
  const resultado = [];
  let i = 0, j = 0;

  while (i < esq.length && j < dir.length) {
    if (esq[i] <= dir[j]) {
      resultado.push(esq[i++]);
    } else {
      resultado.push(dir[j++]);
    }
  }

  return resultado.concat(esq.slice(i)).concat(dir.slice(j));
}

Visualização do crescimento:

n operações (~n log₂ n)
8~24
1.000~10.000
1.000.000~20.000.000

Resumo: é a classe dos melhores algoritmos de ordenação por comparação. Matematicamente provado que não é possível ordenar por comparação em menos que O(n log n) no caso geral.

O(n²) — Tempo Quadrático

O que significa: para cada elemento, o algoritmo faz trabalho proporcional ao tamanho total da entrada. Ou seja, dois laços aninhados, cada um indo até n.

Por que acontece: geralmente porque o algoritmo compara ou processa cada par de elementos. O número de pares possíveis em n elementos é n(n-1)/2, que é O(n²).

Exemplos típicos:

  • Bubble Sort, Insertion Sort, Selection Sort — comparam pares repetidamente.
  • Verificar se há duplicatas em um array (abordagem ingênua com dois laços).
  • Multiplicação de matrizes (abordagem ingênua é O(n³), mas o produto de um vetor por uma matriz é O(n²)).
  • Encontrar todos os pares com soma igual a um alvo (abordagem força bruta).
// Bubble Sort — dois laços aninhados: O(n²)
function bubbleSort(arr) {
  const n = arr.length;
  for (let i = 0; i < n; i++) {          // laço externo: n vezes
    for (let j = 0; j < n - i - 1; j++) { // laço interno: até n vezes
      if (arr[j] > arr[j + 1]) {
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
      }
    }
  }
}

Visualização do crescimento:

n operações (~n²)
10100
10010.000
1.0001.000.000
10.000100.000.000

Resumo: aceitável para entradas pequenas (até alguns milhares), mas começa a travar com volumes maiores. Sempre que ver dois laços aninhados, suspeite de O(n²).

O(n³) — Tempo Cúbico

O que significa: três laços aninhados, cada um proporcional a n. O trabalho cresce ao cubo.

Por que acontece: quando o problema envolve triplas de elementos ou a combinação de dois subproblemas quadráticos. Cada elemento do outer loop dispara um bloco O(n²) dentro.

Exemplos típicos:

  • Multiplicação de matrizes (algoritmo clássico): para calcular cada célula da matriz resultado, você percorre uma linha inteira e uma coluna inteira.
  • Floyd-Warshall para menor caminho entre todos os pares de vértices em um grafo de n nós.
  • Verificar se há uma tripla (i, j, k) tal que arr[i] + arr[j] + arr[k] = 0 (abordagem força bruta).
// Multiplicação de matrizes n×n — O(n³)
function multiplicarMatrizes(A, B) {
  const n = A.length;
  const C = Array.from({ length: n }, () => new Array(n).fill(0));

  for (let i = 0; i < n; i++) {        // laço 1
    for (let j = 0; j < n; j++) {      // laço 2
      for (let k = 0; k < n; k++) {    // laço 3
        C[i][j] += A[i][k] * B[k][j];
      }
    }
  }

  return C;
}

Visualização do crescimento:

n operações (~n³)
101.000
1001.000.000
500125.000.000
1.0001.000.000.000

Resumo: já é considerado lento para n acima de alguns centenas. Quando vê três laços aninhados, é sinal de que provavelmente há uma abordagem melhor. Para multiplicação de matrizes, existem algoritmos mais eficientes como o Algoritmo de Strassen, que chega a O(n^2.81).

O(2ⁿ) — Tempo Exponencial

O que significa: a cada novo elemento adicionado à entrada, o número de operações dobra. O crescimento é catastrófico — com n = 50 já estamos falando de mais de 1 quadrilhão de operações.

Por que acontece: acontece em algoritmos que exploram todas as combinações possíveis de um conjunto, ou em recursões que se ramificam em 2 em cada nível sem reaproveitar resultados já calculados. Cada decisão binária (incluir ou não incluir um elemento) dobra o espaço de busca.

Exemplos típicos:

  • Fibonacci recursivo ingênuo — cada chamada gera duas novas chamadas, criando uma árvore de chamadas que cresce exponencialmente.
  • Problema da Mochila (força bruta) — para cada item, você decide incluir ou não.
  • Subconjuntos de um conjunto — um conjunto de n elementos tem 2ⁿ subconjuntos.
  • Alguns problemas de backtracking sem poda eficiente.
// Fibonacci recursivo — O(2ⁿ)
// fib(5) chama fib(4) e fib(3)
// fib(4) chama fib(3) e fib(2)  ← fib(3) calculado duas vezes!
// ... e isso se repete exponencialmente
function fib(n) {
  if (n <= 1) return n;
  return fib(n - 1) + fib(n - 2); // duas chamadas recursivas por nível
}

// A versão com memoization reduz para O(n):
function fibMemo(n, memo = {}) {
  if (n <= 1) return n;
  if (n in memo) return memo[n]; // reusa o que já foi calculado
  memo[n] = fibMemo(n - 1, memo) + fibMemo(n - 2, memo);
  return memo[n];
}

Visualização do crescimento:

n operações (~2n)
101.024
20~1 milhão
30~1 bilhão
50~1 quadrilhão
64~18 quintilhões

Resumo: inviável para qualquer n moderado. A solução quase sempre envolve memoization, programação dinâmica ou reformulação do problema para evitar recalcular subproblemas.

O(n!) — Tempo Fatorial

O que significa: o número de operações cresce de acordo com o fatorial de n. É o pior crescimento assintótico que existe na prática. 10! = 3.628.800. 20! ≈ 2,4 × 10¹⁸. 30! já ultrapassa o número de átomos no universo observável.

Por que acontece: quando o algoritmo precisa explorar todas as permutações possíveis de uma entrada. O número de maneiras de ordenar n elementos é exatamente n! — para cada posição, escolhemos dentre os elementos restantes, e o produto de todas as escolhas é n × (n-1) × (n-2) × … × 1.

Exemplos típicos:

  • Problema do Caixeiro Viajante (TSP) por força bruta — encontrar o caminho mais curto que visita n cidades exatamente uma vez: é necessário testar todas as n! rotas possíveis.
  • Geração de todas as permutações de uma sequência.
  • Quebra de senha por permutação — testar todas as combinações de caracteres em ordem.
// Gera todas as permutações de um array — O(n!)
function permutacoes(arr, inicio = 0, resultado = []) {
  if (inicio === arr.length) {
    resultado.push([...arr]); // copia o estado atual
    return resultado;
  }

  for (let i = inicio; i < arr.length; i++) {
    [arr[inicio], arr[i]] = [arr[i], arr[inicio]]; // troca
    permutacoes(arr, inicio + 1, resultado);        // recursão
    [arr[inicio], arr[i]] = [arr[i], arr[inicio]]; // desfaz troca
  }

  return resultado;
}

// permutacoes([1, 2, 3]) gera: [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]
// 3! = 6 permutações

Visualização do crescimento:

n n!
5120
103.628.800
151.307.674.368.000
20~2,4 × 1018
25~1,5 × 1025

Resumo: completamente impraticável além de entradas triviais (cerca de n ≤ 12). Problemas que exigem O(n!) por força bruta são geralmente NP-difíceis, e a solução real usa heurísticas, aproximações ou programação dinâmica para torná-los tratáveis.

Como enxergar a ordem na prática

Alguns atalhos mentais ajudam muito:

  • Um único laço que percorre toda a entrada costuma indicar tempo linear, O(n).
  • Dois laços aninhados, cada um indo até n, costumam levar a algo da ordem de n × n, ou seja quadrático, O(n²) — típico de comparações repetidas entre todos os pares.
  • Dividir o problema ao meio repetidamente (e fazer trabalho constante ou linear em cada etapa) costuma aparecer como logarítmico ou linearítmico, O(log n) ou O(n log n).
  • Recursão que resolve o mesmo subproblema muitas vezes sem reaproveitar resultado pode explodir para exponencial, da ordem de O(2ⁿ) ou pior, dependendo da árvore de chamadas.

Constantes multiplicativas (por exemplo, “faço 3n operações”) e termos de ordem menor (algo como n² + 100n) não mudam a classe no Big O quando n cresce: o termo que domina o crescimento é o que fica na notação — nesse exemplo, O(n²).

Com isso em mente, a hierarquia usual — do melhor crescimento assintótico para o pior — aparece na tabela da próxima seção, com nomes e exemplos típicos.

Resumo da hierarquia do Big O

Notação Nome Descrição
O(1) Constante O tempo de execução não muda, independentemente do tamanho de n. Ex: Acessar um índice de um array.
O(log n) Logarítmica O tempo cresce de forma muito lenta. Comum em algoritmos que dividem o problema ao meio. Ex: Busca Binária.
O(n) Linear O tempo cresce proporcionalmente ao tamanho da entrada. Ex: Percorrer uma lista simples.
O(n log n) Linearítmica Um pouco pior que a linear, mas ainda muito eficiente para grandes volumes. Ex: Merge Sort e Quick Sort.
O(n2) Quadrática O tempo cresce ao quadrado da entrada. Comum em loops aninhados simples. Ex: Bubble Sort.
O(n3) Cúbica Três loops aninhados. Geralmente sinaliza que o algoritmo precisa de otimização.
O(2n) Exponencial O tempo dobra a cada novo elemento. Frequentemente visto em recursões sem otimização. Ex: Fibonacci recursivo.
O(n!) Fatorial O pior cenário possível. O crescimento é astronômico. Ex: Problema do Caixeiro Viajante via força bruta.

Conclusão

Resuma os pontos principais do artigo. Reforce os conceitos mais importantes e faça uma conexão com o contexto maior (série de artigos, aplicação prática, etc.).

Referências