Differences
This shows you the differences between two versions of the page.
| Both sides previous revisionPrevious revisionNext revision | Previous revision | ||
| statnice:bakalar:b4b33alg [2025/06/08 14:05] – zapleka3 | statnice:bakalar:b4b33alg [2026/06/06 17:15] (current) – [Counting Sort] knedl1k | ||
|---|---|---|---|
| Line 1: | Line 1: | ||
| - | ==== Základní algoritmy a datové struktury pro vyhledávání a řazení. Vyhledávací stromy, rozptylovací tabulky. Prohledávání grafu. Úlohy dynamického programování. Asymptotická složitost a její určování. ==== | + | ====== Základní algoritmy a datové struktury pro vyhledávání a řazení. Vyhledávací stromy, rozptylovací tabulky. Prohledávání grafu. Úlohy dynamického programování. Asymptotická složitost a její určování. |
| [[https:// | [[https:// | ||
| Line 476: | Line 476: | ||
| === Mazání === | === Mazání === | ||
| * Najdeme a odstraníme klíč (případně jej nahradíme in-order předchůdcem/ | * Najdeme a odstraníme klíč (případně jej nahradíme in-order předchůdcem/ | ||
| - | * Při návratu nahoru testujeme balance; pokud je mimo intervál | + | * Při návratu nahoru testujeme balance; pokud je mimo interval |
| * V nejhorším provedeme až $O(\log n)$ rotací | * V nejhorším provedeme až $O(\log n)$ rotací | ||
| Line 483: | Line 483: | ||
| * prakticky používá v databázových systémech a souborových systémech. | * prakticky používá v databázových systémech a souborových systémech. | ||
| - | B-strom je řízen parametrem **minimální stupeň | + | B-strom je řízen parametrem **minimální stupeň |
| - | * Každý uzel (kromě kořene) má alespoň $t - 1$ a nejvýše $2t - 1$ klíčů. | + | * Každý uzel (kromě kořene) má alespoň $\lfloor |
| * Z toho plyne, že každý vnitřní uzel má mezi $t$ až $2t$ potomků. | * Z toho plyne, že každý vnitřní uzel má mezi $t$ až $2t$ potomků. | ||
| * Kořen může mít méně než $t - 1$ klíčů. | * Kořen může mít méně než $t - 1$ klíčů. | ||
| Line 493: | Line 493: | ||
| * Každý uzel má minimální a maximální počet klíčů (viz definice $t$ výše). | * Každý uzel má minimální a maximální počet klíčů (viz definice $t$ výše). | ||
| - | * Když uzel překročí maximální počet klíčů ($2t - 1$), rozdělí se na dva uzly a prostřední klíč se přesune do rodiče. | + | * Když uzel překročí maximální počet klíčů ($2t$), rozdělí se na dva uzly a prostřední klíč se přesune do rodiče. |
| * Pokud rodič také překročí maximální počet klíčů, proces se opakuje až ke kořeni. | * Pokud rodič také překročí maximální počet klíčů, proces se opakuje až ke kořeni. | ||
| Line 504: | Line 504: | ||
| === Vkládání === | === Vkládání === | ||
| * Klíč vkládáme do správného listu. | * Klíč vkládáme do správného listu. | ||
| - | * Pokud uzel překročí $2t - 1$ klíčů: | + | * Pokud uzel překročí $2t$ klíčů: |
| * Rozdělíme ho na dvě části. | * Rozdělíme ho na dvě části. | ||
| * Prostřední klíč přesuneme do rodiče. | * Prostřední klíč přesuneme do rodiče. | ||
| Line 512: | Line 512: | ||
| === Mazání === | === Mazání === | ||
| - | * Pokud uzel klesne pod $t - 1$ klíčů, musíme situaci opravit: | + | * Pokud uzel klesne pod $\lfloor |
| * **Borrow** – vypůjčíme si klíč od sourozence. | * **Borrow** – vypůjčíme si klíč od sourozence. | ||
| * **Merge** – sloučíme uzel se sourozencem a jeden klíč stáhneme z rodiče. | * **Merge** – sloučíme uzel se sourozencem a jeden klíč stáhneme z rodiče. | ||
| Line 723: | Line 723: | ||
| ==== Counting Sort ==== | ==== Counting Sort ==== | ||
| - | Nevyužívá porovnávání, | + | Nevyužívá porovnávání, |
| * Stabilní, velmi rychlý: $O(n + k)$ (k … rozsah hodnot) | * Stabilní, velmi rychlý: $O(n + k)$ (k … rozsah hodnot) | ||
| Line 945: | Line 945: | ||
| * Tabulka má vyhrazenou „sklepní“ část (**cellar**) – např. posledních 10–20 % buněk. | * Tabulka má vyhrazenou „sklepní“ část (**cellar**) – např. posledních 10–20 % buněk. | ||
| - | * Při kolizi prvek uložíme do **prvního volného** místa hledaného lineárně *odspodu* tabulky | + | * Při kolizi prvek uložíme do **prvního volného** místa hledaného lineárně *odspodu* tabulky (tj. v cellar-zóně) a pomocí ukazatele jej připojíme k řetězci své původní bucket-pozice. |
| - | | + | * Vyhledávání prochází ukazatele stejně jako u zřetězení, |
| - | * Vyhledávání prochází ukazatele stejně jako u zřetězení, | + | |
| - | | + | |
| Různé varianty: | Různé varianty: | ||
| Line 970: | Line 968: | ||
| === Univerzální hashování === | === Univerzální hashování === | ||
| - | Myšlenka: místo jediné pevné hash-funkce zvolíme při inicializaci **náhodně** $h$ | + | Myšlenka: místo jediné pevné hash-funkce zvolíme při inicializaci **náhodně** $h$ z rodiny $ℋ$, která splňuje podmínku univerzality: |
| - | z rodiny $ℋ$, která splňuje podmínku univerzality: | + | |
| $$ | $$ | ||
| Line 981: | Line 978: | ||
| Důsledky | Důsledky | ||
| - | * **Očekávaná** délka řetězce (nebo počet sond) je $\le α$, takže vkládání, | + | * **Očekávaná** délka řetězce (nebo počet sond) je $\le α$, takže vkládání, |
| - | | + | * Adversář, který nezná zvolenou $h$, neumí zkonstruovat mnoho kolizí (→ odolnost proti útokům na hash-tabulky např. v webových serverech). |
| - | * Adversář, který nezná zvolenou $h$, neumí zkonstruovat mnoho kolizí | + | |
| - | | + | |
| Složitost | Složitost | ||
| * Best / Average (v oč.) $O(1)$, protože $\mathbb{E}[\text{kolize}] \le α$. | * Best / Average (v oč.) $O(1)$, protože $\mathbb{E}[\text{kolize}] \le α$. | ||
| - | * Worst-case: stále $O(n)$ (kdybychom si vybrali „špatnou“ funkci), ale pravděpodobnost, | + | * Worst-case: stále $O(n)$ (kdybychom si vybrali „špatnou“ funkci), ale pravděpodobnost, |
| - | | + | |
