Questão de Tecnologia da Informação · FGV CVM 2024 (nº 12)

A complexidade de tempo de um algoritmo de ordenação indica como o número de operações que ele realiza cresce em função do número de elementos (N) a serem ordenados, sendo $N^2$ uma relação quadrática e $N \log N$ uma relação mais eficiente.

• (A) Correta: O Quicksort é conhecido por ter uma complexidade de tempo de $O(N^2)$ no pior caso (quando a escolha do pivô é sempre desfavorável) e $O(N \log N)$ no caso médio, o que corresponde exatamente à descrição da questão.
• (B) Incorreta: O Heap Sort possui complexidade de tempo de $O(N \log N)$ tanto no pior caso quanto no caso médio, não se encaixando no critério de $O(N^2)$ no pior caso.
• (C) Incorreta: O Merge Sort possui complexidade de tempo de $O(N \log N)$ tanto no pior caso quanto no caso médio, não se encaixando no critério de $O(N^2)$ no pior caso.
• (D) Incorreta: O Insertion Sort possui complexidade de tempo de $O(N^2)$ tanto no pior caso quanto no caso médio, não atendendo ao critério de $N \log N$ no caso médio. Armadilha: É um distrator comum porque compartilha a complexidade $O(N^2)$ no pior caso com o Quicksort, mas difere no caso médio.
• (E) Incorreta: O Selection Sort possui complexidade de tempo de $O(N^2)$ tanto no pior caso quanto no caso médio, não atendendo ao critério de $N \log N$ no caso médio.