Questão de Algoritmos e Estrutura de Dados — Complexidade de Algoritmos — FGV 2024
Algoritmos e Estrutura de Dados›Complexidade de Algoritmos
Código
fg077368
Banca
FGV
Órgão
CVM
Ano
2024
Nível
Superior
Cargo
Analista - Perfil 8 - TI / Sistemas e Desenvolvimento - Tarde
O analista José precisa escolher entre dois algoritmos, Abusca e Cbusca. José sabe que, sendo N o tamanho da entrada do algoritmo, Abusca requer 2N + log₂(N) operações para ser executado. Já o Cbusca requer N⁴ + N operações para ser executado. José determinou, na notação O-grande, a complexidade de tempo no pior caso para cada algoritmo e, por fim, deve escolher o algoritmo que apresenta a menor ordem de complexidade no pior caso.José deve escolher o algoritmo:
ACbusca, que possui complexidade O(N);
BAbusca, que possui complexidade O(2N);
CCbusca, que possui complexidade O(N⁴ );
DCbusca, que possui complexidade O(3N);
EAbusca, que possui complexidade O(log(N)).
Revelar gabarito e comentário▾
GabaritoC — Cbusca, que possui complexidade 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”.
Complexidade de algoritmos: notação O-grande
Gabarito: letra C. A única alternativa que apresenta a ordem de complexidade correta na notação O-grande para um dos algoritmos é a C: Cbusca possui complexidade O(N⁴), pois N⁴ domina N. Abusca, por sua vez, possui complexidade O(N) (e não O(2N), pois constantes são desconsideradas na notação). Portanto, a resposta correta é a letra C.
A banca testa o conhecimento do aluno sobre a análise assintótica: em Big-O, eliminam-se constantes multiplicativas e termos de menor ordem. Abusca executa 2N + log₂(N) operações → o termo dominante é 2N, mas a notação simplifica para O(N). Cbusca executa N⁴ + N operações → termo dominante N⁴, resultando em O(N⁴).
Afirma que Cbusca possui complexidade O(N). Na verdade, a complexidade de Cbusca é O(N⁴), pois o termo N⁴ cresce muito mais rápido que N. O(N) é a complexidade de Abusca (após simplificações).
Alternativa B — ❌ Incorreta
Afirma que Abusca possui complexidade O(2N). Embora 2N seja o termo dominante, a notação O-grande ignora constantes multiplicativas. O correto é O(N). Apresentar O(2N) não é a forma padronizada, e a banca considera essa alternativa errada por não simplificar a expressão.
Alternativa C — ✅ Correta ⟵ GABARITO
Afirma que Cbusca possui complexidade O(N⁴), o que está correto. O termo N⁴ domina o termo N, e a notação O-grande é aplicada adequadamente.
Alternativa D — ❌ Incorreta
Afirma que Cbusca possui complexidade O(3N), o que é falso. Cbusca é O(N⁴), e a constante 3 não aparece em sua função de complexidade.
Alternativa E — ❌ Incorreta
Afirma que Abusca possui complexidade O(log N), o que é falso. O termo dominante é linear (2N), e não logarítmico. A complexidade correta de Abusca é O(N).
SE LIGUE NESSA!
A notação O-grande (Big-O) descreve o comportamento assintótico superior de uma função. Ela despreza constantes multiplicativas e termos de menor ordem. Assim, uma função como 2N + log₂(N) é classificada como O(N), e não O(2N) ou O(log N).