Qual é a complexidade assintótica de mesclar k listas ordenadas que juntas contêm n elementos, usando um…
Publicado por Alexandre Lombardi dos Santos, fundador do GeraProva
Identificar o comportamento dos algoritmos no que diz respeito ao consumo de recursos como tempo de execução, espaço de memória e energia, entre outros.
Fonte: Base Nacional Comum Curricular (MEC).Questão
Qual é a complexidade assintótica de mesclar k listas ordenadas que juntas contêm n elementos, usando um min-heap (heap mínimo) para escolher o próximo elemento?
- A) O(log n) já que estamos lidando apenas com um heap.
- B) O(n) devido à simples iteração pela lista de entradas.
- C) O(k) já que cada lista apenas precisa de uma operação.
- D) O(n^2) por necessidade de comparar cada elemento entre listas.
- E) O(n log k).
✅ Resposta correta: alternativa E
Resolução passo a passo
- Ao mesclar k listas ordenadas com n elementos no total, usa-se um min-heap que armazena, em cada momento, o menor elemento ainda não consumido de cada lista, ou seja, no máximo k elementos no heap.
- Cada um dos n elementos é inserido no heap uma vez e removido uma vez. Cada inserção ou remoção custa O(log k), pois o heap tem tamanho no máximo k.
- O custo total é, portanto, n operações de O(log k), resultando em O(n log k). Essa é a complexidade clássica do algoritmo de mesclagem de k listas ordenadas.
- Por que as outras estão erradas: A) O(log n) ignora que há n elementos a processar, então não pode ser o tempo total; B) O(n) seria possível apenas sem o custo logarítmico da escolha do mínimo, e o heap exige comparações; C) O(k) não considera que todos os n elementos precisam ser movidos para a saída; D) O(n^2) descreve uma comparação exaustiva entre todos os pares, o que o heap evita.
- Conclusão: a alternativa correta é E, e o gabarito oficial está coerente com a análise.
💡 Dica: Considere o custo de retirar e inserir elementos no heap para cada um dos n elementos.
Alternativa por alternativa
Acredita que, por usar um heap, o custo depende só do tamanho do heap, esquecendo que todos os n elementos precisam ser processados.
Supõe que percorrer todos os elementos basta, ignorando o custo de encontrar o mínimo a cada passo com o heap.
Confunde o número de listas com o número de operações, imaginando que cada lista é processada uma única vez e não cada elemento.
Imagina que é preciso comparar cada elemento com todos os outros entre listas, o que é um método força bruta e não o uso do heap.
Por que engana: Confundir o número de listas com o número total de elementos, ou considerar apenas o custo de uma operação no heap em vez de repeti-lo para os n elementos.
Inicializa-se o heap com até k cabeças; cada um dos n extrações/insersões no heap custa O(log k), resultando em O(n log k).
Raio-X da questão
Mesclagem com min-heap
avaliacao
Operações e complexidade de heaps · Notação assintótica de algoritmos
Revise como o tamanho do heap determina o custo de cada operação e como esse custo se repete pelos n elementos.
Confundir o número de listas com o número total de elementos, ou considerar apenas o custo de uma operação no heap em vez de repeti-lo para os n elementos.
ciencia_tecnologia
tomada_decisao
cientifico
Questões parecidas com resolução
- Em uma atividade de organização de dados, duas listas já estão ordenadas em ordem crescente. O algoritmo de merge…
- Dadas duas listas ordenadas de números, qual algoritmo e estrutura de dados usar para produzir uma única lista ordenada…
- Um algoritmo percorre uma lista de n elementos e atualiza um dicionário/hashtable com a frequência de cada elemento em…
- Projete um algoritmo em pseudocódigo que mescle duas listas ordenadas (A e B) em uma única lista ordenada crescente…
- Uma equipe de uma biblioteca digital precisa reunir os resultados de K consultas já ordenadas. Cada consulta fornece uma…
- Uma equipe de pesquisa precisa ordenar listas grandes de números coletados em diferentes regiões do Brasil. Para…
🔎 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