Questão de Algoritmos e Estrutura de Dados — Algoritmos — IF-ES 2025
Algoritmos e Estrutura de Dados›Algoritmos
Código
qg529112
Banca
IF-ES
Órgão
IF-ES
Ano
2025
Nível
Médio
Cargo
Técnico de Laboratório / Área: Informática
Considere o algoritmo de ordenação para um vetor de inteiros em linguagem Javascript descrito a seguir:sort = (array) => {if (array.length <= 1) {return array;}const pivot = array[array.length - 1];const left = [];const right = [];for (let i = 0; i < array.length - 1; i++) {if (array[i] < pivot) {left.push(array[i]);} else {right.push(array[i]);}}return [...sort(left), pivot, ...sort(right)];}Considerando n como o tamanho do vetor, assinale a alternativa CORRETA que corresponde à complexidade média de tempo do algoritmo na notação Big-O:
AO(n).
BO(nlogn).
CO(logn).
DO(n²).
EO(2n).
Revelar gabarito e comentário▾
GabaritoB — O(nlogn).
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 do QuickSort (média)
Gabarito: letra B. O algoritmo apresentado é uma implementação recursiva do QuickSort, que escolhe o último elemento como pivô. No caso médio, a complexidade de tempo é O(n log n), resultado da divisão equilibrada do vetor em subproblemas de tamanho aproximadamente n/2 e da combinação linear (n) em cada nível.
A banca testa o conhecimento sobre a notação Big-O e o comportamento médio dos algoritmos de ordenação. Enquanto o pior caso do QuickSort é O(n²) (quando o pivô é o menor ou maior elemento, gerando partições desbalanceadas), o caso médio é O(n log n), que é a alternativa correta.
1Escolhe pivô (último elemento)
2Particiona vetor em left e right
3Recursão em left e right
4Combina: left + pivô + right
LEVEL · soulevel.com.br
Alternativa A — ❌ Incorreta
O(n) corresponde à complexidade de algoritmos lineares, como busca sequencial. Um algoritmo de ordenação por comparação não pode ter complexidade média inferior a O(n log n), conforme o teorema do limite inferior.
Alternativa B — ✅ Correta ⟵ GABARITO
O(n log n) é a complexidade média do QuickSort. A cada nível da recursão, o vetor é particionado e, em média, as partições são equilibradas, gerando log n níveis e, em cada nível, o trabalho total é O(n).
Alternativa C — ❌ Incorreta
O(log n) é a complexidade de algoritmos como a busca binária, que operam em estruturas ordenadas e descartam metade dos elementos a cada passo. Ordenar um vetor exige comparar todos os elementos, o que inviabiliza esse limite.
Alternativa D — ❌ Incorreta
O(n²) é a complexidade do pior caso do QuickSort (vetor já ordenado em ordem crescente e pivô sendo o último elemento) e de algoritmos como Bubble Sort e Insertion Sort no pior caso. Não é a média.
Alternativa E — ❌ Incorreta
O(2n) é equivalente a O(n), pois constantes multiplicativas são ignoradas na notação Big-O. Portanto, também é uma complexidade linear, incorreta para o caso médio do QuickSort.