Se f é uma função de complexidade para um algoritmo F, então, O(f) é considerada a complexidade assintótica ou o comportamento assintótico do algoritmo F. Assinale a alternativa que apresenta somente algoritmos com complexidade assintótica, quando f(n) = O(n log n):
A - Insertion sort.
B - Merge sort e bubble sort.
C - uick sort e merge sort.
D - Quick sort e insertion sort.
E - Bubble sort.
Soluções para a tarefa
Resposta: C - Quick sort e Merge Sort
Explicação:
Gabarito
Sobre a função de complexidade quando f(n) = O(n log n), a alternativa correta é a opção C: Quick sort e merge sort.
O que é a notação O(f)?
A notação O(f) é utilizada para expressar a complexidade assintótica ou o comportamento assintótico de um algoritmo, sendo f uma função de complexidade. Ela indica o limite superior do crescimento do número de operações que o algoritmo realiza em relação ao tamanho de entrada (n).
Ela é amplamente utilizada para comparar diferentes algoritmos e entender como eles se comportam em relação ao aumento do tamanho dos dados de entrada.
Quick sort x Merge sort
Quick sort e Merge sort são ambos algoritmos de ordenação baseados em comparação que possuem complexidade assintótica O(n log n), mas eles possuem diferenças em sua implementação e desempenho.
O Quick sort é um algoritmo de ordenação baseado em divisão e conquista. Ele escolhe um elemento como "pivo" e particiona os dados em dois conjuntos, um com elementos menores que o pivô e outro com elementos maiores. Esses conjuntos são então ordenados recursivamente utilizando o mesmo processo.
O Quick sort tem uma boa performance em dados aleatórios, porém pode ter desempenho ruim em caso de dados já ordenados ou com muitos elementos iguais.
Já o Merge sort é um algoritmo de ordenação baseado em divisão e combinação. Ele divide os dados em duas metades e os ordena recursivamente. Em seguida, esses conjuntos ordenados são combinados para formar o conjunto ordenado final.
O Merge sort é um algoritmo estável, o que significa que ele mantém a ordem relativa dos elementos iguais. Ele é mais lento em comparação com o quick sort mas é menos propenso a erros e é mais estável.
Saiba mais sobre algoritmos aqui: https://brainly.com.br/tarefa/25021296
#SPJ2
