Questão 3832699

• Banca: INSTITUTO AOCP
• Órgão: Prefeitura de Novo Hamburgo - RS
• Ano: 2020
• Provas: INSTITUTO AOCP - 2020 - Prefeitura de Novo Hamburgo - RS - Analista de Desenvolvimento de Sistemas
• Disciplina: Algoritmos e Estrutura de Dados
• Assuntos: Algoritmos; Complexidade de Algoritmos

Assinale a alternativa que apresenta o tempo de execução do pior caso e do melhor caso para o algoritmo quicksort ou ordenação rápida.

• A. Pior caso: O(n²); melhor caso: O(n).
• B. Pior caso: O(n lg n); melhor caso: O(n).
• C. Pior caso: O(n); melhor caso: O(n + m).
• D. Pior caso: O(n lg n); melhor caso: O(n + m).
• E. Pior caso: O(n²); melhor caso: O(n lg n).

Gabarito: E

Comentários

• Não tenho na mente o funcionamento exato do algoritmo informado pela questão, mas basta sabermos a precedência das classes de complexidade de algoritmos e marcar a assertiva onde tenha a maior complexidade para o pior caso e a menor complexidade para o melhor caso! Alternativa E

  A maioria dos algoritmos de ordenação tem o pior caso de complexidade O(n^2)

• @Homelander, seguindo essa lógica, seria letra A.

  O(n) é menos complexo do que O(n lg n)

• O Felipe Jansen foi cirúrgico no raciocínio. Essa estratégia pode ser usada em vários tipos de questões.

  E de fato o pior cenário para o QuickSort é O(n²) e o melhor cenário O(n log(n))

• Força Guerreiro!!!!!!

• GABARITO E

  Quick Sort

  • Melhor caso: O(n log n)
  • Médio caso: O(n log n)
  • Pior caso: O(n²)