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 S_1 e S_2, retorne o conjunto S = S_1 \cup S_2 (a união), contendo todos os elementos de S_1 e de S_2.
  • Dados relevantes que vamos usar:
    • S_1 e S_2 são conjuntos disjuntos (ou seja, S_1 \cap S_2 = \varnothing; não há elementos em comum).
    • Vamos denotar n_1 = |S_1| e n_2 = |S_2| 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:
    1. Tabela de espalhamento (hash table / hash set): operações típicas de busca/inserção/remoção são, em média, O(1) por operação. É a implementação mais usada quando se quer operações rápidas.
    2. Árvore balanceada (por exemplo, red-black tree): inserção/busca/remover em O(\log n).
    3. Estruturas especiais (bitset, vetor booleano) quando o universo é pequeno e indexável.
  • 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 S_1 e S_2 são disjuntos, nenhum elemento de S_2 já está em S_1. Logo a união pode ser obtida simplesmente juntando todos os elementos de S_1 e todos os elementos de S_2.
  • Duas formas práticas:
    A) Criar um novo conjunto S, inserir todos os elementos de S_1 e depois todos os de S_2, e retornar S.
    B) Modificar S_1 in-place: inserir em S_1 todos os elementos de S_2 e retornar S_1 (economiza espaço extra).
  • Como os conjuntos são disjuntos, ao inserir elementos de S_2 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
  • Observações sobre o código:
    • set(S1) cria uma cópia contendo n_1 elementos.
    • update(S2) insere os n_2 elementos de S_2 no conjunto S.
    • Como S_1 e S_2 são disjuntos, cada inserção de S2 realmente 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 S_1 para o novo conjunto: são n_1 inserções (ou uma cópia linear), custo médio O(n_1).
    • Inserir os n_2 elementos de S_2: cada inserção em média custa O(1), total O(n_2).
    • Logo o tempo total médio é O(n_1 + n_2).
  • Caso se opte por modificar S_1 in-place (sem criar um novo conjunto):
    • Basta fazer, para cada elemento de S_2, inserir em S_1: tempo médio O(n_2).
    • Porém, a memória usada já inclui S_1 com n_1 elementos, então este método usa menos espaço extra.
  • 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 k itens pode chegar a O(k^2) no pior caso. Em provas costuma-se responder pelo caso médio O(n_1+n_2) para hash sets, e mencionar que o pior caso do hash pode ser mais custoso.
  • Alternativa: se o conjunto for implementado por árvore balanceada, cada inserção custa O(\log m) (onde m é o tamanho atual), então unir custaria O(n_1\log n_1 + n_2\log(n_1+n_2)) ou, de forma simplificada, O((n_1+n_2)\log(n_1+n_2)).

Passo 6

Análise espacial detalhada (uso de memória):
  • Usando a estratégia que cria um novo conjunto S:
    • É necessário armazenar todos os elementos finais: n_1 + n_2 elementos. Então a memória final ocupada por S é O(n_1 + n_2).
    • 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 S é O(1) ou O(n_1) se a criação da cópia interna exigir buffers, porém normalmente consideramos o espaço extra adicional como O(n_1 + n_2) para o conjunto resultante e O(1) extra auxiliar.
  • Usando a estratégia in-place (modificar S_1):
    • Não é necessário criar uma nova estrutura que contenha todos os elementos; apenas se adicionam n_2 elementos a S_1.
    • Espaço extra auxiliar além dos elementos finais é O(1) (constante), e a memória total usada após a operação é O(n_1 + n_2) (porque S_1 passa a ter n_1+n_2 elementos).
  • Resumindo: a operação necessita, no resultado, espaço para n_1+n_2 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 S_1, indique a opção in-place — é a mais econômica em espaço extra e tem tempo O(n_2) em média.
  • Se não puder modificar S_1 (ou quiser manter imutabilidade), crie uma nova estrutura: tempo O(n_1 + n_2) e espaço O(n_1 + n_2).
  • Em respostas de prova, deixe explícito que n_1 = |S_1| e n_2 = |S_2| e escreva as complexidades em função desses valores.

Resposta

def union_disjoint(S1, S2):
S = set(S1)
S.update(S2)
return S
Tempo (caso médio, hash set): O(n_1 + n_2)
Espaço (para o conjunto resultado): O(n_1 + n_2)

Exercícios relacionados