Kaip maišytuvai optimizuoja algoritmus?

Question

Accepted Answer

**Maišytuvas** (žodynas) suteikia **O(1) vidutinį** paieškos, įterpimo ir ištrynimo laiką. Keičiant O(n) atmintį į greitį, daugelį O(n²) algoritmų paverčiama O(n), pakeičiant pakartotines skenavimus momentinėmis paieško.

## Idėja

Vietoj to, kad kiekvieną kartą ieškotumėte sąraše, saugokite rastus reikšmes maišytuve ir patikrinkite narystę pastoviu laiku.

## Pavyzdys: dviejų skaičių suma per O(n)

```python
def two_sum(nums, target):
    seen = {}                          # value -> index
    for i, x in enumerate(nums):
        need = target - x
        if need in seen:               # O(1) lookup
            return (seen[need], i)
        seen[x] = i
    return None

two_sum([2, 7, 11, 15], 9)             # -> (0, 1)
```

Be žemėlapio tai O(n²); su juo — vienas praėjimas.

## Pagrindiniai naudojimo atvejai

- **Deduplikacija / narystė** su aibe.
- **Dažnio skaičiavimas** (`Counter`).
- **Grupavimas / indeksavimas** pagal raktą.
- **Talpinimas / memoizacija** rezultatų.

## Sudėtingumas

- **Vidutiniškai:** O(1) kiekvienai operacijai. **Blogiausias:** O(n) esant daug susidūrimų. **Vieta:** O(n).

## Spąstai

Raktai turi būti **maišytini** ir nekeičiami. Blogiausio atveju susidūrimai sumažina našumą. Maišytuvai nėra sutvarkytų (jei tvarka svarbi, naudokite sutvarkytus variantus).

## Kodėl tai svarbu

Maišymas yra dažniausiai taikomas optimizavimas kodavimo pokalbiuose ir realiosiose sistemose — jis paverčia "ieškoti iš naujo" į "paieško kartą".

Atminties ir laiko mainai yra nuolatinis inžinerinis svirtis.

Dažnio skaičiavimas, talpinimas ir indeksavimas — visa tai remiasi šia viena idėja.