Questão de Algoritmos e Estrutura de Dados — Complexidade de Algoritmos — CESGRANRIO 2021
Algoritmos e Estrutura de DadosComplexidade de Algoritmos
- Código
- cg016242
- Banca
- CESGRANRIO
- Órgão
- Banco do Brasil
- Ano
- 2021
- Nível
- Médio
- Cargo
- Agente de Tecnologia
O gerente de uma agência bancária recebe, diariamente, solicitações de seus clientes com dúvidas sobre a melhor decisão para aplicações financeiras e as armazena, com um código numérico crescente, num vetor de solicitações, para respondê-las ao final do expediente. Para manter o conceito de bom atendimento, o gerente gostaria, sempre que possível, que a ordem das respostas seguisse, estritamente, a ordem de chegada das solicitações. Entretanto, há casos em que é necessário, por motivos de emergência ou por prioridade legal, localizar determinado código numérico para atender à solicitação correspondente antes das demais, “furando” a fila de espera. O gerente solicitou, então, à equipe de TI do banco, uma proposta que conciliasse essas duas necessidades. Ao estudar o problema, a equipe de TI concluiu que uma solução que mapearia diretamente essa necessidade da gerência seria permitir a realização de uma busca binária sobre o vetor de solicitações ordenado pelos seus códigos numéricos.Verificando a viabilidade dessa sugestão, o grupo de TI calculou que, se considerar a existência de N solicitações, a quantidade de iterações necessárias para localizar determinado código numérico no vetor de solitações, utilizando a busca binária, no pior caso, é
- A
log₂ N 
, em que a notação 
x 
significa maior inteiro menor ou igual a x - B1 +
log₂ N 
, em que a notação 
x 
significa maior inteiro menor ou igual a x - C1 +
log₂ N 
, em que a notação 
x 
significa menor inteiro maior ou igual a x - D2N
- E2N-¹