Questão
ID 2975880Disciplina: Tecnologia da Informação
Assuntos: Complexidade de Algoritmos (Big-O, P x NP)
Ano: 2026 Banca: IFPI - Instituto Federal do Piauí Órgão: Instituto Federal de Educação Ciência e Tecnologia do Piauí
Considere os algoritmos clássicos de ordenação: Bubble Sort, Selection Sort, Insertion Sort, Merge Sort e Quick Sort.
Analise as afirmativas a seguir com base em suas propriedades formais de complexidade, estabilidade e uso de memória na implementação tradicional apresentada na literatura clássica.
I. O Insertion Sort possui complexidade de tempo O(n²) no pior caso e pode apresentar complexidade O(n) no melhor caso, quando o vetor já se encontra ordenado.
II. O Merge Sort apresenta complexidade O(n log n) nos casos melhor, médio e pior, é estável e, em sua implementação tradicional, requer espaço adicional proporcional a O(n).
III. O Quick Sort apresenta complexidade média O(n log n) e pior caso O(n²), podendo este ocorrer quando o pivô escolhido produz partições altamente desbalanceadas.
IV. O Selection Sort possui complexidade O(n²) nos casos melhor, médio e pior e, em sua implementação tradicional, não é considerado um algoritmo estável.
Assinale a alternativa CORRETA: