Kaj je množica in kakšne probleme rešuje?

Question

Accepted Answer

**Množica** (set) je neurejena zbirka **edinstvenih** elementov. Njena glavna prednost je odgovore na vprašanje "je X tukaj?" v **povprečnem O(1)**, in samodejno zavrne podvojene elemente.

## Primer

```python
seen = set()
seen.add('a')
seen.add('a')          # ignored — already present
print(len(seen))       # 1
'a' in seen            # O(1) average membership test

# Set algebra
a = {1, 2, 3}
b = {2, 3, 4}
a & b                  # intersection -> {2, 3}
a | b                  # union        -> {1, 2, 3, 4}
a - b                  # difference   -> {1}
```

Večina množic je implementirana kot **hash set** (hash tabela, ki shranjuje samo ključe), zato:

| Operacija | Povprečje |
|---|---|
| add | O(1) |
| remove | O(1) |
| pripadnost (`in`) | O(1) |

## Pogosti primeri uporabe

- **Odstranjevanje podvojenih** — odpravi podvojene elemente iz seznama v eni vrstici.
- **Hitra preverjanja pripadnosti** — "sem to že videl?"
- **Razmerja** — presek/unija/razlika med skupinami.

## Zakaj je to pomembno

Množi naredijo "edinstvenost" in "pripadnost" preprosto in hitro, kar nadomesti počasne ugnezdene zanke nad seznami.

Pogosta trik pri razgovoru — odkrivanje podvojenih ali obiskanih vozlišč — se reducira na nekaj operacij z množico.