Complexidade de algoritmo sem matemática pesada

Complexidade descreve como a quantidade de trabalho cresce quando a entrada aumenta. Em vez de decorar letras, conte comparações e voltas para 10, 1.000 e 1.000.000 de itens; o padrão aparece antes da fórmula.

O domínio é buscar um nome numa lista de participantes. Primeiro contamos passos independentemente da máquina. Depois medimos a mesma tarefa no Node v26.3.0 e tratamos tempo como observação local, não promessa universal.

A pergunta certa é quantos passos crescem

Uma busca linear visita itens até encontrar. No pior caso, o alvo está no fim:

function buscar(lista, alvo) {
  let passos = 0;
  for (const item of lista) {
    passos += 1;
    if (item === alvo) return { achou: true, passos };
  }
  return { achou: false, passos };
}

console.log(buscar(['Ana', 'Bia', 'Caio', 'Davi'], 'Davi'));

Pense numa fila sem índice alfabético: para achar a última pessoa, você pergunta uma por uma. O limite é que computadores têm caches, otimizações e representações que tornam “um passo” uma abstração. A contagem explica crescimento, não nanosegundos.

Conte antes de medir

Se a lista cresce cem vezes, o pior caso da busca linear também cresce cem vezes:

for (const tamanho of [10, 1_000, 1_000_000]) {
  let passos = 0;
  for (let i = 0; i < tamanho; i += 1) passos += 1;
  console.log(tamanho, passos);
}

Isso é crescimento linear, escrito O(n). A letra n representa tamanho da entrada. Constantes importam em medição, mas são omitidas ao descrever a forma de crescimento.

Laço aninhado multiplica as voltas

Comparar todos com todos executa n × n pares:

for (const tamanho of [10, 100, 1_000]) {
  let pares = 0;
  for (let a = 0; a < tamanho; a += 1) {
    for (let b = 0; b < tamanho; b += 1) pares += 1;
  }
  console.log(tamanho, pares);
}

Multiplicar entrada por dez multiplica trabalho por cem. É O(n²). Em tamanho pequeno, milhão ainda pode caber; em um milhão de itens, o quadrado é um trilhão de pares. A curva vira parede.

Nem todo laço dentro de laço é quadrático. Se o interno percorre sempre três colunas, o trabalho é 3n, portanto linear. Conte limites, não formatos visuais.

Cortar uma lista ordenada ao meio

Busca binária compara o meio e descarta metade. Este exemplo conta as decisões:

function buscaBinaria(lista, alvo) {
  let inicio = 0;
  let fim = lista.length - 1;
  let passos = 0;
  while (inicio <= fim) {
    passos += 1;
    const meio = Math.floor((inicio + fim) / 2);
    if (lista[meio] === alvo) return passos;
    if (lista[meio] < alvo) inicio = meio + 1;
    else fim = meio - 1;
  }
  return passos;
}

const lista = Array.from({ length: 1_000_000 }, (_, i) => i);
console.log(buscaBinaria(lista, 999_999));

Vinte comparações alcançam o fim de um milhão de números ordenados. A condição é importante: manter a lista ordenada custa trabalho. Se os dados mudam sempre, esse custo pode superar a economia de uma única busca.

Lista contra Set na mesma execução

Para medir sem inventar, foram usadas sete rodadas; mostramos a mediana do tempo por consulta. O alvo é o último item, Array.includes faz pior caso, e a construção do Set fica fora da região medida. Um selo consome os resultados para evitar uma chamada sem uso:

import { performance } from 'node:perf_hooks';
let selo = 0;
function medir(fn, repeticoes) {
  const amostras = [];
  for (let rodada = 0; rodada < 7; rodada += 1) {
    let resultado = 0;
    const inicio = performance.now();
    for (let i = 0; i < repeticoes; i += 1) resultado += fn() ? 1 : 0;
    amostras.push((performance.now() - inicio) / repeticoes);
    selo += resultado;
  }
  amostras.sort((a, b) => a - b);
  return amostras[3];
}

