GabaritoC — O (n 2 )
Gabarito: letra C. A complexidade de tempo de pior caso do algoritmo quicksort é O(n²), que ocorre quando as partições são extremamente desbalanceadas (por exemplo, quando a lista já está ordenada e o pivô é o primeiro ou último elemento). O conteúdo de apoio da Wikipedia confirma que "o algoritmo terá tempo de execução igual à θ(n²)" no pior caso.
A banca testa o conhecimento da análise de complexidade do quicksort, um clássico de algoritmos de ordenação. É essencial diferenciar os casos: melhor caso O(n log n), caso médio O(n log n) e pior caso O(n²).
O(1) é complexidade constante, típica de operações elementares (acesso a um índice de array). Não se aplica à ordenação de n elementos.
O(n) é linear, comum em algoritmos como percorrer um vetor uma vez. O quicksort, no pior caso, faz muito mais comparações.
O(n²) é a complexidade do pior caso do quicksort. Ocorre quando o pivô é sempre o maior ou o menor elemento, gerando partições de tamanho 0 e n-1, levando a uma relação de recorrência cuja solução é θ(n²).
O(n log n) é a complexidade do melhor caso e do caso médio do quicksort, não do pior caso.
O(n² log n) não é uma complexidade típica do quicksort ou da maioria dos algoritmos de ordenação comuns. É superior ao pior caso real.
O pior caso do quicksort é O(n²). Para evitar esse comportamento, usa-se escolha aleatória do pivô ou algoritmos como o introsort, que alterna para heapsort quando detecta um pior caso. Na prova, lembre-se da tríade: melhor O(n log n), médio O(n log n), pior O(n²).
Gabarito: letra C.
Link permanente: /questoes/qq317754