Uma introdução visual à notação Big O

(samwho.dev)

2 pontos por GN⁺ 2025-08-26 | 1 comentários | Compartilhar no WhatsApp

Notação Big O expressa o desempenho de uma função pelo padrão de crescimento conforme a variação do tamanho da entrada
O texto explica, com exemplos, os principais tipos de Big O: constante, logarítmico, linear e quadrático
Dependendo da estrutura de dados e do algoritmo, a complexidade de tempo muda, mostrando diferenças em tarefas como ordenação e busca em arrays
Para melhorar o desempenho do código na prática, os pontos centrais são escolher a estrutura de dados adequada e eliminar operações desnecessárias dentro de loops
Big O sempre representa, da forma mais simplificada possível, a relação entre entrada e tempo de execução, e ao otimizar desempenho é importante medir o código diretamente

Visão geral da notação Big O

Notação Big O é uma forma de descrever o padrão de crescimento do tempo de execução conforme o tamanho da entrada (n), em vez de medir diretamente o tempo
Ela classifica o tempo de execução de uma função de acordo com a entrada, e normalmente analisa formas como constante (O(1)), logarítmica (O(log n)), linear (O(n)) e quadrática (O(n²))
Este texto explica cada categoria por meio de conceitos, exemplos visuais e exemplos de código reais, de forma acessível até para iniciantes

Iteração (Iterating) e algoritmos lineares

A função sum(n) é um exemplo de estrutura iterativa que soma de 1 até n, e quanto maior o valor de entrada n, maior o tempo de execução em proporção direta
Na prática, sum(1e9) leva cerca de 1 segundo, e sum(2e9) cerca de 2 segundos, então o tempo de relógio (wall-clock time) cresce em um padrão O(n)
Complexidade de tempo é a relação entre a entrada da função e o tempo de execução, e isso é expresso com notação Big O (O(n) — proporcional a n)
Em vez de iterar, usar a fórmula matemática sum(n) = (n*(n+1))/2 faz com que o tempo de execução seja constante, independentemente do valor de entrada n
Esse tipo de função tem complexidade de tempo constante O(1), cuja característica é não apresentar crescimento no tempo de execução conforme a entrada muda

Sintaxe da notação Big O

O O de Big O vem de “Order” (ordem de crescimento) e indica apenas a forma de crescimento em si
Ela não representa o valor absoluto do tempo de execução, mas sim apenas o 'padrão' de crescimento em relação à entrada, de forma concisa
Por exemplo, mesmo para uma função O(n), não se escreve de forma detalhada como 'O(2n)' ou 'O(n+1)'; escolhe-se apenas o termo mais simples e dominante

Redução de tempo usando a composição da entrada

Como no exemplo da fórmula de sum(n), é possível transformar a complexidade de tempo de O(n) em O(1) ao melhorar o algoritmo
Ainda assim, ter complexidade constante não significa automaticamente ser mais rápido; o tempo total de execução pode variar conforme o tipo de operação
Um algoritmo O(n) pode ser mais rápido do que um O(1) para certas entradas específicas, mas à medida que a entrada cresce, o método O(1) sempre tende a levar vantagem

Ordenação (Sorting) e algoritmos quadráticos: exemplo com Bubble Sort

Bubble Sort é um exemplo básico de ordenação que organiza um array repetindo trocas entre elementos adjacentes
Quando o array já está ordenado, basta 1 passagem (O(n)); em ordem inversa, é preciso percorrer repetidamente n vezes → no pior caso, o total de operações é n²
Um algoritmo O(n²) tem tempo de execução que cresce fortemente de forma quadrática à medida que a entrada aumenta
Na prática, Big O normalmente considera o pior caso (worst-case), embora em alguns contextos também se indiquem média e melhor caso
Dependendo do estado inicial do array, o número de repetições pode diminuir, mas considerando o pior caso, ele continua sendo classificado como complexidade quadrática

Busca (Searching) e algoritmos logarítmicos: exemplo com busca binária

Busca binária (Binary Search) estima o valor central de um intervalo ordenado e, em cada etapa, elimina metade da área candidata
Por exemplo, para adivinhar um número específico entre 1 e 100, são necessárias no máximo 7 tentativas; entre 1 e 1 bilhão, menos de 31 tentativas
Como a lista de candidatos diminui pela metade a cada etapa, o tempo de execução é O(log n) (complexidade logarítmica)
Algoritmos logarítmicos têm crescimento extremamente lento quando n aumenta, sendo muito mais eficientes do que os lineares ou quadráticos
Ao comparar gráficos, a diferença de crescimento entre log n, n e n² aparece de forma muito clara

Aplicação prática: dicas para melhorar a complexidade de tempo

Encontrar um item em uma lista

Em geral, uma função que procura um valor em um array é O(n)
Se a busca for frequente, usar uma estrutura de dados como Set pode melhorar para O(1)
Porém, o próprio processo de conversão com new Set(array) é O(n), então isso só vale a pena para consultas frequentes (considerando o custo da conversão)
Exemplo: items.has("banana") oferece complexidade de tempo constante

