Questão 769318

• Banca: CESPE / CEBRASPE
• Órgão: Banco da Amazônia
• Ano: 2012
• Provas: CESPE - 2012 - Banco da Amazônia - Técnico Científico - Administração de Dados
• Disciplina: Algoritmos e Estrutura de Dados
• Assuntos: Algoritmos; Algoritmos de Ordenação

Com relação a classificação de dados, julgue os itens que se seguem.


O método de classificação Shellsort iguala-se ao método Quicksort em termos de complexidade temporal, porém é mais eficiente para quantidades pequenas a moderadas de dados.

• C. Certo
• E. Errado

Gabarito: E

Comentários

• Shellsort:
    É o método a ser escolhido para a maioria das aplicações por ser muito e?ciente para arquivos de tamanho moderado.
    Mesmo para arquivos grandes, o método é cerca de apenas duas vezes mais lento do que o Quicksort.
    Sua implementação é simples e geralmente resulta em um programa pequeno.
    Não possui um pior caso ruim e quando encontra um arquivo parcialmente ordenado trabalha menos.
• A questão está errada por completa. "O método de classificação Shellsort iguala-se ao método Quicksort em termos de complexidade temporal, porém é mais eficiente para quantidades pequenas a moderadas de dados."
  A primeira parte está completamente errada. O Shellsort tem a complexidade dependente do gap escolhido. O problema da complexidade de tempo do Shellsort continua aberto. Mas, de uma forma geral, ele é pior que o Quicksort.
  A segunda parte é relativa. Depende bastante dos dados de entrada. O Shellsort se beneficia de dados ordenados ou quase ordenados. Para dados aleatórios, o Quicksort tende a se sair melhor. Na prática, o shellsort se sai um pouco melhor com um conjunto pequeno de dados. Mas não é categórico que ele é mais eficiente.

• Shellsort - O(n lg(n)2)

  Quicksort - O(nlg(n))

• QUICK - o (n log n) || o (n log n) || O (n2)

  Shell -    O (n) || o (n) || O (n log n)

• Força Guerreiro!!!!!!