Avalie as afirmativas abaixo: 1 - O merge sort executa em O(n log n). 2 - O bucket sort executa em O(n). 3 - Algoritmos que executam em uma complexidade abaixo de O(n log n) ordenam a sequência sem comparar os elementos desta sequência.
Soluções para a tarefa
Resposta:
Todas estão corretas
Explicação:
respondi na estacio
Resposta:
Todas estão corretas
Explicação:
Para o merge sort sempre se executa em ordem O (n long n), ou seja em todos os casos, pois sua eficiência não depende do tamanho do tamanho inicial do array e nem da ordem inicial dos elementos, o que representa a preocupação nesse algoritmo é o uso a mais de memória.
O bucket sort executa em O(n) ,ou seja, complexidade linear para casos onde o vetor a ser ordenado contém valores que são uniformemente distribuídos.
Quanto a última afirmativa, achei a resposta nesse material, https://joaoarthurbm.github.io/eda/posts/merge-sort/, que diz o seguinte:
"Merge Sort é um algoritmo eficiente de ordenação por divisão e conquista. Se nossa missão é ordenar um array comparando seus elementos, do ponto de vista assintótico, n∗logn é o nosso limite inferior. Ou seja, nenhum algoritmo de ordenação por comparação é mais veloz do que n∗logn. Formalmente, todos são Ω(n∗logn)."
Logo, algoritmos que tem ordem inferior a isso não podem ser de comparação, e ordenam sem comprar os elementos desta sequência.