Matemática · FGV · 2024 | Questão sqc-fg086268

MatemáticaAlgoritmo

Código: fg086268
Banca: FGV
Órgão: INPE
Ano: 2024
Nível: Superior

Cargo: Tecnologista Pleno I - Desenvolvimento ou Aprimoramento de Sistema de Assimilação de Dados nas Componentes do Sistema Terrestre e de Aplicações para Monitoramento do Processo de Assimilação

Algoritmos para assimilação de dados geralmente envolvem cálculos complexos que dependem de diversos fatores, como o tamanho dos espaços de estados, número de pontos da grade em questão, tamanho da janela de assimilação, etc. Frequentemente, observa-se que dois algoritmos usados para solucionar um mesmo problema podem ter eficiências diferentes, por conta de diferenças em suas implementações.Uma maneira de se mensurar e representar a complexidade de um algoritmo é contabilizar o número de operações de ponto-flutuante (flops) necessárias para executá-lo e utilizar a notação “O-grande”.Considere o algoritmo a seguir, implementado em uma linguagem de pseudocódigo autoexplicativa. Imagem associada para resolução da questão

Imagem associada para resolução da questão

A complexidade desse algoritmo será

AO (2n²).
BO (2n² − 1).
CO (n²).
DO (n).
EO (n² − n − 1).

Revelar gabarito e comentário

GabaritoC — 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 C. A complexidade do algoritmo é $O(n^2)$ porque ele utiliza dois laços de repetição aninhados, cada um executando $n$ vezes, resultando em um total de $n \times n = n^2$ operações elementares no corpo do laço.

Para determinar a complexidade de um algoritmo usando a notação O-grande, focamos no termo dominante que descreve como o tempo de execução cresce em relação ao tamanho da entrada ( $n$ ). No pseudocódigo fornecido:

O laço externo (linha 9) percorre o índice $i$ de $1$ até $n$ .
O laço interno (linha 10) percorre o índice $j$ de $1$ até $n$ .
A operação na linha 11 (uma multiplicação e uma soma) é executada para cada par $(i, j)$ , totalizando $n^2$ execuções.

Na notação assintótica, constantes multiplicativas e termos de ordem inferior são desprezados, pois o foco é o comportamento de crescimento assintótico. Assim, $O(2n^2)$ ou $O(2n^2 - 1)$ simplificam-se para $O(n^2)$ .

1Identificar laços aninhados
2Contar execuções do corpo
3n × n = n² operações
4Desprezar constantes e termos inferiores
5Resultado: O(n²)

LEVEL · soulevel.com.br

Alternativa A — ❌ Incorreta

Embora o número de operações possa ser proporcional a $2n^2$ (se contarmos separadamente a multiplicação e a soma), a notação O-grande ignora constantes multiplicativas. Portanto, $O(2n^2)$ é equivalente a $O(n^2)$ , mas a forma canônica e simplificada é preferida.

Alternativa B — ❌ Incorreta

A notação O-grande não inclui termos de ordem inferior ou constantes, como o $-1$ . A complexidade assintótica descreve o limite superior do crescimento, não o número exato de operações.

Alternativa C — ✅ Correta ⟵ GABARITO

Esta alternativa apresenta a forma simplificada e correta da complexidade do algoritmo, que é quadrática em relação ao tamanho da entrada $n$ .

Alternativa D — ❌ Incorreta

Esta alternativa descreve uma complexidade linear, o que ocorreria apenas se houvesse um único laço de repetição percorrendo a matriz, e não dois laços aninhados.

Alternativa E — ❌ Incorreta

Esta alternativa inclui termos de ordem inferior ( $-n$ e $-1$ ), que são descartados na notação O-grande, pois não afetam o comportamento de crescimento assintótico do algoritmo para valores grandes de $n$ .

PEGA ESSA DICA!

Ao analisar a complexidade de algoritmos, sempre identifique o número de laços aninhados. Laços simples resultam em $O(n)$ , laços duplos aninhados resultam em $O(n^2)$ , e assim por diante. Ignore constantes e termos de menor grau ao definir a notação O-grande.

Link permanente: /questoes/fg086268