Algoritmos, estruturas e raciocínio de complexidade
Crie estruturas.cjs para resolver três problemas do atendimento: localizar número em catálogo ordenado, guardar registros por chave e encontrar uma rota no grafo. Use Node.js 24 e dados pequenos no início. A entrega precisa conter um trace manual de BFS, testes de colisão e uma análise de custo. A solução está disponível depois do exercício; tente explicar os passos antes de copiá-la.
Não faremos benchmark de infraestrutura. Uma contagem de comparações serve para conferir um raciocínio sobre crescimento, enquanto colisões e ciclos servem para conferir correção. Você poderá mudar o tamanho da entrada depois, mas não deve atribuir um tempo de execução ao algoritmo sem definir máquina, dados e procedimento. O resultado principal é saber por que ele termina e qual resposta está autorizado a produzir.
ProgramaçãoAo terminar esta aula
- Trace manual revela atualização errada de estado.
- Colisões devem preservar a chave original.
- Teste ausência, ciclo e limites além do caso encontrado.
Antes de continuar: Leitura: Algoritmos, estruturas e raciocínio de complexidade
Trace a busca e teste os extremos
AvaliaçãoComece com [0,2,4,6,8,10,12,14]. Procure 14 e anote lo, hi e m em cada iteração. Depois procure 3. Para o primeiro caso, o intervalo deve terminar no último elemento; para o segundo, deve ficar vazio sem encontrar igualdade. Registre a redução do número de candidatos. Se algum passo conserva exatamente o mesmo intervalo depois de uma desigualdade, você encontrou risco de laço infinito.
Execute a busca em 1024 valores pares e observe o campo comparacoes. O teste do último valor permite até onze comparações nesta implementação. Esse limite veio do tamanho e da redução do intervalo, não de uma promessa de performance do Node. Acrescente testes de array vazio e primeiro elemento. Se sua função recebe uma lista desordenada, ela deveria recusar ou declarar a pré-condição; verificar ordenação em cada consulta também custa uma passagem pela lista.
Construa um índice que não perca identidade
FundamentosA Tabela didática usa comprimento da chave módulo dois. Esse hash é ruim para desempenho, mas excelente para provocar colisão de maneira previsível: AA e BB vão ao mesmo bucket. Insira os dois valores, atualize AA e leia BB de novo. Se BB desaparecer ou assumir o valor de AA, o algoritmo tratou posição como identidade. A solução conserva pares chave/valor e procura a chave exata antes de atualizar.
Agora procure CC, que compartilha o bucket mas não foi inserida. O retorno undefined indica ausência neste contrato; não significa valor zero. Se o domínio precisasse armazenar undefined como dado válido, seria necessário um método has ou um resultado que distinguisse presença de valor. Essa pequena decisão de interface evita um bug comum no uso de caches: ausência e resultado vazio legítimo são estados diferentes. Descreva a pior colisão possível e por que esta tabela pode degenerar numa busca linear.
Descubra antes de enfileirar
FundamentosDesenhe o grafo com A ligado a B e C, B ligado a A e D, C ligado a D, D sem saída e Z isolado. Inicie a fila com A e o mapa de pais com A→null. Retire A, descubra B e C, atribua seus pais e coloque-os na fila. Ao retirar B, ignore A porque já foi descoberto; descubra D. Quando C encontra D, o pai já existe. Essa ordem conserva a primeira descoberta e impede duplicação.
A solução usa um índice head em vez de remover repetidamente o primeiro item do array. O contrato da fila é retirar na mesma ordem em que inseriu; o índice implementa essa ordem sem depender do custo de deslocar elementos. Cada vértice descoberto entra uma vez. Cada lista de vizinhos é percorrida quando seu vértice é processado. Sob lista de adjacência e operações de mapa adequadas, esse raciocínio leva a trabalho proporcional aos vértices e arestas alcançados, além da validação inicial do grafo.
Reconstrua a rota e exponha os limites
FundamentosDepois da descoberta de D, siga pais de D até A e inverta a sequência. A rota A,B,D tem duas arestas; A,C,D também teria duas, mas o algoritmo escolhe a primeira conforme a ordem dos vizinhos. O teste de um caminho exato, portanto, é válido para a ordem fixa deste exemplo. Uma aplicação que aceite qualquer rota mínima deveria testar validade das arestas e tamanho, evitando rejeitar uma alternativa igualmente correta.
Teste A→A, A→Z e uma aresta para X que não aparece no conjunto de vértices. São respectivamente rota de comprimento zero, destino inalcançável e entrada inválida. Não converta os três em lista vazia. Entregue o trace, o significado de null e uma nota sobre rotas com pesos: BFS não minimiza duração quando cada aresta possui tempo diferente. A rubrica exige progresso da busca, manutenção das chaves colidentes, término no ciclo e explicação do critério de menor rota; passar apenas o caminho nominal não basta.
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. Quando um vértice deve ser marcado como descoberto?
Antes de entrar na fila.
Assim outra aresta não enfileira o mesmo vértice novamente.
2. Por que procurar CC testa mais que procurar AA?
Porque separa presença de colisão.
Uma chave não cadastrada não pode receber o valor de outra que compartilha bucket.
3. O caminho A→A deve ser null?
Não; contém somente A.
Existe uma rota de zero arestas, diferente de destino inalcançável.
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.