Questão de Algoritmos e Estrutura de Dados — Estrutura de Dados — FGV 2024
Algoritmos e Estrutura de Dados›Estrutura de Dados
Código
fg098518
Banca
FGV
Órgão
TJ-MS
Ano
2024
Nível
Superior
Cargo
Técnico de Nível Superior - Analista de Sistemas Computacionais - Analista de Sistemas
Bárbara implementa um algoritmo de ordenação estável cuja complexidade temporal média OT pertence a O(n.logn) e cuja complexidade espacial OE pertence a O(n), sendo n o tamanho do vetor a ser ordenado.O algoritmo implementado é o:
Aquick sort;
Bmerge sort;
Cbubble sort;
Dinsertion sort;
Eselection sort.
Revelar gabarito e comentário▾
GabaritoB — merge sort;
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”.
Algoritmos de ordenação: análise de complexidade
Gabarito: letra B (merge sort). O merge sort é um algoritmo estável, com complexidade temporal média O(n log n) e complexidade espacial O(n), exatamente como descrito no enunciado. Nenhuma das outras alternativas reúne essas três características simultaneamente.
A banca cobra a memória das propriedades clássicas dos algoritmos de ordenação. A tabela abaixo resume os pontos-chave:
Algoritmo
Estável?
Tempo médio
Espaço extra
Quick sort
Não
O(n log n)
O(log n) (in-place)
Merge sort
Sim
O(n log n)
O(n)
Bubble sort
Sim
O(n²)
O(1)
Insertion sort
Sim
O(n²)
O(1)
Selection sort
Não
O(n²)
O(1)
Alternativa A — ❌ Incorreta
O quicksort não é estável e, embora tenha tempo médio O(n log n), sua complexidade espacial adicional é O(log n) (para a pilha de recursão), e não O(n). Além disso, a versão in-place típica não utiliza espaço extra linear. Portanto, não atende à descrição.
Alternativa B — ✅ Correta ⟵ GABARITO
O merge sort é estável, possui complexidade temporal média O(n log n) e complexidade espacial O(n) (necessária para o vetor auxiliar na intercalação). Essas características casam perfeitamente com o enunciado.
Alternativa C — ❌ Incorreta
O bubble sort é estável e tem espaço O(1), mas sua complexidade temporal média é O(n²), e não O(n log n). Portanto, não se enquadra.
Alternativa D — ❌ Incorreta
O insertion sort é estável e tem espaço O(1), porém o tempo médio é O(n²), e não O(n log n).
Alternativa E — ❌ Incorreta
O selection sortnão é estável (quebra a ordem relativa de elementos iguais), tem tempo médio O(n²) e espaço O(1). Nenhum dos requisitos é atendido.
PEGA ESSA DICA!
Para questões de ordenação, memorize o trio de propriedades (estabilidade, tempo, espaço) de cada algoritmo. O merge sort é o único estável com O(n log n) e O(n) de espaço. O quicksort (não estável, espaço O(log n)) e o heapsort (não estável, espaço O(1)) também têm O(n log n), mas não são estáveis.