GabaritoC — Certo
Gabarito: C — CERTO. A afirmação está correta porque o Merge Sort, no pior caso, apresenta complexidade de tempo O(n log n), enquanto o Bubble Sort apresenta O(n²) — e, para entradas grandes, O(n log n) é assintoticamente mais eficiente que O(n²). Essa é uma relação clássica de análise de algoritmos, cobrada em conceitos básicos de programação e estruturas de dados.
A complexidade de tempo de um algoritmo descreve como o número de operações cresce conforme o tamanho da entrada (n) aumenta. Não se trata de medir segundos, mas da taxa de crescimento — a chamada notação Big-O. Ela ignora constantes e termos de menor ordem, focando no comportamento dominante quando n tende ao infinito. Por isso, comparar O(n log n) com O(n²) é comparar duas curvas de crescimento: a primeira cresce de forma quase linear, a segunda cresce de forma quadrática, tornando-se inviável para entradas grandes.
O Merge Sort é um algoritmo de ordenação baseado na técnica de divisão e conquista: divide o vetor ao meio recursivamente até restarem subvetores de tamanho 1 e, depois, intercala (merge) as partes ordenadas. Cada nível de divisão custa O(n) para intercalar, e há log n níveis — daí o O(n log n) em todos os casos (melhor, médio e pior). Já o Bubble Sort percorre o vetor repetidamente, comparando e trocando elementos adjacentes; no pior caso (vetor invertido), ele faz n passagens com n comparações cada, resultando em O(n²).
Na prática, a diferença é brutal. Para um vetor de 1 milhão de elementos, o Merge Sort executa cerca de 20 milhões de operações (n log n ≈ 10⁶ × 20), enquanto o Bubble Sort executa cerca de 500 bilhões (n² ≈ 10¹²) — uma diferença de 25 mil vezes. É por isso que algoritmos quadráticos funcionam bem em testes pequenos, mas se tornam inviáveis em produção com grandes volumes de dados.
A pegadinha que a banca poderia explorar é inverter os valores ou afirmar que o Merge Sort é O(n²) no pior caso — o que é falso, pois o Merge Sort mantém O(n log n) mesmo no pior cenário. Outra confusão comum é trocar a complexidade do Merge Sort pela do Quick Sort (que tem pior caso O(n²), embora o caso médio seja O(n log n)). Aqui, a afirmação está tecnicamente precisa e correta.
Guarde a fronteira entre as complexidades: O(n log n) é a classe dos algoritmos eficientes (Merge Sort, Heap Sort), enquanto O(n²) é a classe dos algoritmos simples e lentos (Bubble Sort, Insertion Sort, Selection Sort). É exatamente nessa distinção que a questão se apoia.
A afirmação está correta. O Merge Sort tem complexidade de tempo O(n log n) no pior caso, pois divide o problema em duas metades (log n níveis) e gasta O(n) para intercalar cada nível. O Bubble Sort, por sua vez, tem complexidade O(n²) no pior caso, pois realiza n passagens com n comparações cada. Como O(n log n) cresce muito mais lentamente que O(n²) para n grande, o Merge Sort é, de fato, mais eficiente que o Bubble Sort. A comparação está tecnicamente precisa e reflete o conhecimento clássico de análise de algoritmos.
A afirmação não é falsa. Se a banca considerasse esta alternativa como correta, estaria negando uma relação matemática bem estabelecida: O(n log n) < O(n²) para n suficientemente grande. O erro aqui seria do candidato que confundisse a complexidade do Merge Sort com a do Quick Sort (que tem pior caso O(n²)) ou que acreditasse que o Merge Sort é O(n²) no pior caso — o que não ocorre, pois o Merge Sort mantém O(n log n) em todos os cenários. Portanto, esta alternativa está incorreta.
Para fixar, memorize a tabela das complexidades dos algoritmos de ordenação mais cobrados:
Algoritmo | Melhor caso | Caso médio | Pior caso |
|---|---|---|---|
Bubble Sort | O(n) | O(n²) | O(n²) |
Insertion Sort | O(n) | O(n²) | O(n²) |
Selection Sort | O(n²) | O(n²) | O(n²) |
Merge Sort | O(n log n) | O(n log n) | O(n log n) |
Quick Sort | O(n log n) | O(n log n) | O(n²) |
Heap Sort | O(n log n) | O(n log n) | O(n log n) |
A pegadinha clássica é trocar o pior caso do Quick Sort (O(n²)) pelo do Merge Sort. Com essa tabela, você elimina a dúvida na hora da prova.
Gabarito: letra C — a afirmação está CERTA.
Link permanente: /questoes/qg603668