Questão 4 — Algoritmos de Ordenação — Complexidade do Quicksort (Algoritmos e Estruturas de Dados) — Serviço de Seleção do Pessoal da Marinha (SSPM) · Marinha do Brasil 2023

Algoritmos e Estruturas de Dados Algoritmos de Ordenação — Complexidade do Quicksort

Serviço de Seleção do Pessoal da Marinha (SSPM) 2023

Marinha do Brasil · Quadro Técnico do Corpo Auxiliar da Marinha (CP-T) — Informática · Caderno Amarela

Gabarito disponível

Segundo Szwarcfiter (2010), assinale a opção correta referente à performance do algoritmo de ordenação quicksort.

Selecione uma alternativa A) No pior caso a performance corresponde à O(n log² n). B) No caso médio a performance corresponde à O(n²). C) No melhor caso a performance corresponde à O(log n). D) No melhor caso a performance corresponde à O(n). E) No melhor caso a performance corresponde à O(n log n).

Resolução comentada

O melhor caso do quicksort é O(n log n).

No melhor caso, e também no caso médio, o pivô divide o vetor de forma equilibrada. Isso dá log n níveis de recursão com custo n por nível, ou seja, O(n log n). O pior caso é O(n²).

Análise das alternativas

A) O pior caso é O(n²), não O(n log² n). B) O caso médio é O(n log n). C e D) O(log n) e O(n) são inferiores ao mínimo necessário para ordenar por comparações.

Referência: Szwarcfiter (2010), Estruturas de Dados e Seus Algoritmos.

Resolução comentada do VaiConcursos.