Zhrnutie na Dynamické dátové štruktúry a algoritmy

Dynamické Dátové Štruktúry a Algoritmy: Komplexný Sprievodca

ZhrnutieTest znalostíKartičkyPodcastMyšlienková mapa

Úvod

Dátové štruktúry sú spôsoby organizácie dát v pamäti, ktoré umožňujú efektívne vkladanie, vyhľadávanie, triedenie a mazanie prvkov. V tomto materiáli sa zameriame na lineárne dátové štruktúry (polia, spájané zoznamy, množiny) a na triediace algoritmy (Merge sort, Quick sort) a techniky vyhľadávania (binárne vyhľadávanie, hašovanie). Materiál je určený pre samoukov (Not attending student) — preto rozkladáme pojmy na menšie časti, uvádzame príklady a praktické použitia.

Definícia: Dynamické dátové štruktúry sú také dátové štruktúry, ktorých veľkosť sa môže počas behu programu meniť; prvky sa dajú pridávať, odoberať alebo prepájať.

Základné pojmy a miery zložitosti

Asymptotická časová zložitosť

  • Označenie: $T(n)$, kde $n$ je veľkosť vstupu.
  • Používaná notácia: $O(\cdot)$ (horný odhad).
  • Typické triedy: $O(1)$, $O(\log n)$, $O(n)$, $O(n\log n)$, $O(n^2)$.

Definícia: Najlepší prípad (best-case), priemerný prípad (average-case) a najhorší prípad (worst-case) opisujú správanie algoritmu vzhľadom na vstup.

Pamäťová zložitosť

  • In-place algoritmy: $O(1)$ alebo $O(\log n)$ (rekurzívny zásobník).
  • Externé algoritmy alebo pomocné pole: $O(n)$.

Triediace algoritmy (sorting)

Triedenie usporiada prvky podľa kľúča (napr. vzostupne). Sledujeme čas, pamäť a stabilitu.

Merge Sort (Divide and Conquer)

  • Postup:
    1. Rozdelí pole na dve polovice.
    2. Rekurzívne utriedi obe polovice.
    3. Spojí (merge) zoradené časti.
  • Rekurentný vzťah: $$T(n) = 2T(n/2) + O(n)$$
  • Riešenie: $$T(n) = O(n\log n)$$
  • Zložitosť: best-case $O(n\log n)$, average-case $O(n\log n)$, worst-case $O(n\log n)$.
  • Vlastnosti:
    • stabilný
    • dodatočná pamäť $O(n)$
    • vhodný pre veľké dáta a externé triedenie

Quick Sort

  • Postup:
    1. Vyberie sa pivot.
    2. Rozdelí prvky na menšie a väčšie ako pivot.
    3. Rekurzívne triedi časti.
  • Priemerný prípad: $$T(n)=2T(n/2)+O(n)$$
  • Najhorší prípad: $$T(n)=T(n-1)+O(n)$$
  • Zložitosť: best-case $O(n\log n)$, average-case $O(n\log n)$, worst-case $O(n^2)$.
  • Vlastnosti:
    • nestabilný
    • pamäť $O(\log n)$ (rekurzia)
    • veľmi rýchly v praxi (dobrá cache lokalita)

Porovnanie Merge Sort vs Quick Sort

VlastnosťMerge SortQuick Sort
Čas (avg)$O(n\log n)$$O(n\log n)$
Čas (worst)$O(n\log n)$$O(n^2)$
Pamäť$O(n)$$O(\log n)$
Stabilitaánonie
Praktické použitieexterné triedenieinterné triedenie
💡 Vedeli ste?Zajímavost: Merge sort má garantovaný čas $O(n\log n)$ bez ohľadu na vstup, zatiaľ čo Quick sort môže skĺznuť do $O(n^2)$ pri zlých pivotoch.

Odhady zložitosti — pravidlá

  • Iteratívne algoritmy: jeden cyklus → $O(n)$; dva vnorené cykly → $O(n^2)$.
  • Rekurzívne algoritmy: používame rekurentné rovnice alebo Master theorem.
  • Typický prípad rozdelenia na polovice: $\log n$ úrovní, práca na úrovni $n$ → $O(n\log n)$.

