Conjuntos y multiconjuntos

Un conjunto: hash table de llaves — membresía O(1), sin duplicados. Un multiconjunto: llaves con conteos.

Dos preguntas, respondidas en O(1)

• Conjunto — "¿ya vi esto?" (membresía, dedup)
• Multiconjunto — "¿cuántos hay de cada uno?" (conteo)
• Más un álgebra: unión, intersección, diferencia
• Todo construido sobre membresía O(1)

Mira una intersección

Sondea cada elemento de A para ver si está en B. 1,2,3 fallan; 4,5,6 aciertan → A ∩ B = {4,5,6}. Cada sondeo O(1).

Complejidad

• agregar / contiene / eliminar: O(1) promedio
• unión: O(n+m) · intersección: O(el más chico) · diferencia: O(n)
• x in list es O(n); x in set es O(1)

El patrón del conjunto de vistos

Registra lo que ya viste → convierte recorridos O(n²) en O(n). El truco más útil del libro.

Para llevar

Membresía en O(1) → dedup, "ya lo vi", conteos. Sin orden, sin duplicados. Siguiente bloque: recursión y ordenamiento.