Flashcard FC517275
Qual a complexidade média e a complexidade no pior caso do Quick Sort?
Computação
CEBRASPE (CESPE) · 2025
Qual a complexidade média e a complexidade no pior caso do Quick Sort?
Mostrar resposta e comentário
Resposta
A complexidade média do Quick Sort é O(n log n) e no pior caso é O(n²).
• Complexidade média: ocorre porque a escolha do pivô gera partições balanceadas, com custo por nível O(n) e número de níveis O(log n).
• Pior caso: ocorre quando as partições são muito desiguais, pela recorrência T(n)=T(n-1)+Θ(n), resultando em Θ(n²).
Veja como foi cobrado:
https://flashcardsconcursos.com.br/portal/flashcard/513447
Conteúdo do catálogo FC Concursos · Atualizado em