Questão 425128

• Banca: COPEVE-UFAL
• Órgão: UFAL
• Ano: 2011
• Provas: COPEVE-UFAL - 2011 - UFAL - Analista de Tecnologia da Informação
• Disciplina: Algoritmos e Estrutura de Dados
• Assuntos: Algoritmos; Algoritmos de Ordenação; Complexidade de Algoritmos

tempo de execução do pior caso do algoritmo de ordenação Quicksort é:

• A.
• B.
• C.
• D.
• E.

Gabarito: E

Comentários

• a complexidade de pior caso do algoritmo quicksort é O(n²).
  Já o tempo de execução não há como saber, depende de uma série de fatores, entre eles:
  • Tamanho da entrada
  • Arquitetura na qual o algoritmo é executado
  • Concorrência com outros processos
  • etc...

• A complexidade no caso médio (Teta) para o QuickSort é n log n.
  Para o pior caso é O(n^2).

• O quick sort têm tempo médio n log n, mas em casos específicos(pior caso) leva n^2.

  Apesar de ser lento apenas em caso específicos, o caso específico não deixa de ser comum. Em implementações comuns o algoritmo se comporta mal justamente quando uma lista já está ordenada, algo que não é incomum.Apesar de existirem diversos algoritmos com temo n log n, o quicksort é um dos mais velozes no caso médio, por isso ainda é muito utilizado.

  Imagino que a questão foi anulada por falar em tempo de execução ao invés de complexidade. Um problema que talvez fosse ignorado por muitas bancas.