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
1 é complexidade constante, mas contar zeros exige percorrer o array inteiro, então o custo não fica fixo.
- B)N
Correta, porque a contagem é feita em uma única passagem pelo vetor, resultando em complexidade linear O(N).
- C)N2
N2 seria custo quadrático, o que aconteceria se houvesse processamento de todos contra todos, e não numa simples varredura.
- D)N log N
N log N costuma aparecer em algoritmos de ordenação eficientes, não em uma contagem simples de elementos.
- E)2N
2N também representa comportamento linear, mas a notação assintótica simplifica constantes, então o correto é O(N), não 2N.
Gabarito: B
Quando a questão fala em contar quantos elementos de um array são iguais a zero, você não precisa ordenar, buscar em árvore, nem fazer mágica de algoritmo. Basta percorrer o vetor uma vez e verificar cada posição, incrementando um contador sempre que encontrar o valor 0. Isso faz com que o trabalho cresça de forma linear com o tamanho de X. Se o array tem N elementos, o algoritmo examina cada um deles uma única vez. Logo, a complexidade é O(N). Em prova, a banca costuma cobrar essa ideia simples: se você só faz uma passada sequencial, o custo é proporcional ao número de itens analisados. Por isso o gabarito B está correto. Não há comparação entre todos os pares, não há divisão recursiva, nem qualquer etapa que multiplique o esforço. É o clássico caso de varredura linear: rápido de escrever, elegante e bem menos dramático do que parece. Em resumo: contar zeros em um array desordenado exige olhar elemento por elemento. Isso é complexidade linear, ou seja, O(N).