Pular para o conteúdo principal

Questão de Programação — Linguagens de programação — Avança SP 2025

ProgramaçãoLinguagens de programação
Código
qg425166
Banca
Avança SP
Órgão
UNITAU
Ano
2025
Nível
Superior
Cargo
Programador Pleno
Qual é a complexidade de tempo (notação Big-O) do algoritmo Quick Sort no caso médio?
  1. AO(n)
  2. BO(n log n)
  3. CO(n²)
  4. DO(log n)
  5. EO(n^2)
Revelar gabarito e comentário

GabaritoB — O(n log n)

Comentário gerado por IA. É um apoio ao estudo, ancorado em fontes, mas pode conter imprecisões — confira sempre na fonte oficial (lei, súmula, edital e gabarito da banca). Encontrou um erro? Use “Reportar”.

Complexidade de tempo do Quick Sort

Gabarito: letra B. No caso médio, o Quick Sort apresenta complexidade de tempo O(n log n), pois o particionamento divide o array em duas metades aproximadamente iguais a cada chamada recursiva, resultando em log n níveis de recursão, cada um com custo linear O(n). Essa é a característica que torna o algoritmo eficiente na prática, apesar de seu pior caso ser O(n²).

A complexidade de tempo de um algoritmo mede como o número de operações cresce em função do tamanho da entrada (n). No Quick Sort, o algoritmo escolhe um pivô e particiona o array em elementos menores e maiores que ele, recursivamente ordenando cada partição. No caso médio, o pivô tende a dividir o array em duas partes aproximadamente iguais, criando uma árvore de recursão balanceada com profundidade logarítmica (log n). Em cada nível dessa árvore, o algoritmo percorre todos os n elementos para particionar, resultando em um custo total de O(n) por nível. Multiplicando a profundidade (log n) pelo custo por nível (n), obtemos O(n log n).

Para entender por que o caso médio é O(n log n), considere um array de 8 elementos. O primeiro particionamento divide em duas partes de 4, cada uma dividida em partes de 2, e assim por diante. O número de níveis de recursão é log₂(8) = 3. Em cada nível, o algoritmo processa todos os 8 elementos, totalizando 8 × 3 = 24 operações, que é proporcional a n log n. Esse comportamento é o que torna o Quick Sort um dos algoritmos de ordenação mais rápidos na prática, superando algoritmos quadráticos como o Bubble Sort e o Insertion Sort para entradas grandes.

A distinção crucial que a banca explora é entre o caso médio e o pior caso. Enquanto o caso médio é O(n log n), o pior caso ocorre quando o pivô escolhido é sempre o menor ou o maior elemento, resultando em partições desbalanceadas (uma com n-1 elementos e outra vazia). Nesse cenário, a profundidade da recursão se torna n, e o custo total é O(n²). Esse pior caso acontece, por exemplo, quando o array já está ordenado e o pivô é sempre o primeiro elemento. A escolha de um pivô aleatório ou da mediana de três elementos é uma estratégia comum para evitar esse comportamento degenerado.

A pegadinha desta questão está em confundir o caso médio com o pior caso. Muitos candidatos, ao lembrarem que o Quick Sort pode ser O(n²), marcam a alternativa C, mas a pergunta é específica sobre o caso médio, que é O(n log n). É essencial ler o enunciado com atenção e distinguir os três cenários: melhor caso (O(n log n)), caso médio (O(n log n)) e pior caso (O(n²)).

Guarde essa fronteira entre caso médio e pior caso: é exatamente nela que as alternativas se dividem. A alternativa correta é a que apresenta O(n log n), enquanto as demais ou representam outras complexidades ou o pior caso do algoritmo.

Alternativa A — ❌ Incorreta

A alternativa afirma que a complexidade é O(n), o que seria uma complexidade linear. Isso não corresponde ao Quick Sort em nenhum cenário. O(n) seria a complexidade de algoritmos que percorrem o array uma única vez, como uma busca linear. O Quick Sort, mesmo no melhor caso, precisa de log n níveis de recursão, resultando em O(n log n), nunca O(n).

Alternativa B — ✅ Correta ⟵ GABARITO

A alternativa está correta porque, no caso médio, o Quick Sort divide o array em duas metades aproximadamente iguais a cada recursão, gerando log n níveis de recursão, cada um com custo linear O(n). O produto desses fatores resulta em O(n log n), que é a complexidade esperada para o caso médio do algoritmo.

Alternativa C — ❌ Incorreta

A alternativa afirma que a complexidade é O(n²), o que corresponde ao pior caso do Quick Sort, não ao caso médio. O pior caso ocorre quando o pivô escolhido é sempre o menor ou o maior elemento, gerando partições desbalanceadas e profundidade de recursão n. A banca explora exatamente essa confusão entre caso médio e pior caso.

Alternativa D — ❌ Incorreta

A alternativa afirma que a complexidade é O(log n), o que seria uma complexidade logarítmica. Isso não corresponde ao Quick Sort, pois o algoritmo precisa processar todos os n elementos em cada nível de recursão. O(log n) seria a complexidade de uma busca binária, que não ordena o array, apenas encontra um elemento.

Alternativa E — ❌ Incorreta

A alternativa afirma que a complexidade é O(n^2), que é a mesma do pior caso, representada de forma diferente da alternativa C. Assim como a C, essa alternativa confunde o caso médio com o pior caso. A notação O(n^2) é equivalente a O(n²), e ambas estão incorretas para o caso médio.

NÃO CAIA NESSA!

A banca troca o caso médio pelo pior caso. O candidato que lembra que o Quick Sort pode ser O(n²) marca a alternativa C ou E, mas a pergunta é específica sobre o caso médio, que é O(n log n). Fique atento ao termo "caso médio" no enunciado — ele é o gatilho para a resposta correta.

PEGA ESSA DICA!

Para memorizar as complexidades do Quick Sort, lembre-se: melhor caso e caso médio são O(n log n), pior caso é O(n²). Compare com outros algoritmos de ordenação: Merge Sort é sempre O(n log n), Heap Sort é sempre O(n log n), e Bubble Sort é O(n²) no pior caso. Essa tabela ajuda a fixar:

Algoritmo

Melhor caso

Caso médio

Pior caso

Quick Sort

O(n log n)

O(n log n)

O(n²)

Merge Sort

O(n log n)

O(n log n)

O(n log n)

Heap Sort

O(n log n)

O(n log n)

O(n log n)

Bubble Sort

O(n)

O(n²)

O(n²)

Gabarito: letra B

Link permanente: /questoes/qg425166