Escrever loops aproveitando o índice

Código que usa .indexOf dentro do loop, como abaixo, costuma ser uma causa comum de problema de desempenho

function buildList(items) {
  const output = [];
  for (const item of items) {
    const index = items.indexOf(item);
    output.push(`Item ${index + 1}: ${item}`);
  }
  return output.join("\n");
}

Como .indexOf é uma operação O(n) dentro do loop, o padrão total se torna O(n^2)

Ao usar iteração baseada em índice ou forEach((item, index) => ...), é possível melhorar para O(n)

function buildList(items) {
  const output = [];
  for (let i = 0; i < items.length; i++) {
    output.push(`Item ${i + 1}: ${items[i]}`);
  }
  return output.join("\n");
}

Uso de memoization

Em estruturas com cálculos repetidos em chamadas sucessivas, como no fatorial, é possível melhorar o desempenho aplicando cache de resultados (usando Map)
A consulta em Map é O(1), o que minimiza recálculos desnecessários

Ainda assim, o cache contribui para melhorar o tempo médio e, mesmo que a complexidade no pior caso não mude, pode trazer ganho real de eficiência

const cache = new Map();
function factorial(n) {
  if (cache.has(n)) {
    return cache.get(n);
  }
  if (n === 0) {
    return 1;
  }
  const result = n * factorial(n - 1);
  cache.set(n, result);
  return result;
}

Avaliação de desempenho e conclusão

Ao melhorar o desempenho de um código, além da complexidade de tempo teórica, é preciso confirmar a melhoria real com testes de execução diretos
Big O expressa, da forma mais essencial e simplificada possível, a relação e o padrão de crescimento entre entrada e tempo de execução
Escolher bons algoritmos e otimizar a estrutura de dados permite maximizar a eficiência do código

Resumo

Notação Big O expressa a relação entre o valor de entrada de uma função e o tempo de execução
Principais categorias de desempenho: O(1) (constante), O(log n) (logarítmica), O(n) (linear), O(n^2) (quadrática)
Para escrever código eficiente, é importante usar o algoritmo adequado e otimizar os loops
O desempenho real deve ser medido diretamente para validar se houve melhoria
Usar gráficos comparativos de crescimento ajuda a entender rapidamente as características da complexidade de tempo

1 comentários

GN⁺ 2025-08-26

Comentários no Hacker News

