Questão de Algoritmos e Estrutura de Dados — Algoritmos — LJ Assessoria e Planejamento Administrativo Limita 2022
Algoritmos e Estrutura de Dados›Algoritmos
Código
qq775981
Banca
LJ Assessoria e Planejamento Administrativo Limita
Órgão
Prefeitura de Buriticupu - MA
Ano
2022
Nível
Superior
Cargo
Analista de Sistemas
Dada as duas funções a seguir, assinale a opção que diz corretamente qual é a ordem de complexidade de cada uma delas.f1(n) = 2n 2 + 5n operaçõesf2(n) = 500n + 4000 operações
Af1(n) = O(n²), f2(n) = O(n)
Bf1(n) = O(n² + n), f2(n) = O(n + 1)
Cf1(n) = O(n), f2(n) = O(n)
Df1(n) = O(n), f2(n) = O(n²)
Ef1(n) = O(10n²), f2(n) = O(500n)
Revelar gabarito e comentário▾
GabaritoA — f1(n) = O(n²), f2(n) = 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 de complexidade de algoritmos
Gabarito: letra A. A notação Big O descreve o comportamento assintótico, ignorando constantes multiplicativas e termos de menor ordem. Para f1(n) = 2n² + 5n, o termo dominante é n², logo f1(n) = O(n²). Para f2(n) = 500n + 4000, o termo dominante é n, logo f2(n) = O(n). A alternativa A reflete isso corretamente.
Alternativa A — ✅ Correta ⟵ GABARITO
A alternativa afirma que f1(n) = O(n²) e f2(n) = O(n). Isso está em conformidade com a definição: constantes (2 e 500) e termos de ordem inferior (5n e 4000) são descartados na notação Big O. O termo de maior grau em f1 é n²; em f2 é n.
Alternativa B — ❌ Incorreta
Afirma que f1(n) = O(n² + n) e f2(n) = O(n + 1). Embora n² + n seja equivalente a O(n²), a notação não deve incluir termos de ordem inferior. Além disso, f2(n) = O(n) é suficiente; O(n + 1) é redundante. A banca exige a simplificação correta.
Alternativa C — ❌ Incorreta
Afirma que ambas são O(n). Isso está errado para f1, pois o termo dominante é n², não n. A complexidade de f1 é quadrática, não linear.
Alternativa D — ❌ Incorreta
Inverte as ordens: f1 como O(n) e f2 como O(n²). f1 é quadrática e f2 é linear, portanto a inversão é incorreta.
Alternativa E — ❌ Incorreta
Mantém constantes na notação: f1 = O(10n²) e f2 = O(500n). A notação Big O ignora constantes multiplicativas (10 e 500), portanto ambas as expressões são equivalentes a O(n²) e O(n), respectivamente, mas a forma padrão não inclui constantes.
PEGA ESSA DICA!
Na notação Big O, foque sempre no termo de maior ordem (dominante) e descarte constantes e termos de ordem inferior. Por exemplo, 2n² + 5n é O(n²); 500n + 4000 é O(n). Isso vale para qualquer constante.