Algoritmos, estruturas e raciocínio de complexidade
Você já sabe escrever uma função pequena. Agora precisa escolher como organizar os dados para que ela continue útil quando a entrada cresce. Um atendimento tem catálogo de produtos, consultas por identificador e etapas ligadas por dependências. Lista, índice e grafo respondem a perguntas diferentes. A escolha de estrutura deve nascer da operação necessária, não do desejo de usar uma palavra técnica.
Esta unidade introduz busca, tabelas hash, grafos e BFS por um caso controlável à mão. O laboratório combina essas peças, mede comparações e testa colisões e ciclos. A preparação oferece vocabulário para analisar custos e correção dos exemplos de IA, inclusive retrieval e orquestração. Ela não cobre todo o campo de algoritmos nem transforma uma demonstração pequena em garantia de desempenho de um serviço real.
ProgramaçãoAo terminar esta aula
- Declare hipóteses antes de escolher um algoritmo.
- Complexidade descreve crescimento, não latência medida.
- Separar descoberta e processamento evita ciclos infinitos.
Antes de continuar: Laboratório: Programação JavaScript, contratos e debugging
Crescimento, operações e hipóteses
FundamentosImagine um catálogo com n produtos. Uma busca sequencial compara o SKU desejado com cada registro até encontrar ou terminar. No pior caso, faz n comparações. Dobrar a entrada pode dobrar esse trabalho. O(n) descreve a ordem de crescimento num modelo de custo; não informa que a execução levou um número específico de milissegundos. A mesma ideia vale para memória: guardar n registros requer espaço que cresce com n, mesmo que os bytes exatos dependam da representação.
↗ Open Data Structures: Correctness, Time Complexity, and Space Complexity
Se cada etapa divide por dois o conjunto de candidatos, o número de etapas cresce aproximadamente com log2(n), expresso como O(log n). Isso explica a busca binária, mas somente depois de declarar a ordenação e o custo de acesso ao meio. Uma tabela hash pode oferecer acesso esperado constante sob distribuição e manutenção apropriadas; no pior caso de colisão, a lista de um bucket cresce. Diferencie garantia de pior caso, expectativa e amortização de redimensionamentos. A tabela de dois buckets do laboratório deliberadamente não oferece a expectativa de uma estrutura bem dimensionada.
↗ Open Data Structures: Correctness, Time Complexity, and Space Complexity
Busca binária depende de uma invariante
FundamentosUma lista ordenada permite uma pergunta mais forte: o valor está antes ou depois do meio? Se a posição intermediária contém 40 e procuramos 70, todos os valores anteriores ou iguais a 40 podem ser descartados. A cada comparação, o intervalo de candidatos diminui. O algoritmo conserva a afirmação de que, se o alvo existe, está dentro do intervalo ainda ativo. Quando o intervalo fica vazio, a ausência está provada sob a hipótese de ordenação. Sem essa hipótese, o descarte pode eliminar o valor procurado.
Na implementação inclusiva, lo e hi apontam aos extremos válidos. O índice m é a parte inteira do meio. Se a[m] é menor que x, o próximo intervalo começa em m+1; usar m novamente pode impedir o progresso quando restam dois candidatos. A condição lo<=hi garante que um último candidato ainda seja comparado. Lista vazia, primeiro elemento, último elemento e valor entre dois elementos são casos diferentes. Um teste somente com o elemento central esconde os erros de atualização dos extremos.
Ordenar um catálogo inteiro para uma única busca pode custar mais do que percorrê-lo. A decisão depende de quantas consultas ocorrerão, quantas atualizações mudarão a ordem e se existe um índice mantido por outro componente. Um índice tem custo de construção e manutenção; ele não elimina trabalho, apenas muda onde e quando o trabalho acontece. Essa pergunta reaparece em bancos e bases vetoriais: qual custo estamos amortizando, sob qual carga e com qual requisito de resultado?
Hash escolhe um local; igualdade escolhe o registro
FundamentosUma tabela hash transforma a chave numa posição de armazenamento. Como há mais chaves possíveis do que posições, chaves diferentes podem colidir. Uma estratégia é manter uma coleção em cada bucket e comparar as chaves dentro dela. O hash orienta a procura, mas não prova identidade. Se AA e BB caem no mesmo bucket, sobrescrever o primeiro somente por compartilharem posição perde informação. O laboratório força essa colisão para que a responsabilidade da comparação fique visível.
Grafos e BFS tornam relações percorríveis
FundamentosUm grafo representa vértices e arestas. No fluxo de atendimento, A é entrada, B é consulta de compra, C é triagem e D é conclusão. A lista de adjacência informa quais etapas podem ser alcançadas a partir de cada vértice. Se B liga de volta a A, existe um ciclo; um percurso que visita novamente cada vizinho sem memória pode não terminar. A definição de direção importa: permitir A→B não implica permitir B→A. O grafo expressa relações escolhidas, não deduções automáticas do programa.
BFS usa uma fila para processar primeiro os vértices descobertos mais cedo. Ao descobrir um vizinho novo, marca sua presença e registra o pai antes de enfileirar. Assim, um ciclo não volta a inserir o início e cada descoberta conserva um caminho conhecido. A primeira camada fica a uma aresta do início, a segunda a duas, e assim por diante. Como a fila esgota uma camada antes de avançar, a primeira descoberta de um destino não pode ignorar um caminho com menos arestas. Isso justifica a propriedade de menor caminho no caso sem pesos; não prova menor duração quando as arestas possuem custos distintos.
Com listas de adjacência, o percurso visita cada vértice alcançado uma vez e examina suas arestas de saída. O custo típico é O(V+E), sob operações apropriadas de fila e marcação. O mapa de pais e a fila consomem memória proporcional aos vértices descobertos. Uma matriz de adjacência muda a forma de enumerar vizinhos e pode exigir examinar uma linha inteira por vértice. Antes de escolher a representação, pergunte se o grafo é esparso, quais consultas ocorrerão e se existe necessidade de testar uma aresta individual frequentemente.
Exercício aplicado
Um serviço procura um SKU em uma lista ordenada e calcula a rota entre etapas de atendimento. O grafo contém um ciclo e duas rotas de mesmo tamanho. Proponha busca e percurso que terminem, sem confundir colisão de hash com igualdade de chave.
- Faça uma busca manual no intervalo e anote o conjunto de candidatos que permanece.
- Percorra o grafo A→B/C, B→A/D, C→D; registre fila e pais.
- Teste chave colidente, nó isolado e início igual ao destino.
- Explique complexidade, memória auxiliar e condição de validade de cada algoritmo.
Abrir resolução comentada
Busca binária descarta metade dos candidatos porque a ordenação justifica o descarte. BFS usa fila e marca descoberta antes de inserir; por isso A não retorna indefinidamente pelo ciclo B→A. O primeiro pai encontrado reconstrói uma rota mínima em quantidade de arestas, não em preço ou duração.
A tabela possui só dois buckets para forçar colisões. AA e BB caem no mesmo bucket, mas a comparação de chave mantém valores distintos. Essa implementação didática pode custar tempo linear; não é um benchmark nem reprodução interna de Map. A contagem de comparações da busca é uma medida do algoritmo neste caso.
const assert=require('node:assert/strict');
function buscaBinaria(a,x){let lo=0,hi=a.length-1,comparacoes=0;
while(lo<=hi){const m=Math.floor((lo+hi)/2);comparacoes++;if(a[m]===x)return {indice:m,comparacoes};if(a[m]<x)lo=m+1;else hi=m-1;}
return {indice:-1,comparacoes};}
// Tabela didatica com colisao proposital: o bucket nao e identidade.
class Tabela {constructor(){this.buckets=[[],[]];} hash(k){return k.length%2;}
set(k,v){const b=this.buckets[this.hash(k)],p=b.find(x=>x[0]===k);if(p)p[1]=v;else b.push([k,v]);}
get(k){return this.buckets[this.hash(k)].find(x=>x[0]===k)?.[1];}}
function bfs(g,inicio,fim){
if(!g.has(inicio)||!g.has(fim))throw new Error('vertice ausente');
for(const vizinhos of g.values())for(const v of vizinhos)if(!g.has(v))throw new Error('aresta invalida');
const fila=[inicio],pais=new Map([[inicio,null]]);let head=0;
while(head<fila.length){const u=fila[head++];if(u===fim)break;
for(const v of g.get(u))if(!pais.has(v)){pais.set(v,u);fila.push(v);}}
if(!pais.has(fim))return null;
const caminho=[];for(let v=fim;v!==null;v=pais.get(v))caminho.push(v);
return caminho.reverse();}
const numeros=Array.from({length:1024},(_,i)=>i*2);
assert.equal(buscaBinaria(numeros,1024).indice,512);
assert.equal(buscaBinaria(numeros,3).indice,-1);
assert(buscaBinaria(numeros,2046).comparacoes<=11);
const t=new Tabela();t.set('AA',1);t.set('BB',2);t.set('AA',3);
assert.equal(t.get('AA'),3);assert.equal(t.get('BB'),2);assert.equal(t.get('CC'),undefined);
const g=new Map([['A',['B','C']],['B',['A','D']],['C',['D']],['D',[]],['Z',[]]]);
assert.deepEqual(bfs(g,'A','D'),['A','B','D']);
assert.deepEqual(bfs(g,'A','A'),['A']);assert.equal(bfs(g,'A','Z'),null);
assert.throws(()=>bfs(new Map([['A',['X']],['B',[]]]),'A','B'),/aresta/);
console.log('busca, colisoes, ciclos e menor numero de arestas verificados');Como conferir seu resultado
- A ordenação é pré-condição declarada da busca.
- Chaves colidentes conservam valores independentes.
- Cada vértice entra na fila no máximo uma vez.
- Caminho ausente retorna null; vértice ausente é erro de contrato.
Teste sua compreensão
Responda com suas palavras antes de abrir o comentário. Saber explicar uma decisão é parte do domínio.
1. BFS encontra a rota de menor custo monetário?
Não; no caso sem pesos, minimiza o número de arestas.
Custos distintos exigem um algoritmo e contrato adequados aos pesos.
2. Duas chaves com o mesmo hash são iguais?
Não. O bucket ainda precisa comparar as chaves.
Colisões são possíveis e precisam de tratamento.
3. Por que busca binária numa lista desordenada é incorreta?
Porque o descarte de metade deixa de ser justificado.
O alvo pode estar na parte descartada apesar da comparação com o meio.
Seu progresso fica salvo neste navegador. Concluir a leitura não substitui demonstrar o domínio nos exercícios.
Referências e aprofundamento
Documentação oficial e trabalhos originais. As referências registram o escopo e as limitações para você conferir o que sustentam.
- Open Data Structures: Correctness, Time Complexity, and Space Complexity
Pat Morin / Open Data Structures • consulta: 2026-10-06
FundamentosCorreção e ordem de crescimento de tempo e memória.
Limites: Modelo de custo assintótico não fornece latência observada.
- Open Data Structures: ChainedHashTable
Pat Morin / Open Data Structures • consulta: 2026-10-06
FundamentosHashing com encadeamento e tratamento de colisão.
Limites: Tabela didática local não representa implementação interna de Map.
- Open Data Structures: Graphs
Pat Morin / Open Data Structures • consulta: 2026-10-06
FundamentosVértices, arestas, caminhos, ciclos e representações.
Limites: Modelagem depende da direção e significado das relações.
- Open Data Structures: Graph Traversal
Pat Morin / Open Data Structures • consulta: 2026-10-06
FundamentosPercurso em largura, fila e descoberta de vértices.
Limites: BFS sem pesos minimiza arestas, não custos arbitrarios.