Questões de Concurso Público BNDES 2024 para Analista - Análise de Sistemas - Desenvolvimento (Manhã)

Determinada empresa venceu a licitação de uma secretaria de transportes municipal para a implementação de um software que faz o cálculo da melhor rota, dentre diversas possíveis, para que o ônibus da prefeitura ligue os pontos inicial e final da linha mais frequentada com distância percorrida mínima.

Nesse contexto, o responsável pelo projeto resolveu utilizar um algoritmo consagrado de caminho mínimo, o algoritmo de

Considere os seguintes algoritmos, todos com complexidade assintótica O(n):

Algoritmo 1: executa uma iteração simples sobre uma lista de tamanho n.

Algoritmo 2: executa duas iterações simples sobre uma lista de tamanho n, uma após a outra.

Algoritmo 3: executa uma iteração simples sobre uma lista de tamanho n, mas a iteração interna realiza uma operação constante que leva t_C tempo.

Algoritmo 4: executa uma iteração sobre uma lista de tamanho n e, dentro dessa iteração, realiza uma operação constante k vezes, em que o tempo total das operações é k * t_D e(k * t_D > t_C).

Algoritmo 5: executa uma iteração simples sobre uma lista de tamanho n, mas a iteração interna realiza uma operação com complexidade O(1).

Qual dos algoritmos é menos eficiente em termos de tempo de execução, embora todos tenham a mesma complexidade assintótica O(n)?

Considere o seguinte código em uma linguagem de programação hipotética que possui função de hashing.

Considerando-se esse código, sobre o hashing, verifica-se que a(o)