GabaritoB — N
Gabarito: letra B. A contagem de elementos iguais a zero em um array unidimensional exige percorrer todos os N elementos uma única vez, resultando em complexidade linear O(N). Nenhum outro fator altera essa análise — a cada elemento verifica-se se é zero, operação de tempo constante, totalizando N operações.
A questão testa o entendimento básico de análise assintótica: para contar ocorrências em um vetor não ordenado, não há como evitar visitar cada posição ao menos uma vez. Isso contrasta com algoritmos como busca binária (que exigem ordenação) ou ordenação (O(N log N) ou O(N²)).
Complexidade constante O(1). Para contar zeros, é impossível saber o resultado sem examinar todos os elementos. Exceto se o array já for conhecido, o que não é o caso.
Complexidade linear O(N). O algoritmo executa uma iteração sobre todo o array, verificando cada elemento. A operação de comparação e incremento é de tempo constante, portanto o custo total é proporcional a N.
Complexidade quadrática O(N²). Isso ocorreria, por exemplo, com dois loops aninhados (comparar cada par de elementos), mas a contagem simples não exige tal estrutura.
Complexidade O(N log N). É típica de algoritmos de ordenação eficientes (merge sort, quicksort) ou de divisão e conquista. A contagem não requer ordenação ou divisão recursiva.
Complexidade 2N. Embora assintoticamente seja O(N) (constantes são desprezadas na notação Big O), a alternativa oferece um valor exato, e a análise padrão simplifica para N. Além disso, o algoritmo conta zeros com uma única passada, não duas. Se cada elemento fosse verificado duas vezes, ainda seria linear, mas a banca considera que a resposta correta é simplesmente N.
Em análise de complexidade, lembre-se: contagem de elementos em um array não ordenado é sempre O(N) — você precisa percorrer todos os dados. Compare com busca de um elemento (pode ser O(1) em hash, O(log N) em árvore balanceada, O(N) em lista linear).
Gabarito: letra B
Link permanente: /questoes/fg054947