FGV 2022 · Informática

Question

Dado um array unidimensional X, contendo milhares de números inteiros não ordenados, a complexidade de um algoritmo que faz a contagem de números iguais a zero presentes em X é:

A) 1
B) N
C) N2
D) N log N
E) 2N

Accepted Answer

Gabarito oficial: B. # Análise da Questão

A resposta correta é **B (N)** porque contar zeros em um array unidimensional exige uma única passagem sequencial pela estrutura. O algoritmo precisa visitar cada elemento exatamente uma vez para compará-lo com zero, resultando em operações proporcionais ao tamanho N do array. Não há otimização possível — você não pode "pular" elementos sem risco de perder uma contagem.

**Por que as alternativas erram:** A opção **A** está absurda; O(1) seria tempo constante, independente do tamanho da entrada (faria sentido apenas se o resultado já estivesse pré-calculado). **C (N²)** seria resultado de algoritmos com loops aninhados desnecessários — aqui não há. **D (N log N)** é tipicamente de algoritmos eficientes de ordenação; não se aplica a simples contagem. **E (2^N)** é complexidade exponencial, própria de problemas combinatórios; está completamente desconectada da tarefa.

O conceito testado é o de **análise assintótica** e reconhecimento de que varredura linear é a operação fundamental para leitura de dados não-indexáveis. Mesmo que o array estivesse ordenado, isso não ajudaria na contagem de zeros. A questão cobra noção básica: familiarize-se com as ordens comuns (1 < log N < N < N log N < N² < 2^N) e saiba identificar quantas vezes os dados serão processados.

Informática — FGV 2022

Mais questões de Informática

Fonte