Este artigo, junto com os comentários no HN, continua a tradição de explicar Big O Notation e discutir sua aplicação prática e detalhes técnicos. Como exemplos úteis, há este texto explicativo e este texto sobre a postura de especialistas
- Nos comentários do texto anterior, um usuário chamado Pyon mostrou uma postura ácida e inflexível. Mas a resposta do Ned também não foi lá grande coisa. Ele não explica os detalhes técnicos com precisão e fica só contornando com expressões como “certos detalhes específicos”. Fica a sensação de que faltou explicar por que a crítica dele era mera implicância e por que o próprio conteúdo foi rejeitado. O Ned aponta uma direção correta em relação à comunicação e à empatia online. Ainda assim, como educador, eu queria que ele ao menos tivesse apontado por que aquela discussão técnica era excessivamente minuciosa ou mera picuinha. O próprio Ned só diz “eu não sabia disso há décadas”, e isso parece insuficiente. E relendo a thread original de comentários, o Ned na verdade debateu de forma bem diplomática e séria. Então fico me perguntando por que essa análise ficou de fora do post do blog. Pessoalmente, não sei bem quais eram os detalhes técnicos, mas queria que alguém resumisse isso de forma simples ao menos uma vez
- Eu sou mais do tipo especialista crítico. Sempre me decepciono quando vejo tentativas de ensinar temas complexos em blogs, porque em geral quem explica não é especialista e acaba sacrificando a precisão. O resultado é que 1) informações imprecisas são copiadas e coladas pela internet inteira, e 2) leitores veem só o nível do blog, deixam de estudar mais e acabam reforçando a própria ignorância. E, além disso, eu também não gostei do layout da página. Pela minha experiência com ADHD e memória ruim, eu só consigo acompanhar bem quando o conteúdo é quebrado em um formato adequado, com subtítulos/negrito/cores de separação/bullets etc., mas esse texto pareceu só um paredão de texto. Quanto mais tempo levo para captar o ponto principal, mais perco o foco. A explicação de Big O na Simple Wikipedia é muito mais direta. Já a página normal da Wikipédia introduz matemática de repente, e ao vê-la fica claro que Big O é um tema bem mais complexo do que parece, o que me levou à conclusão de que “talvez simplificar demais também não seja bom”
- O segundo link não é sobre Big-O, e não há por que imitar esse tipo de atitude
- O Ned me mandou um e-mail há alguns dias, e fico feliz em também contribuir para esse tipo de discussão
- Quando vejo textos assim, a verdadeira lição para mim é que “se houver explicações erradas ou enganosas, isso não significa que se deve parar de corrigi-las; o problema é que alguns ‘especialistas’ na internet só querem vencer a discussão”. Pela postura do Pyon, ele pareceu bem agressivo, quase como um troll de internet. A conclusão nunca deve ser “então detalhes técnicos não importam e tudo bem ser impreciso”
O(1) na prática usa uma função de hash, o que não é simples, mas ainda assim envolve um custo constante de operação. Se os dados forem muito pequenos, até um algoritmo péssimo como O(n^2) pode ser mais rápido em tempo real
- É verdade, mas também não convém enfatizar isso demais. No trabalho real, já é difícil fazer as pessoas entenderem que n^2 pode travar o computador. Além disso, dependendo do caso, também dá para usar uma função de hash perfeita, como mod
Tenho a impressão de que a importância moderna de Big-O não é a mesma de antes. O hardware atual tem multithreading, pipeline, NUMA, caches complexos e afins, então há operações que terminam em menos de um ciclo e outras que podem levar centenas ou milhares de ciclos. Se você tentar explicar algoritmos só pelo número de iterações no innermost loop, acaba distorcendo a realidade. E, ao falar de Big-O, também é obrigatório mencionar outras notações, como Big-Omega. (Aliás, também gostei da animação sobre Big-O)
- A teoria de Big-O surgiu justamente para definir a quantidade de trabalho independentemente desses fatores dependentes da máquina. Nesse sentido, é uma ferramenta que não envelhece. (Um bom apresentador geralmente também faz questão de mencionar que “constantes como C se tornam muito importantes quando N é pequeno”)
O realmente interessante é que, em computação quântica, certas operações crescem como O(n^7) em relação ao número de átomos, mas os cientistas não têm medo de executar esse cálculo na prática. Isso porque N é pequeno o bastante, computadores e memória continuam ficando mais rápidos, e o valor do resultado é enorme. (Não sou especialista em ciência da computação, então perdoem se usei a notação O() de forma errada)
- Pode simplesmente dizer “cresce proporcionalmente a n^7”. Quando se diz O(n^7), a maioria entende, mas matematicamente O representa só um limite superior, então isso não é rigorosamente preciso. Se quiser ser realmente exato, o correto seria algo como Ω(n^7)
Gostei muito da visualização. Mesmo tendo estudado algoritmos no passado, continuar vendo isso de forma visual ainda ajuda bastante
Talvez por eu ter cursado engenharia elétrica, sempre senti que Big O Notation era tratado como um conceito meio passado por cima. Sempre era algo apresentado como se fosse óbvio, então acho que nunca vi uma explicação realmente gentil e detalhada. Fico curioso sobre em que nível de matemática ou computação esse conceito costuma ser introduzido pela primeira vez
- Foi na disciplina de Matemática Discreta do curso de computação que aprendi Big-O da forma mais sistemática
- Na minha faculdade, Big-O e vários métodos de prova eram ensinados em Análise de Algoritmos (disciplina obrigatória). Mas essa matéria era quase sempre do 3º ou 4º ano, e na prática havia a expectativa implícita de que você já tivesse absorvido parte do conceito por volta do 1º ano (provavelmente por aprender isso naturalmente ao redor)
- Em termos matemáticos, dizer que uma função f(x) é O(g(x)) significa que f(x)/g(x) satisfaz “para todo x, f(x)/g(x) < C” para alguma constante C. Em computação, f(x) muitas vezes representa a complexidade, como o número de operações de um certo algoritmo
- O desenho da Big-O Notation permite várias interpretações. Por exemplo, se você definir um algoritmo pelo número de passos de uma máquina de Turing, não pode existir algoritmo em tempo log, e O(log n) passa a ser tratado como O(1)
- Aprendi isso numa disciplina obrigatória do 1º ano de computação. Não tem nada demais: é apenas uma forma de descrever como a quantidade de operações cresce quando a entrada aumenta. Parece difícil por fora, mas na prática é muito simples e clara
A visualização dinâmica ajudou demais a entender. Espero que façam mais lições e materiais assim
- Fico muito grato e feliz com essa reação
Toda vez que aparece uma thread sobre Big-O Notation, eu sempre espero que alguém explique como esse conceito se conecta ao anime The Big O. Até hoje eu não entendo muito bem sobre o que aquele anime é
- (vira 4 latas de cerveja)Certo, escuta só. Aquele anime é como se misturassem Pacific Rim, Dark City e The Matrix, nessa ordem
Pessoalmente, acho que a forma mais eficaz de entender Big O Notation é conectá-la com analogias do cotidiano
Acho que é um material bonito. Enviei um sinal e espero que tenha chegado bem; fiquei com aquela sensação de ter ganhado uma colherada de dopamina à toa
- Chegou certinho. Obrigado