Questão de Algoritmos e Estrutura de Dados — Algoritmos — CESGRANRIO 2024

Complexidade de Algoritmos de Ordenação

Gabarito: letra C. O pior caso do Quick sort tem complexidade $O(n^2)$. O algoritmo cujo caso médio é $O(n^2)$ é o Insertion sort — exatamente o que a questão pede: um algoritmo que, em seu caso médio, seja proporcional ao pior caso do Quick sort. Dados aleatórios não favorecem o Insertion sort (que é $O(n^2)$ em média), enquanto os demais algoritmos listados possuem caso médio $O(n \log n)$ ou melhor.

A banca testa o conhecimento das complexidades típicas dos principais algoritmos de ordenação. A chave é lembrar que:

• Quick sort: melhor/médio $O(n \log n)$, pior $O(n^2)$ (quando o pivô é sempre o menor ou maior elemento).

• Insertion sort: melhor $O(n)$ (já ordenado), médio e pior $O(n^2)$.

• Heap sort, Merge sort, Tree sort: todos $O(n \log n)$ no caso médio (e também no pior, exceto Tree sort que pode degenerar).

• Bucket sort: médio $O(n+k)$, mas pode ser $O(n^2)$ no pior; porém seu caso médio é linear, não $O(n^2)$.

Alternativa A — ❌ Incorreta

Bucket sort tem complexidade média $O(n + k)$, onde $k$ é o número de baldes. Para dados uniformemente distribuídos, aproxima-se de $O(n)$, não $O(n^2)$. Portanto, não atende ao requisito.

Alternativa B — ❌ Incorreta

Heap sort possui complexidade $O(n \log n)$ tanto no pior quanto no caso médio. Logo, seu caso médio é $\Theta(n \log n)$, não $O(n^2)$.

Alternativa C — ✅ Correta ⟵ GABARITO

Insertion sort tem complexidade média $O(n^2)$. Para um array de 10.000 elementos aleatórios, o número médio de comparações e trocas é proporcional a $n^2$, o que equivale ao pior caso do Quick sort ($O(n^2)$). O enunciado pede exatamente essa correspondência.

Alternativa D — ❌ Incorreta

Merge sort tem complexidade $O(n \log n)$ no melhor, médio e pior caso. Seu caso médio é $\Theta(n \log n)$, não $O(n^2)$.

Alternativa E — ❌ Incorreta

Tree sort (inserção em árvore binária de busca seguida de percurso em ordem) tem complexidade média $O(n \log n)$. Embora no pior caso (árvore degenerada) possa ser $O(n^2)$, o caso médio para dados aleatórios é $\Theta(n \log n)$, não $O(n^2)$.

Gabarito: letra C.