Questão de Tecnologia da Informação · FGV TCE-TO 2022 (nº 37)

A complexidade de um algoritmo é uma medida de como o tempo de execução ou o espaço em memória que ele consome cresce à medida que o tamanho da entrada (geralmente denotado por $N$) aumenta. Usamos a notação Big O ($O$) para expressar essa taxa de crescimento no pior caso.

(A) Incorreta: A complexidade $O(1)$ (constante) significa que o tempo de execução é fixo, independentemente do tamanho do array. Para contar zeros, é preciso olhar cada elemento, então o tempo varia com o tamanho do array.
(B) Correta: A complexidade $O(N)$ (linear) significa que o tempo de execução cresce proporcionalmente ao número de elementos $N$ no array. Para contar todos os zeros em um array não ordenado, o algoritmo precisa, no pior caso, inspecionar cada um dos $N$ elementos uma única vez. Se o array tem $N$ elementos, ele fará aproximadamente $N$ operações de comparação, o que caracteriza uma complexidade linear.
(C) Incorreta: A complexidade $O(N^2)$ (quadrática) indica que o tempo cresce com o quadrado do número de elementos. Isso geralmente ocorre com loops aninhados (um loop dentro do outro), o que não é necessário para uma simples contagem.
(D) Incorreta: A complexidade $O(N \log N)$ é comum em algoritmos de ordenação eficientes ou busca em estruturas de dados específicas. Contar elementos em um array não ordenado não se beneficia desse tipo de abordagem.
(E) Incorreta: A complexidade $O(2^N)$ (exponencial) representa um crescimento extremamente rápido e é típica de problemas muito complexos que exigem testar muitas combinações, o que está muito além da necessidade de uma simples contagem.