Questão de Algoritmos e Estrutura de Dados — Algoritmos — IADES 2025
Algoritmos e Estrutura de Dados›Algoritmos
Código
qg509212
Banca
IADES
Órgão
CRMV-PI
Ano
2025
Nível
Superior
Cargo
Analista de Suporte e Gestão da Tecnologia da Informação
Considere dois algoritmos que resolvem o mesmo problema.Entretanto, o algoritmo A tem complexidade O(n²), enquanto o algoritmo B, tem complexidade O(n log n), em que n representa o tamanho da entrada.Em termos de desempenho assintótico, acerca desses algoritmos, ¢ correto afirmar que
Aambos os algoritmos apresentam desempenho idêntico em qualquer situação, pois resolvem o mesmo problema.
Bo algoritmo A sempre será mais eficiente que o algoritmo B, independentemente do tamanho da entrada.
Co algoritmo B tende a ser mais eficiente que o algoritmo A para grandes valores de n.
Da complexidade O(n²) garante melhor escalabilidade que O(n log n).
Eo algoritmo B é menos eficiente que o algoritmo A.
Revelar gabarito e comentário▾
GabaritoC — o algoritmo B tende a ser mais eficiente que o algoritmo A para grandes valores de 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 Algoritmos e Análise Assintótica
Gabarito: letra C. Em análise assintótica, a complexidade O(n log n) cresce mais lentamente que O(n²) para valores grandes de n, o que significa que o algoritmo B tende a ser mais eficiente que o A para entradas grandes. Esse é o fundamento da notação Big-O: comparar taxas de crescimento, não desempenho absoluto em um ponto específico.
A questão testa o entendimento básico de que, embora ambos os algoritmos resolvam o mesmo problema, suas complexidades computacionais diferem. O(n²) representa crescimento quadrático, enquanto O(n log n) é superlinear, mas muito mais próximo do linear para n grande. A alternativa correta reconhece que a vantagem do algoritmo B se manifesta sobretudo para grandes volumes de dados.
Alternativa A — ❌ Incorreta
Afirma que ambos têm desempenho idêntico em qualquer situação. Isso é falso: as complexidades são diferentes. Para entradas pequenas, O(n²) pode até ser mais rápido devido a constantes ocultas, mas a análise assintótica trata do comportamento para n grande, e ali as curvas divergem.
Alternativa B — ❌ Incorreta
Diz que o algoritmo A (O(n²)) sempre será mais eficiente que B (O(n log n)), independentemente do tamanho. Na verdade, para n suficientemente grande, O(n log n) supera O(n²). A afirmação ignora que, para entradas pequenas, fatores constantes podem inverter a ordem, mas assintoticamente B é superior.
Alternativa C — ✅ Correta ⟵ GABARITO
Afirma que o algoritmo B tende a ser mais eficiente para grandes valores de n. Isso está correto: O(n log n) tem taxa de crescimento menor que O(n²). Por exemplo, para n = 10⁶, n² = 10¹², enquanto n log n ≈ 10⁶ × 20 ≈ 2×10⁷, uma diferença enorme.
Alternativa D — ❌ Incorreta
Afirma que O(n²) garante melhor escalabilidade que O(n log n). Escalabilidade se refere ao comportamento conforme a entrada cresce; O(n²) escala pior (cresce mais rápido), portanto é menos escalável. O correto é o oposto: O(n log n) oferece melhor escalabilidade.
Alternativa E — ❌ Incorreta
Diz que o algoritmo B é menos eficiente que o A. Na verdade, B é mais eficiente assintoticamente. A alternativa inverte a relação.
PEGA ESSA DICA!
Em questões de complexidade, foque na ordem de crescimento: para n grande, funções com menor ordem dominam. Lembre-se: O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ). O(n log n) está entre linear e quadrático, sendo muito mais rápido que O(n²) para grandes entradas.