Questão 769330

• 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; Complexidade de Algoritmos

Métodos de classificação por contagem são mais eficientes em termos de complexidade de tempo de execução que os métodos de classificação por comparação de chave.

• C. Certo
• E. Errado

Gabarito: C

Comentários

• Os métodos por contagem utilizam informação anterior para ordenar. Dessa forma, eles não estão resolvendo exatamente a mesma classe de problemas dos métodos por comparação.
  De qualquer forma, métodos por contagem conseguem ordenar em tempo linear (O(n+k) para o counting sort, geralmente k=n), enquanto métodos por comparação possuem o limite inferior de O(n log n) (maior que linear).

• Força Guerreiro!!!!!!