Considere que um conjunto é uma coleção de elementos distintos, não ordenados e não indexados, ou seja, não é possível acessar um elemento em um conjunto por meio de um índice. Os elementos são adicionados ao conjunto e, caso já existam no conjunto, não são adicionados novamente. Também é possível remover elementos de um conjunto. Implemente uma função aceita como parâmetro dois conjuntos disjuntos S1 e S2 e retorne um conjunto S = S1 U S2, consistindo de todos os elementos de S1 e S2. Calcule a complexidade temporal e espacial desta operação.
Passo 1
O que o enunciado pede e quais são os dados dados:
- O enunciado pede que se implemente uma função que, dados dois conjuntos disjuntos
e , retorne o conjunto (a união), contendo todos os elementos de e de . - Dados relevantes que vamos usar:
-
e são conjuntos disjuntos (ou seja, ; não há elementos em comum). - Vamos denotar
e os tamanhos (número de elementos) de cada conjunto.
-
- O enunciado também pede para calcular a complexidade temporal e espacial dessa operação.
Passo 2
Entendendo o que é um conjunto em termos de implementação (intuição prática, para a prova):
- Conceito abstrato: um conjunto armazena elementos distintos, sem ordem e sem índice.
- Implementações comuns de conjuntos em programação:
- Tabela de espalhamento (hash table / hash set): operações típicas de busca/inserção/remoção são, em média,
por operação. É a implementação mais usada quando se quer operações rápidas. - Árvore balanceada (por exemplo, red-black tree): inserção/busca/remover em
. - Estruturas especiais (bitset, vetor booleano) quando o universo é pequeno e indexável.
- Tabela de espalhamento (hash table / hash set): operações típicas de busca/inserção/remoção são, em média,
- Para essa questão vamos adotar a implementação mais comum e simples para provas/prática: conjunto baseado em hash (hash set). Isso torna a explicação direta e o raciocínio sobre complexidade claro.
Passo 3
Ideia do algoritmo (explicação verbal, passo a passo):
- Como
e são disjuntos, nenhum elemento de já está em . Logo a união pode ser obtida simplesmente juntando todos os elementos de e todos os elementos de . - Duas formas práticas:
A) Criar um novo conjunto, inserir todos os elementos de e depois todos os de , e retornar .
B) Modificarin-place: inserir em todos os elementos de e retornar (economiza espaço extra). - Como os conjuntos são disjuntos, ao inserir elementos de
não haverá verificações de duplicatas removendo elementos — a implementação do conjunto ainda fará a verificação interna, mas sabemos logicamente que não haverá colisões por igualdade.
Passo 4
Implementação (código) — abordagem clara e direta (cria um novo conjunto):
- Exemplo em Python (usando set, que é um hash set). O código abaixo é curto e prático; funciona na prova se for permitido pseudocódigo/linguagem de alto nível.
def union_disjoint(S1, S2):
S = set(S1) # copia todos os elementos de S1 para S
S.update(S2) # adiciona todos os elementos de S2 a S
return S
S = set(S1) # copia todos os elementos de S1 para S
S.update(S2) # adiciona todos os elementos de S2 a S
return S
- Observações sobre o código:
set(S1)cria uma cópia contendoelementos. update(S2)insere oselementos de no conjunto S.- Como
e são disjuntos, cada inserção de S2realmente adiciona um novo elemento (sem substituir iguais).
Passo 5
Análise temporal detalhada (tempo de execução):
- Vamos contar operações, assumindo a implementação por hash set e análise média (caso típico usado em provas e em prática):
- Copiar
para o novo conjunto: são inserções (ou uma cópia linear), custo médio . - Inserir os
elementos de : cada inserção em média custa , total . - Logo o tempo total médio é
.
- Copiar
- Caso se opte por modificar
in-place (sem criar um novo conjunto): - Basta fazer, para cada elemento de
, inserir em : tempo médio . - Porém, a memória usada já inclui
com elementos, então este método usa menos espaço extra.
- Basta fazer, para cada elemento de
- Sobre o pior caso teórico:
- Em situações adversas de hashing (colisões massivas), a inserção pode degradar e o pior caso pode ser muito maior; em implementações ingênuas com encadeamento, inserir
itens pode chegar a no pior caso. Em provas costuma-se responder pelo caso médio para hash sets, e mencionar que o pior caso do hash pode ser mais custoso.
- Em situações adversas de hashing (colisões massivas), a inserção pode degradar e o pior caso pode ser muito maior; em implementações ingênuas com encadeamento, inserir
- Alternativa: se o conjunto for implementado por árvore balanceada, cada inserção custa
(onde é o tamanho atual), então unir custaria ou, de forma simplificada, .
Passo 6
Análise espacial detalhada (uso de memória):
- Usando a estratégia que cria um novo conjunto
: - É necessário armazenar todos os elementos finais:
elementos. Então a memória final ocupada por é . - Além disso, há custo extra temporário para a cópia (dependendo da linguagem), mas em termos assintóticos o espaço adicional além de
é ou se a criação da cópia interna exigir buffers, porém normalmente consideramos o espaço extra adicional como para o conjunto resultante e extra auxiliar.
- É necessário armazenar todos os elementos finais:
- Usando a estratégia in-place (modificar
): - Não é necessário criar uma nova estrutura que contenha todos os elementos; apenas se adicionam
elementos a . - Espaço extra auxiliar além dos elementos finais é
(constante), e a memória total usada após a operação é (porque passa a ter elementos).
- Não é necessário criar uma nova estrutura que contenha todos os elementos; apenas se adicionam
- Resumindo: a operação necessita, no resultado, espaço para
elementos; o overhead extra depende se cria novo conjunto ou faz in-place.
Passo 7
Observações finais, dicas para a prova (curto e prático):
- Se o enunciado permitir modificar
, indique a opção in-place — é a mais econômica em espaço extra e tem tempo em média. - Se não puder modificar
(ou quiser manter imutabilidade), crie uma nova estrutura: tempo e espaço . - Em respostas de prova, deixe explícito que
e e escreva as complexidades em função desses valores.
Resposta
def union_disjoint(S1, S2):
S = set(S1)
S.update(S2)
return S
S = set(S1)
S.update(S2)
return S
Tempo (caso médio, hash set):
Espaço (para o conjunto resultado):
Espaço (para o conjunto resultado):