Considere dois conjuntos de números inteiros,
e
,
.
(a) Monte um algoritmo que utiliza uma tabela hash para testar se
é um subconjunto de
.
(b) Qual é o tempo médio de funcionamento de seu algoritmo?
(a) Monte um algoritmo que utiliza uma tabela hash para testar se
(b) Qual é o tempo médio de funcionamento de seu algoritmo?
Passo 1
O enunciado pede para testar se um conjunto S de tamanho m é subconjunto de outro conjunto T de tamanho n usando tabela hash; o conteúdo envolve operações básicas de tabela hash (inserção e busca) e vamos usar a propriedade de tempo médio O(1) dessas operações.
Passo 2
Começamos criando uma tabela hash H inicialmente vazia, que armazenará elementos de T para permitir buscas rápidas.
Passo 3
Percorremos todos os elementos de T. Para cada elemento
, fazemos a inserção em H. Cada inserção leva tempo médio constante
, logo toda esta etapa custa
.
Em seguida, percorremos cada elemento de S e fazemos uma busca em H. Se algum
não for encontrado, concluímos imediatamente que S não é subconjunto de T e paramos o algoritmo; caso todos sejam encontrados, concluímos que S é subconjunto.
Em seguida, percorremos cada elemento
Passo 4
Analisando o tempo total: a fase de inserir todos os
elementos de T custa em média
e a fase de buscar os
elementos de S custa em média
. Portanto, o tempo médio de funcionamento é
.
Resposta
O(m + n)