Questão FC373200
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 apresen
Algoritmos e Lógica de Programação
FCC · 2022
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-1
NCmédio ≅ (N*(N-1))/4 - 1/2
NCpior ≅ (N*(N-1)-1)/2
Com base nestes resultados, é correto afirmar que o método
- é sempre ineficiente, mesmo para valores pequenos de N.
- é de ordem de complexidade quadrática ou O(N2).
- apresenta um desempenho muito eficiente no caso médio, quando o vetor está em ordem decrescente, por exemplo.
- é de ordem de complexidade linearítmica ou O(N-1) no melhor caso, quando o vetor está parcialmente ordenado.
- sempre realiza um número muito grande de trocas em todos os três casos, por isso é muito ineficiente.
Mostrar resposta e comentário
Gabarito
B
Comentário do professor
A alternativa está correta porque o número de comparações no caso médio e no pior caso apresenta termos que crescem com o quadrado de \(N\). Especificamente, \(NC_{médio}\approx \frac{N(N-1)}{4}-\frac{1}{2}\) e \(NC_{pior}\approx \frac{N(N-1)-1}{2}\), cujos termos dominantes são, respectivamente, \(\approx \frac{N^2}{4}\) e \(\approx \frac{N^2}{2}\).
Em análise assintótica considera-se o termo dominante para \(N\) grande, desprezando constantes e termos de menor ordem; por isso ambos os casos implicam crescimento proporcional a \(N^2\).
Embora o melhor caso seja \(NC_{melhor}=N-1\) (linear), isso não altera a classificação assintótica geral: a complexidade é definida pelo comportamento assintótico mais relevante, resultando em ordem de complexidade quadrática, ou seja, O(N^2).
Conteúdo do catálogo FC Concursos · Atualizado em