Em uma atividade de organização de dados, duas listas já estão ordenadas em ordem crescente. O algoritmo de…
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
Em uma atividade de organização de dados, duas listas já estão ordenadas em ordem crescente. O algoritmo de merge compara os primeiros elementos ainda não utilizados de cada lista, transfere o menor para uma nova lista e repete esse procedimento até que uma das listas termine. Em seguida, os elementos restantes da outra lista são transferidos diretamente. Considere duas listas de tamanhos m e n, sem assumir que esses tamanhos sejam iguais. Com base no funcionamento descrito, qual é a complexidade temporal assintótica do algoritmo de merge, expressa em função de m e n, no pior caso?
- A) Θ(m + n), pois cada elemento das duas listas é processado no máximo uma vez.
- B) Θ(n), pois a lista resultante é formada a partir da segunda lista ordenada.
- C) Θ(m · n), pois cada elemento de uma lista é comparado com todos os da outra.
- D) Θ(m), pois basta percorrer integralmente a primeira lista ordenada.
- E) Θ(log(m + n)), pois o algoritmo reduz o problema a cada comparação.
✅ Resposta correta: alternativa A
Resolução passo a passo
- Entenda o procedimento descrito. Em cada iteração, o algoritmo compara os primeiros elementos ainda não usados das duas listas, transfere o menor para a lista resultante e avança apenas no ponteiro da lista de onde o elemento saiu.
- Conte quantas operações ocorrem. Cada iteração transfere exatamente um elemento para a nova lista e, portanto, cada elemento de cada lista é transferido no máximo uma vez. Como a lista resultante tem m + n elementos, há no máximo m + n iterações de comparação e transferência.
- Analise a cauda. Quando uma lista termina, os elementos restantes da outra são copiados diretamente, o que custa um tempo proporcional ao número de elementos restantes, sem novas comparações. Assim, o trabalho total continua limitado pela soma m + n.
- Conclua no pior caso. Como o número de operações cresce linearmente com m + n e também é necessário pelo menos percorrer todos os elementos para produzir a saída completa, a complexidade é Θ(m + n). A alternativa A está correta.
- Por que as outras estão erradas. B está errada porque ignora a primeira lista, cujos elementos também precisam ser processados. C está errada porque o merge não compara cada elemento com todos os da outra lista; ele avança de forma sequencial. D está errada porque percorrer apenas a primeira lista deixa de considerar a segunda, que também contribui para o trabalho. E está errada porque log(m + n) seria típico de busca binária, e o merge precisa tocar em cada elemento ao menos uma vez.
💡 Dica: Considere a definição de complexidade temporal do algoritmo.
Alternativa por alternativa
A cada comparação, pelo menos um elemento é transferido para a lista resultante. Assim, os elementos das duas listas são percorridos uma única vez, incluindo os elementos restantes após o término de uma delas. O número total de operações é proporcional a m + n, portanto a complexidade temporal no pior caso é Θ(m + n).
Acredita que o custo depende apenas de uma das listas, como se a lista resultante fosse copiada inteira da segunda sem considerar a primeira.
Por que engana: Confundir a complexidade do algoritmo de merge com a de outros algoritmos, como o de multiplicação de matrizes, levando a uma resposta incorreta.
Imagina que o merge compara todos os pares de elementos entre as duas listas, como em um produto cartesiano, confundindo com algoritmos de comparação par a par.
Supõe que, como a primeira lista é percorrida, a segunda é ignorada, esquecendo que os elementos de ambas precisam ser transferidos para a saída.
Associa o procedimento a estratégias de divisão pela metade, como busca binária ou divisão e conquista logarítmica, sem perceber que o merge processa todos os elementos.
Raio-X da questão
complexidade temporal
avaliacao
análise de algoritmos · notação Big O
Revisar algoritmos de ordenação e suas complexidades.
Confundir a complexidade do algoritmo de merge com a de outros algoritmos, como o de multiplicação de matrizes, levando a uma resposta incorreta.
ciencia_tecnologia
pensamento_critico
abstrato
Questões parecidas com resolução
- Qual é a complexidade assintótica de mesclar k listas ordenadas que juntas contêm n elementos, usando um min-heap (heap…
- Considere um algoritmo que para cada um dos N elementos de um vetor executa, no pior caso, uma busca linear sobre M…
- Um algoritmo aninhado percorre uma matriz M de tamanho n×n com dois loops: para i de 1 até n e para j de 1 até n. Se a…
- Um algoritmo percorre uma lista de n elementos com dois loops aninhados: para i de 1 a n: para j de 1 a n: executar…
- Qual é a complexidade temporal do algoritmo Bubble Sort no pior caso?
- Considere um algoritmo com duas estruturas de repetição aninhadas, cada uma iterando de 1 até n. Qual é a complexidade…
🔎 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