Questão de Algoritmos e Estrutura de Dados — Algoritmos — FCC 2022
Algoritmos e Estrutura de Dados›Algoritmos
Código
fc064891
Banca
FCC
Órgão
TRT - 19ª Região (AL)
Ano
2022
Cargo
Analista Judiciário - Área Apoio Especializado Especialidade: Tecnologia da Informação
Considere que um método de ordenação tenha seu desempenho baseado no número de comparações que realiza para ordenar um vetor com N elementos em ordem crescente. Este método apresenta o seguinte resultado no melhor caso (NCmelhor), no caso médio (NCmédio) e no pior caso (NCpior):NCmelhor = N-1NCmédio ≅ (N*(N-1))/4 - 1/2NCpior ≅ (N*(N-1)-1)/2Com base nestes resultados, é correto afirmar que o método
Aé sempre ineficiente, mesmo para valores pequenos de N.
Bé de ordem de complexidade quadrática ou O(N²).
Capresenta um desempenho muito eficiente no caso médio, quando o vetor está em ordem decrescente, por exemplo.
Dé de ordem de complexidade linearítmica ou O(N-1) no melhor caso, quando o vetor está parcialmente ordenado.
Esempre realiza um número muito grande de trocas em todos os três casos, por isso é muito ineficiente.
Revelar gabarito e comentário▾
GabaritoB — é de ordem de complexidade quadrática ou O(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”.
Análise da complexidade do método de ordenação
Gabarito: letra B. As fórmulas fornecidas (N-1 no melhor caso, aproximadamente N²/4 no caso médio e N²/2 no pior caso) são características do algoritmo de ordenação por inserção (insertion sort), cuja complexidade assintótica é O(N²) — quadrática. As demais alternativas incorrem em erros conceituais sobre eficiência, comportamento em diferentes cenários e nomenclatura de complexidade.
Caso
Número de Comparações (NC)
Complexidade Assintótica
Característica do Vetor
Melhor
N – 1
O(N)
Já ordenado
Médio
≈ N²/4
O(N²)
Aleatório
Pior
≈ N²/2
O(N²)
Ordem decrescente
Complexidade do método: Melhor caso (N-1) (Vetor já ordenado, Nenhuma troca, O(N) — linear); Caso médio (~N²/4) (Vetor aleatório, O(N²) — quadrático); Pior caso (~N²/2) (Vetor decrescente, O(N²) — quadrático)
Alternativa A — ❌ Incorreta
Afirma que o método "é sempre ineficiente, mesmo para valores pequenos de N". Na verdade, a ordenação por inserção é eficiente para N pequenos (típico uso em subvetores de algoritmos como quicksort), e seu melhor caso é linear (O(N)).
Alternativa B — ✅ Correta ⟵ GABARITO
A comparação das fórmulas mostra que o termo dominante nos casos médio e pior é quadrático: NCmédio ∼ N²/4 e NCpior ∼ N²/2. Portanto, a ordem de complexidade é O(N²) (quadrática).
Alternativa C — ❌ Incorreta
Diz que o desempenho é "muito eficiente no caso médio, quando o vetor está em ordem decrescente". O vetor em ordem decrescente é justamente o pior caso (maior número de comparações/trocas), não o caso médio. O caso médio é um vetor aleatório, não decrescente.
Alternativa D — ❌ Incorreta
Alega que o método é de "ordem de complexidade linearítmica ou O(N-1) no melhor caso". O termo linearítmico refere-se a O(N log N), não a O(N). O(N-1) é O(N), linear. Além disso, o melhor caso da ordenação por inserção ocorre quando o vetor já está ordenado, não "parcialmente ordenado".
Alternativa E — ❌ Incorreta
Afirma que "sempre realiza um número muito grande de trocas em todos os três casos". No melhor caso (vetor já ordenado), a ordenação por inserção não realiza trocas (apenas uma comparação por elemento), portanto não há um número grande de trocas.