Question

A área de complexidade de algoritmos abrange a medição da eficiência de um algoritmo frente à quantidade de operações realizadas até que ele encontre seu resultado final.

A respeito desse contexto, suponha que um arquivo texto contenha o nome de N cidades de determinado estado, que cada nome de cidade esteja separado do seguinte por um caracter especial de fim de linha e classificado em ordem alfabética crescente. Considere um programa que realize a leitura linha a linha desse arquivo, à procura de nome de cidade

Com base nessa descrição, verifica-se que a complexidade desse programa


Escolha uma:
a. O(1), em caso de busca sequencial.
b. O(N), em caso de busca sequencial.
c. O(log2N)O(log2⁡N), em caso de busca binária.
d. O(N), em caso de transferência dos nomes para uma árvore binária e, então, realizar a busca.
e. O(log2N)O(log2⁡N), em caso de transferência dos nomes para uma árvore binária e, então, realizar a busca.

Answer 1

Resposta:

O(N), em caso de busca sequencial.

Explicação:

Como o programa faz a leitura linha a linha, então trata-se de uma busca sequencial (ou linear), que verifica cada elemento do conjunto de dados (lista de nomes) até encontrar o elemento procurado. Tal busca tem complexidade O(n). Logo, a alternativa correta é a B.

Source: blogcyberini