Did you know that pre porovnávacie triedenie platí dolná hranica $\Omega(n\log n)$, t.j. žiadny porovnávací algoritmus nemôže byť asymptoticky rýchlejší?

Vyhľadávanie

Binárne vyhľadávanie

  • Podmienka: pole musí byť usporiadané.
  • Postup: porovnáme s prostredným prvkom, ak menší → ľavá polovica, ak väčší → pravá polovica; opakujeme.
  • Zložitosť: best-case $O(1)$ (prvok je presne v strede), average/worst-case $O(\log n)$.
  • Výhody: rýchle vyhľadávanie; Nevýhody: potreba usporiadaného poľa.

Hašovanie (Hashing)

  • Myšlienka: pomocou hašovacej funkcie mapujeme kľúč priamo na index tabuľky.
  • Postup:
    1. Na kľúč aplikujeme hašovaciu funkciu.
    2. Funkcia vráti index v tabuľke.
    3. Na tomto indexe uložíme alebo vyhľadáme prvok.
  • Príklad hašovacej funkcie: $$h(k) = k \bmod m$$ (pre celočíselné kľúče).
  • Výhody: takmer konštantný čas operácií.
  • Nevýhody: kolízie (dva kľúče môžu mať rovnaký index).

Definícia: Kolízia nastane, keď dva rôzne kľúče mapujú na rovnaký index.

  • Riešenie kolízií: hašovanie reťazením — každá pozícia obsahuje zoznam, do ktorého sa pridávajú kolidujúce prvky.
Zaregistruj sa pre celé zhrnutie
KartičkyTest znalostíZhrnutiePodcastMyšlienková mapa
Začni zadarmo

Už máš účet? Prihlásiť sa

Dátové štruktúry – lineárne a triedenie

Klíčová slova: Dátové štruktúry - lineárne a triedenie, Dátové štruktúry - stromy a grafy

Klíčové pojmy: Dynamické dátové štruktúry menia veľkosť počas behu programu, Asymptotická zložitosť sa vyjadruje pomocou $O(\cdot)$, Merge sort má vždy $O(n\log n)$ a je stabilný, Quick sort má priemerný $O(n\log n)$, najhorší $O(n^2)$, Binárne vyhľadávanie vyžaduje usporiadané pole a má $O(\log n)$, Hašovanie poskytuje takmer konštantné operácie, rieši sa kolízia, Spájaný zoznam umožňuje vkladanie O(1) na začiatok, vyhľadanie O(n), Pole poskytuje rýchly priamy prístup, ale pomalé odstránenie, Bitový vektor je efektívny pre malé univerzálne množiny, Pri evaluácii algoritmov sledujeme čas, pamäť a stabilitu

