Considere a seguinte figura.A figura mostra a operação de or...

Próximas questões
Com base no mesmo assunto
Q378280 Algoritmos e Estrutura de Dados
Considere a seguinte figura.

Imagem associada para resolução da questão

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
Alternativas

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