Em um algoritmo que realiza um join entre duas matrizes de registros 'pedidos' e 'clientes' usando o campo…
Publicado por Alexandre Lombardi dos Santos, fundador do GeraProva
Identificar as principais formas de organizar e representar a informação de maneira estruturada (matrizes, registros, listas e grafos) ou não estruturada (números, palavras, valores verdade).
Fonte: Base Nacional Comum Curricular (MEC).Questão
Em um algoritmo que realiza um join entre duas matrizes de registros 'pedidos' e 'clientes' usando o campo 'cliente_id', qual estratégia reduz a complexidade média quando uma das matrizes é muito menor que a outra?
- A) Sort-merge join: ordenar ambas as matrizes antes do join.
- B) Nested loop join: para cada registro, comparar com todos na outra matriz.
- C) Merge join apenas com registros que têm o mesmo 'cliente_id'.
- D) Hash join: construir uma tabela hash da menor matriz e fazer probe com os registros da maior.
- E) Cross join: combinar todas as entradas antes de filtrar.
✅ Resposta correta: alternativa D
Resolução passo a passo
- O problema pede a estratégia de join que tem menor custo médio quando uma das matrizes é muito menor que a outra. O custo depende do número de comparações e acessos feitos entre as duas matrizes.
- Hash join (alternativa D): constrói-se uma tabela hash apenas da matriz menor, com custo proporcional ao seu tamanho. Depois, cada registro da matriz maior faz uma busca (probe) na tabela, que tem tempo médio constante. O custo médio fica próximo de n + m, e a memória necessária é só a da matriz menor. Por isso D é a resposta correta.
- Nested loop join (B) compara cada registro com todos os da outra matriz, custando cerca de n vezes m comparações, o que não aproveita o tamanho menor.
- Sort-merge join (A) exige ordenar as duas matrizes, com custo de ordenação da ordem de n log n + m log m, e não tira vantagem da diferença de tamanho.
- Merge join filtrando apenas registros com o mesmo cliente_id (C) não é uma estratégia distinta que reduza o custo: o merge já depende de ordenação e não se beneficia de uma matriz muito menor.
- Cross join (E) gera todas as n vezes m combinações antes de filtrar, sendo a pior opção em custo.
- Conclusão: a alternativa D é a correta e coincide com o gabarito oficial.
💡 Dica: Considere a relação entre as matrizes e a estratégia de join.
Alternativa por alternativa
Acredita que ordenar ambas as matrizes reduz o custo médio do join, sem perceber que a ordenação custa caro e não aproveita a diferença de tamanho entre as matrizes.
Imagina que comparar cada registro com todos da outra matriz é eficiente por ser simples, sem notar que o número de comparações cresce como o produto dos tamanhos.
Por que engana: Escolher o Nested loop join, acreditando que é a abordagem mais simples, sem considerar a eficiência em termos de complexidade.
Entende que restringir o merge aos registros com o mesmo cliente_id muda a complexidade, mas o merge join continua exigindo ordenação e não se beneficia de uma matriz muito menor.
Construir um hash da menor matriz permite buscas por chave em tempo médio O(1), resultando em custo médio O(n+m) e evitando ordenação; é eficiente quando a menor matriz cabe em memória.
Pensa que combinar todas as entradas antes de filtrar é uma forma direta de resolver o join, sem perceber que isso gera n vezes m combinações intermediárias.
Raio-X da questão
join entre matrizes
avaliacao
estratégias de join em bancos de dados · complexidade de algoritmos
Revisar estratégias de otimização de joins em bancos de dados.
Escolher o Nested loop join, acreditando que é a abordagem mais simples, sem considerar a eficiência em termos de complexidade.
ciencia_tecnologia
pensamento_critico
abstrato
Questões parecidas com resolução
- Dada uma matriz grande de registros 'clientes' com campo 'cpf', qual técnica reduz o tempo de busca por um CPF…
- Escreva em pseudocódigo um algoritmo que, dada uma matriz 'clientes' onde cada linha é um registro [id, nome, telefone]…
- Ao implementar um algoritmo que percorre uma matriz de registros 'dados' armazenada em memória row-major, qual ordem de…
- Descreva um algoritmo generalizado (inclua assinatura e pseudocódigo) que receba duas coleções de registros e um…
- Dada uma matriz não ordenada de registros, qual estratégia é adequada para localizar um dado específico: varredura…
- Descreva um algoritmo em pseudocódigo que receba uma matriz de registros 'clientes' (linhas = grupos, colunas =…
Todas as questões de Organização e representação da informação
🔎 Procurar outra questão
Procure no banco do GeraProva pelo tema ou por um trecho do enunciado. Cada questão já vem com resolução comentada e a análise de cada alternativa.
Professor: monte a prova com questões como esta, com gabarito e folha de respostas, em 30 segundos. Ver planos · Blog