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

• 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