Considere dois conjuntos de números inteiros, m <= n e S, T.
(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?

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 ti, fazemos a inserção em H. Cada inserção leva tempo médio constante O(1), logo toda esta etapa custa O(n).
Em seguida, percorremos cada elemento sj de S e fazemos uma busca em H. Se algum sj 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.

Passo 4

Analisando o tempo total: a fase de inserir todos os n elementos de T custa em média O(n) e a fase de buscar os m elementos de S custa em média O(m). Portanto, o tempo médio de funcionamento é O(n + m).

Resposta

O(m + n)

Exercícios relacionados