Considere a seguinte figura.A figura mostra a operação de or...
A figura mostra a operação de ordenação sobre um arranjo de entrada de 10 números, feita pelo algoritmo bucket sort, que tem como característica
Comentários
Veja os comentários dos nossos alunos
https://pt.wikipedia.org/wiki/Bucket_sort
Gabarito letra B
O Bucket sort divide um vetor em um número finito de "baldes". Cada "balde" é então ordenado individualmente, seja usando um algoritmo de ordenação diferente, ou usando o algoritmo bucket sort recursivamente.
O Bucket Sort tem complexidade linear O(n) quando o vetor a ser ordenado contém valores que são uniformemente distribuídos
complexidade pior caso O(n^2)
Creio que o erro da letra D seja dizer que colocando, em cada recipiente, um algoritmo recursivamente diferente confundindo o próprio bucket sort recursivamente com outros algoritmos de ordenação.
Fonte: Cormen, Thomas; Leiserson, Charles; Rivest, Ronald; Stein, Clifford (2012). Algoritmos: teoria e prática. Rio de Janeiro: Elsevier. pp. 145–146–147.
instagram: @papirobizurado
Força Guerreiro!!!!!!
[GABARITO: LETRA B]
A figura fornecida mostra a operação de ordenação pelo algoritmo Bucket Sort. Baseado na explicação do Bucket Sort e analisando as alternativas, a alternativa correta é:
B. funcionar em tempo linear, quando a entrada é gerada a partir de uma distribuição uniforme.
O Bucket Sort é eficiente para dados distribuídos uniformemente. Nesses casos, ele pode alcançar uma complexidade de tempo média de O(n), onde n é o número de elementos. A eficiência do Bucket Sort se dá pelo fato de que, quando os elementos são distribuídos uniformemente, cada balde terá aproximadamente o mesmo número de elementos, resultando em um desempenho linear na média.
Clique para visualizar este comentário
Visualize os comentários desta questão clicando no botão abaixo