## Úvod Dátové štruktúry sú spôsoby organizácie dát v pamäti, ktoré umožňujú efektívne vkladanie, vyhľadávanie, triedenie a mazanie prvkov. V tomto materiáli sa zameriame na **lineárne dátové štruktúry** (polia, spájané zoznamy, množiny) a na **triediace algoritmy** (Merge sort, Quick sort) a techniky vyhľadávania (binárne vyhľadávanie, hašovanie). Materiál je určený pre samoukov (Not attending student) — preto rozkladáme pojmy na menšie časti, uvádzame príklady a praktické použitia. > **Definícia:** Dynamické dátové štruktúry sú také dátové štruktúry, ktorých veľkosť sa môže počas behu programu meniť; prvky sa dajú pridávať, odoberať alebo prepájať. ## Základné pojmy a miery zložitosti ### Asymptotická časová zložitosť - Označenie: $T(n)$, kde $n$ je veľkosť vstupu. - Používaná notácia: $O(\cdot)$ (horný odhad). - Typické triedy: $O(1)$, $O(\log n)$, $O(n)$, $O(n\log n)$, $O(n^2)$. > **Definícia:** Najlepší prípad (best-case), priemerný prípad (average-case) a najhorší prípad (worst-case) opisujú správanie algoritmu vzhľadom na vstup. ### Pamäťová zložitosť - In-place algoritmy: $O(1)$ alebo $O(\log n)$ (rekurzívny zásobník). - Externé algoritmy alebo pomocné pole: $O(n)$. ## Triediace algoritmy (sorting) Triedenie usporiada prvky podľa kľúča (napr. vzostupne). Sledujeme čas, pamäť a stabilitu. ### Merge Sort (Divide and Conquer) - Postup: 1. Rozdelí pole na dve polovice. 2. Rekurzívne utriedi obe polovice. 3. Spojí (merge) zoradené časti. - Rekurentný vzťah: $$T(n) = 2T(n/2) + O(n)$$ - Riešenie: $$T(n) = O(n\log n)$$ - Zložitosť: best-case $O(n\log n)$, average-case $O(n\log n)$, worst-case $O(n\log n)$. - Vlastnosti: - stabilný - dodatočná pamäť $O(n)$ - vhodný pre veľké dáta a externé triedenie ### Quick Sort - Postup: 1. Vyberie sa pivot. 2. Rozdelí prvky na menšie a väčšie ako pivot. 3. Rekurzívne triedi časti. - Priemerný prípad: $$T(n)=2T(n/2)+O(n)$$ - Najhorší prípad: $$T(n)=T(n-1)+O(n)$$ - Zložitosť: best-case $O(n\log n)$, average-case $O(n\log n)$, worst-case $O(n^2)$. - Vlastnosti: - nestabilný - pamäť $O(\log n)$ (rekurzia) - veľmi rýchly v praxi (dobrá cache lokalita) ### Porovnanie Merge Sort vs Quick Sort | Vlastnosť | Merge Sort | Quick Sort | |---|---:|---:| | Čas (avg) | $O(n\log n)$ | $O(n\log n)$ | | Čas (worst) | $O(n\log n)$ | $O(n^2)$ | | Pamäť | $O(n)$ | $O(\log n)$ | | Stabilita | áno | nie | | Praktické použitie | externé triedenie | interné triedenie | Zajímavost: Merge sort má garantovaný čas $O(n\log n)$ bez ohľadu na vstup, zatiaľ čo Quick sort môže skĺznuť do $O(n^2)$ pri zlých pivotoch. ## Odhady zložitosti — pravidlá - Iteratívne algoritmy: jeden cyklus → $O(n)$; dva vnorené cykly → $O(n^2)$. - Rekurzívne algoritmy: používame rekurentné rovnice alebo Master theorem. - Typický prípad rozdelenia na polovice: $\log n$ úrovní, práca na úrovni $n$ → $O(n\log n)$. > **Did you know** that pre porovnávacie triedenie platí dolná hranica $\Omega(n\log n)$, t.j. žiadny porovnávací algoritmus nemôže byť asymptoticky rýchlejší? ## Vyhľadávanie ### Binárne vyhľadávanie - Podmienka: pole musí byť usporiadané. - Postup: porovnáme s prostredným prvkom, ak menší → ľavá polovica, ak väčší → pravá polovica; opakujeme. - Zložitosť: best-case $O(1)$ (prvok je presne v strede), average/worst-case $O(\log n)$. - Výhody: rýchle vyhľadávanie; Nevýhody: potreba usporiadaného poľa. ### Hašovanie (Hashing) - Myšlienka: pomocou hašovacej funkcie mapujeme kľúč priamo na index tabuľky. - Postup: 1. Na kľúč aplikujeme hašovaciu funkciu. 2. Funkcia vráti index v tabuľke. 3. Na tomto indexe uložíme alebo vyhľadáme prvok. - Príklad hašovacej funkcie: $$h(k) = k \bmod m$$ (pre celočíselné kľúče). - Výhody: takmer konštantný čas operácií. - Nevýhody: kolízie (dva kľúče môžu mať rovnaký index). > **Definícia:** Kolízia nastane, keď dva rôzne kľúče mapujú na rovnaký index. - Riešenie kolízií: hašovanie reťazením — každá pozícia obsahuje zoznam, do ktorého sa pridávajú kolidujúce prvky.