O algoritmo de Ordenação por Mesclagem divide recursivamente a lista em porções cada vez menores e, quando não é mais possível dividir, o algoritmo passa a mesclar ordenadamente as porções menores em porções cada vez maiores. Analise as seguintes proposições sobre este algoritmo de ordenação e assinale a alternativa correta. O algoritmo de Ordenação por Mesclagem realiza o mesmo número de comparações, independentemente de os valores da lista estarem aleatoriamente distribuídos, ordenados na ordem desejada, ordenados na ordem inversa à desejada, ou quando a lista tem poucos valores diferentes entre seus itens. O algoritmo de Ordenação por Mesclagem tem ordem de complexidade de tempo de O(n log2(n)). As asserções I e II são proposições verdadeiras, mas a II não é uma justificativa da I. A asserção I é uma proposição falsa, e a II é uma proposição verdadeira. As asserções I e II são proposições verdadeiras, e a II é uma justificativa da I. A asserção I é uma proposição verdadeira, e a II é uma proposição falsa. As asserções I e II são proposições falsas.
Soluções para a tarefa
Resposta: asserções I e II são proposições verdadeiras, mas a II não é uma justificativa da I
Explicação:
A resposta correta é a letra A, considerando a asserção I e II são verdadeiras, mas a asserção II não é justificativa da I, já que as comparações do algoritmo de ordenação por mesclagem é realizada com o mesmo número, contudo não tem relação quanto a análise da complexidade de tempo.
A ordenação por mesclagem e complexidade de tempo
A ordenação por mesclagem é um tipo de algoritmo que divide uma grande array em dois subarrays e, de modo recursivo, classifica os subarrays, de modo que o problema seja dividido em subproblemas menores e mais simples de cima para baixo até que se encontre uma solução.
Em comparação a outros tipos de algoritmos de ordenação por comparação, a ordenação por mesclagem chamada de merge sort possui uma excelente eficiência quanto a complexidade do tempo, como pode ser visto na lista comparativa abaixo:
- Merge sort: O(n log2(n))
- Quick sort: O(n2)
- Bubble sort: O(n2)
- Insertion sort: O(n2)
- Selection sort: O(n2)
Conheça sobre a complexidade de um algoritmo: https://brainly.com.br/tarefa/45277633
#SPJ2