Zhrnutie na Dynamické dátové štruktúry a algoritmy
Dynamické dátové štruktúry a algoritmy – Kompletný prehľad
Úvod
Dátové štruktúry sú spôsoby, ako organizovať a ukladať dáta tak, aby sa s nimi dalo efektívne pracovať. Tento materiál pokrýva kľúčové pojmy a štruktúry používané pri práci s množinami, grafmi, hašovaním a analýzou zložitosti. Cieľom je vysvetliť princípy, ukázať praktické príklady a porovnať riešenia pri konkrétnych úlohách.
Definícia: Dátová štruktúra je spôsob usporiadania a ukladania dát, ktorý umožňuje efektívne vykonávať operácie ako vloženie, vyhľadanie alebo odstránenie.
Grafy
Základná definícia
Definícia: Graf je dvojica $G = (V, E)$, kde $V$ je množina vrcholov a $E$ je množina hrán medzi týmito vrcholmi.
- Vrchol predstavuje objekt; hrana predstavuje vzťah medzi dvoma vrcholmi.
- Príklad: mestá ako vrcholy a cesty ako hrany.
Typy grafov
- Neorientovaný graf: hrany nemajú smer. Hrana medzi $A$ a $B$ znamená spojenie v oboch smeroch (A — B). Použitie: cestné siete, mapy.
- Orientovaný graf (digraf): hrany majú smer. Hrana sa zapisuje ako usporiadaná dvojica, napr. $A \to B$. To znamená spojenie z $A$ do $B$, nie nevyhnutne opačne. Použitie: závislosti úloh, some siete.
Reprezentácie grafov
- Zoznam susedov
- Každý vrchol uchováva zoznam priamo susedných vrcholov.
- Výhoda: menšia pamäťová náročnosť pri riedkych grafoch.
- Nevýhoda: pomalšie zisťovanie existencie konkrétnej hrany.
- Príklad zápisu: $A \to B, C$; $B \to A$; $C \to A$.
Prehľadávanie grafu
- DFS – Depth First Search
- Prehľadávanie do hĺbky, rekurzívne (alebo zásobníkom). Najprv sa spracuje vrchol, potom jeho susedia.
- BFS – Breadth First Search
- Prehľadávanie do šírky: najprv všetci susedia s vzdialenosťou 1, potom s vzdialenosťou 2 atď. Použitie: hľadanie najkratšej cesty v neohodnotených grafoch.
Použitie grafov
- Modelovanie dopravných sietí
- Sociálne siete
- Počítačové siete
- Plánovanie úloh a závislostí
- Vyhľadávanie najkratšej cesty
Množiny (ADT)
Definícia: Množina je abstraktný dátový typ obsahujúci neusporiadané prvky bez opakovania.
Základné operácie
- vloženie prvku
- odstránenie prvku
- zistenie príslušnosti prvku
- zjednotenie množín
- prienik množín
- rozdiel množín
Množinu možno implementovať rôznymi spôsobmi, ktoré sa líšia v časovej a pamäťovej zložitosti.
Reprezentácia množín
-
Bitový vektor
-
Pole bitov, kde každý bit reprezentuje jeden prvok univerzálnej množiny.
-
Hodnota $1$ znamená, že prvok je v množine; $0$ znamená, že v množine nie je.
-
Príklad: univerzálna množina ${0,1,2,3,4}$ a bitový vektor
index: 0,1,2,3,4
bit: 1,0,1,0,1
reprezentovaná množina: ${0,2,4}$
-
Výhody: veľmi rýchle operácie množinových operácií (bitové operácie).
-
Nevýhody: neefektívne pri veľkých univerzálnych množinách alebo pri riedkom výskyte prvkov.
-
-
Pole
- Ukladanie prvkov v poli, napr. $[5,8,12,20]$.
- Operácie: vloženie (pridanie), vyhľadanie (lineárne), odstránenie (nájdenie a vymazanie).
- Časová zložitosť: vyhľadanie $O(n)$, vloženie $O(1)$ (ak je miesto), odstránenie $O(n)$.
- Výhody: jednoduchá implementácia. Nevýhody: pomalé vyhľadávanie.
-
Spájaný zoznam
- Každý prvok je uzol s hodnotou a odkazom na ďalší prvok.
- Operácie: vloženie na začiatok $O(1)$, vyhľadanie $O(n)$, odstránenie $O(n)$.
- Výhody: dynamická veľkosť, jednoduché vkladanie. Nevýhody: pomalé vyhľadávanie.
Poznámka: Informácie o stromových reprezentáciách množín sú spracované inde, preto sú vynechané v tomto materiáli.
Hašovanie a hašovacie tabuľky
Definícia: Hašovanie je technika, pri ktorej sa kľúč pomocou hašovacej funkcie mapuje priamo na pozíciu v tabuľke.
Hašovacia funkcia
- Príklad jednoduchého hašu: $h(k) = k \bmod m$, kde $m$ je veľkosť tabuľky.
- Ilustrácia: $h(27) = 27 \bmod 10 = 7$.
- Dobrý haš rovnomerne rozdeľuje prvky, minimalizuje kolízie a je rýchly
Zaregistruj sa pre celé zhrnutieUž máš účet? Prihlásiť sa
Dátové štruktúry - prehľad
Klíčové pojmy: Graf je $G=(V,E)$: vrcholy $V$, hrany $E$, Neorientovaný graf: hrana bez smeru, orientovaný: $A \to B$, Zoznam susedov šetrí pamäť, hľadanie hrany môže byť pomalé, BFS nájde najkratšiu cestu v neohodnotených grafoch, DFS prehľadáva do hĺbky, Množina (ADT): vloženie, odstránenie, príslušnosť, zjednotenie, prienik, rozdiel, Bitový vektor reprezentuje množinu ako pole bitov, vhodné pre malé univerzum, Hašovacia tabuľka: $h(k)=k \bmod m$ príklad, priemerný čas operácií takmer $O(1)$, Kolízie riešime reťazením (zoznamy) alebo otvoreným adresovaním, Merge Sort: $T(n)=2T(n/2)+O(n)$ ⇒ $O(n\log n)$, pamäť $O(n)$, Quick Sort: priemer $O(n\log n)$, worst $O(n^2)$, pamäť $O(\log n)$, Dolná hranica porovnávacieho triedenia je $\Omega(n\log n)$