Kaip pasirinkti tinkamą duomenų struktūrą problemai?

Question

Accepted Answer

Pasirinkite struktūrą, kurios **dažniausios operacijos yra pigiausios** jūsų prieigos šablonui. Pradėkite sąrašant operacijas, kurias atlieksite, įvertinkite jų dažnumą, tada suderinkite su struktūros stiprybėmis.

## Sprendimo kontrolinis sąrašas

```text
1. How do you access data?  by index -> array
                            by key   -> hash map
                            by order -> tree / heap
2. Need ordering?           sorted   -> balanced BST / sorted array
                            FIFO     -> queue
                            LIFO     -> stack
3. Frequent middle inserts? -> linked list
4. Need fast "seen it?"     -> set / hash map
5. Need "best/min/max next" -> heap (priority queue)
```

## Suderinkite operacijas su sudėtingumu

| Reikalinga | Geriausia struktūra | Pagrindinės op kaina |
|---|---|---|
| Atsitiktinis priėjimas pagal indeksą | dinaminė masyvas | O(1) |
| Paieška pagal raktą | hash map | O(1) vid. |
| Rūšiuota + diapazonų užklausos | balansuota BST | O(log n) |
| Min/max kartotinai | heap | O(log n) pop |
| FIFO / LIFO | eilė / krūva | O(1) |
| Priešdėlio paieška | trie | O(L) |

## Samprotavimo pavyzdys

```text
"Find the 10 most frequent words in a huge file."
 - count frequencies  -> hash map (O(1) updates)
 - keep top 10        -> min-heap of size 10 (O(log 10) per word)
```

## Kodėl tai svarbu

Tinkamas pasirinkimas dažnai yra skirtumas tarp O(n) ir O(n²) sprendimo — didžiausias našumo svirtis.

Pokalbyje dėstytojai testuoja būtent šį samprotavimą: jie nori pamatyti, kaip susieti reikalavimus su operacijos kaštais, o ne įsiminti struktūras.

Reikalinga	Geriausia struktūra	Pagrindinės op kaina
Atsitiktinis priėjimas pagal indeksą	dinaminė masyvas	O(1)
Paieška pagal raktą	hash map	O(1) vid.
Rūšiuota + diapazonų užklausos	balansuota BST	O(log n)
Min/max kartotinai	heap	O(log n) pop
FIFO / LIFO	eilė / krūva	O(1)
Priešdėlio paieška	trie	O(L)