Acerca das estruturas de dados multimídias e dos algoritmos de ordenação e busca, julgue o item a seguir. O algoritmo de ordenação Quick Sort possui, em média, complexidade de temp

Gabarito

Certo

Comentário do professor

Quick Sort é um algoritmo de ordenação por divide and conquer. Na prática, sua **complexidade média** é \(O(n\log n)\) porque, em média, a escolha do pivô gera partições balanceadas; o custo por nível é \(O(n)\) e o número de níveis é da ordem de \(\log n\), modelado pela recorrência típica \(T(n)=2T(n/2)+\Theta(n)\), que resulta em \(\Theta(n\log n)\).

Contudo, no pior caso as partições ficam muito desiguais, por exemplo quando o pivô é sempre o menor ou maior elemento (caso comum se a entrada já está ordenada e o pivô for extremo). A recorrência vira \(T(n)=T(n-1)+\Theta(n)\), levando a \(\Theta(n^2)\).

Por isso a afirmação está correta. Estratégias como escolha aleatória do pivô ou median-of-three reduzem a probabilidade do pior caso, mantendo o tempo esperado em \(O(n\log n)\).