for (const tamanho of [1_000, 100_000, 1_000_000]) {
  const lista = Array.from({ length: tamanho }, (_, i) => `pessoa-${i}`);
  const conjunto = new Set(lista);
  const alvo = `pessoa-${tamanho - 1}`;
  const repeticoesLista = tamanho === 1_000 ? 1_000 : tamanho === 100_000 ? 100 : 10;
  const linear = medir(() => lista.includes(alvo), repeticoesLista);
  const porSet = medir(() => conjunto.has(alvo), 100_000);
  console.log(`${tamanho}: linear=${linear.toFixed(6)}ms set=${porSet.toFixed(6)}ms passos=${tamanho}`);
}
console.log(`selo=${selo}`);

Esses números pertencem a esta execução. Operações muito curtas ficam especialmente sensíveis a otimização e resolução do relógio. A evidência mais confiável é a tendência da busca linear; a consulta ao Set permanece aproximadamente constante depois que a estrutura está pronta.

Construir o índice também custa

Uma consulta não justifica converter toda lista. Conte o trabalho conceitual:

function custoEstimado(tamanho, consultas) {
  const lista = tamanho * consultas;
  const set = tamanho + consultas;
  return { lista, set };
}

console.log('uma consulta', custoEstimado(1000, 1));
console.log('cem consultas', custoEstimado(1000, 100));

É um modelo de passos, não benchmark. Para uma consulta, os custos são próximos e Array já existe. Para cem consultas, pagar a construção uma vez pode compensar.

Trocar memória por tempo

Um mapa de presença guarda uma chave por nome e responde sem percorrer a lista:

const participantes = ['Ana', 'Bia', 'Caio'];
const porNome = new Map(participantes.map((nome, indice) => [nome, indice]));

console.log(porNome.get('Caio'));
console.log(porNome.has('Dora'));

Uma terceira estratégia é ordenar uma cópia e usar busca binária. Ela paga ordenação antes das consultas e mantém menos estrutura adicional que um mapa, mas precisa decidir o que fazer com duplicatas e índices originais. Conte o custo total do fluxo, não apenas a operação favorita:

function compararPlanos(tamanho, consultas) {
  const linear = tamanho * consultas;
  const ordenarEBuscar = Math.ceil(tamanho * Math.log2(tamanho)) + Math.ceil(consultas * Math.log2(tamanho));
  const construirSet = tamanho + consultas;
  return { linear, ordenarEBuscar, construirSet };
}

console.log(compararPlanos(1024, 1));
console.log(compararPlanos(1024, 1000));

O modelo simplifica constantes e implementação, mas força uma decisão importante: uma consulta não paga a preparação; mil consultas podem pagar. Depois meça com os dados reais.

Benchmark precisa registrar runtime, entrada, aquecimento, repetições e estatística escolhida. Uma única duração inclui ruído do sistema. Mediana reduz picos, mas não corrige cenário artificial. O alvo no fim representa pior caso da busca linear; alvo no começo produziria outra distribuição.

Observe memória junto com tempo. Set duplica referências e estrutura de índice. Em serviço com limite apertado, consulta mais rápida pode aumentar coleta de lixo ou exceder memória. Complexidade é conversa de recursos, não ranking de métodos.

Repita medições em processo novo e descarte conclusões baseadas numa diferença menor que o ruído observado. Publique entradas e código junto do número, como fizemos aqui. Sem cenário reproduzível, “mais rápido” é uma opinião com casas decimais.

O ganho de busca compra memória extra e manutenção do índice. Se a lista muda, o mapa precisa mudar junto. Estrutura mais rápida com dado desatualizado é pior que busca lenta correta.

Quando não otimizar

Se a entrada máxima tem vinte itens e a operação acontece uma vez, clareza domina. Primeiro meça uma situação real, identifique o trecho responsável e preserve testes. “O(n²)” não significa automaticamente lento; significa que o risco cresce rápido com n.

Sua missão é implementar busca linear e binária para 128 números ordenados. Conte passos para primeiro, meio, último e ausente. O critério é a binária nunca ultrapassar oito comparações. Depois pratique nos exercícios de lógica, relacione com vetores e matrizes, revise recursividade e consulte o guia.