Questão 5605678

• Banca: FGV
• Órgão: Banestes
• Ano: 2021
• Provas: FGV - 2021 - Banestes - Analista em Tecnologia da Informação - Desenvolvimento de Sistemas; FGV - 2021 - Banestes - Analista em Tecnologia da Informação - Segurança da Informação; FGV - 2021 - Banestes - Analista em Tecnologia da Informação - Suporte e Infraestrutura
• Disciplina: Algoritmos e Estrutura de Dados
• Assuntos: Algoritmos; Complexidade de Algoritmos

João pretende armazenar uma coleção de dados referentes a cerca de um milhão de pessoas. Cada pessoa tem como chave de acesso um número inteiro sequencial, que não se repete.

Empregando uma estrutura de Tabela Hash, João conseguiria obter, praticamente, acesso com complexidade:

• A. O(1)
• B. O(log N)
• C. O(N)
• D. O(N log N)
• E. O(N²)

Gabarito: A

Comentários

• Gab A. A implementação típica busca uma função hash que seja de complexidade O(1), não importando o número de registros na tabela (desconsiderando colisões). O ganho com relação a outras estruturas associativas (como um vetor simples) passa a ser maior conforme a quantidade de dados aumenta.