Differences

This shows you the differences between two versions of the page.

Link to this comparison view

Both sides previous revisionPrevious revision
Next revision		Previous revision
statnice:bakalar:b4b33alg [2025/06/08 13:29] – zapleka3statnice: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://fel.cvut.cz/cz/education/bk/predmety/46/82/p4682306.html|B4B33ALG]] [[https://cw.fel.cvut.cz/b211/courses/b4b33alg/start|Webové stránky předmětu]] [[https://fel.cvut.cz/cz/education/bk/predmety/46/82/p4682306.html|B4B33ALG]] [[https://cw.fel.cvut.cz/b211/courses/b4b33alg/start|Webové stránky předmětu]]
Line 476: Line 476:
 === Mazání === === Mazání ===
   * Najdeme a odstraníme klíč (případně jej nahradíme in-order předchůdcem/nástupcem).   * Najdeme a odstraníme klíč (případně jej nahradíme in-order předchůdcem/nástupcem).
-  * Při návratu nahoru testujeme balance; pokud je mimo intervál $<-1,1>$, rotacemi jej opravíme.+  * Při návratu nahoru testujeme balance; pokud je mimo interval $<-1,1>$, rotacemi balance opravíme.
   * 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ň _t_ (t ≥ 2)**: +B-strom je řízen parametrem **minimální stupeň $t$ ($t \ge 2$)**: 
-  * 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 t/2 \rfloor$ a nejvýše $2t$ klíčů.
   * 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 t/2 \rfloor$ klíčů, musíme situaci opravit:
     * **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 541: Line 541:
  
 {{https://upload.wikimedia.org/wikipedia/commons/2/24/Sorting_insertion_sort_anim.gif?200}} {{https://upload.wikimedia.org/wikipedia/commons/2/24/Sorting_insertion_sort_anim.gif?200}}
 +
 +<code python>
 +# Insertion Sort
 +def insertion_sort(arr):
 +    for i in range(1, len(arr)):
 +        key = arr[i]
 +        j = i - 1
 +        while j >= 0 and arr[j] > key:
 +            arr[j + 1] = arr[j]
 +            j -= 1
 +        arr[j + 1] = key
 +    return arr
 +</code>
  
 ==== Selection Sort ==== ==== Selection Sort ====
Line 551: Line 564:
  
 {{https://upload.wikimedia.org/wikipedia/commons/3/3e/Sorting_selection_sort_anim.gif?200}} {{https://upload.wikimedia.org/wikipedia/commons/3/3e/Sorting_selection_sort_anim.gif?200}}
 +
 +<code python>
 +# Selection Sort
 +def selection_sort(arr):
 +    for i in range(len(arr)):
 +        min_idx = i
 +        for j in range(i + 1, len(arr)):
 +            if arr[j] < arr[min_idx]:
 +                min_idx = j
 +        arr[i], arr[min_idx] = arr[min_idx], arr[i]
 +    return arr
 +</code>
  
 ==== Bubble Sort ==== ==== Bubble Sort ====
Line 560: Line 585:
  
 {{https://upload.wikimedia.org/wikipedia/commons/5/54/Sorting_bubblesort_anim.gif?200}} {{https://upload.wikimedia.org/wikipedia/commons/5/54/Sorting_bubblesort_anim.gif?200}}
 +
 <code python> <code python>
 +# Bubble Sort
 def bubble_sort(arr): def bubble_sort(arr):
-  for n in range(len(arr) - 1, 0, -1): +    for n in range(len(arr) - 1, 0, -1): 
-    swapped = False   +        swapped = False 
- +        for i in range(n): 
-    for i in range(n): +            if arr[i] > arr[i + 1]: 
-      if arr[i] > arr[i + 1]: +                arr[i], arr[i + 1] = arr[i + 1], arr[i] 
-        arr[i], arr[i + 1] = arr[i + 1], arr[i] +                swapped = True 
-                 +        if not swapped: 
-        swapped = True +            break 
-         +    return arr
-      if not swapped: +
-        break +
-  return arr+
 </code> </code>
  
-==== QuickSort ====Vysoce efektivní algoritmus typu "rozděl a panuj". Vybereme prvek jako pivot, rozdělíme pole na dvě části (menší a větší než pivot) a rekurzivně řadíme každou část.+==== QuickSort ==== 
 +Vysoce efektivní algoritmus typu "rozděl a panuj". Vybereme prvek jako pivot, rozdělíme pole na dvě části (menší a větší než pivot) a rekurzivně řadíme každou část.
  
   * Průměrně $O(n \log n)$, ale nejhorší případ $O(n^2)$ (např. již seřazené pole a špatně zvolený pivot).   * Průměrně $O(n \log n)$, ale nejhorší případ $O(n^2)$ (např. již seřazené pole a špatně zvolený pivot).
Line 583: Line 608:
  
 {{https://upload.wikimedia.org/wikipedia/commons/6/6a/Sorting_quicksort_anim.gif?200}} {{https://upload.wikimedia.org/wikipedia/commons/6/6a/Sorting_quicksort_anim.gif?200}}
 +
 +<code python>
 +# QuickSort
 +def quicksort(arr):
 +    if len(arr) <= 1:
 +        return arr
 +    pivot = arr[0]
 +    less = [x for x in arr[1:] if x < pivot]
 +    greater_eq = [x for x in arr[1:] if x >= pivot]
 +    return quicksort(less) + [pivot] + quicksort(greater_eq)
 +</code>
  
 ==== Merge Sort ==== ==== Merge Sort ====
Line 592: Line 628:
  
 {{https://upload.wikimedia.org/wikipedia/commons/c/c5/Merge_sort_animation2.gif?200}} {{https://upload.wikimedia.org/wikipedia/commons/c/c5/Merge_sort_animation2.gif?200}}
 +
 +<code python>
 +# Merge Sort
 +def merge_sort(arr):
 +    if len(arr) <= 1:
 +        return arr
 +    mid = len(arr) // 2
 +    left = merge_sort(arr[:mid])
 +    right = merge_sort(arr[mid:])
 +    return merge(left, right)
 +
 +def merge(left, right):
 +    result = []
 +    i = j = 0
 +    while i < len(left) and j < len(right):
 +        if left[i] <= right[j]:
 +            result.append(left[i])
 +            i += 1
 +        else:
 +            result.append(right[j])
 +            j += 1
 +    result.extend(left[i:])
 +    result.extend(right[j:])
 +    return result
 +</code>
  
 ==== Heap Sort ==== ==== Heap Sort ====
Line 601: Line 662:
  
 {{https://upload.wikimedia.org/wikipedia/commons/1/1b/Sorting_heapsort_anim.gif?200}} {{https://upload.wikimedia.org/wikipedia/commons/1/1b/Sorting_heapsort_anim.gif?200}}
 +
 +<code python>
 +# Heap Sort
 +def heapify(arr, n, i):
 +    largest = i
 +    l = 2 * i + 1
 +    r = 2 * i + 2
 +    if l < n and arr[l] > arr[largest]:
 +        largest = l
 +    if r < n and arr[r] > arr[largest]:
 +        largest = r
 +    if largest != i:
 +        arr[i], arr[largest] = arr[largest], arr[i]
 +        heapify(arr, n, largest)
 +
 +def heap_sort(arr):
 +    n = len(arr)
 +    for i in range(n // 2 - 1, -1, -1):
 +        heapify(arr, n, i)
 +    for i in range(n - 1, 0, -1):
 +        arr[0], arr[i] = arr[i], arr[0]
 +        heapify(arr, i, 0)
 +    return arr
 +</code>
  
 ==== Radix Sort ==== ==== Radix Sort ====
Line 608: Line 693:
   * Vhodný pro řetězce nebo celá čísla s pevnou délkou.   * Vhodný pro řetězce nebo celá čísla s pevnou délkou.
   * Používá se např. u PSČ, osobních čísel apod.   * Používá se např. u PSČ, osobních čísel apod.
 +
 +<code python>
 +# Radix Sort
 +def counting_sort_by_digit(arr, exp):
 +    n = len(arr)
 +    output = [0] * n
 +    count = [0] * 10
 +    for i in range(n):
 +        index = (arr[i] // exp) % 10
 +        count[index] += 1
 +    for i in range(1, 10):
 +        count[i] += count[i - 1]
 +    for i in reversed(range(n)):
 +        index = (arr[i] // exp) % 10
 +        output[count[index] - 1] = arr[i]
 +        count[index] -= 1
 +    return output
 +
 +def radix_sort(arr):
 +    if not arr:
 +        return []
 +    max_val = max(arr)
 +    exp = 1
 +    while max_val // exp > 0:
 +        arr = counting_sort_by_digit(arr, exp)
 +        exp *= 10
 +    return arr
 +</code>
  
 ==== Counting Sort ==== ==== Counting Sort ====
-Nevyužívá porovnávání, ale frekvenční pole. Nejprve spočítáme výskyty všech hodnot, pak je seřadíme podle počtu. Funguje pouze pro celočíselné hodnoty v omezeném rozsahu.+Nevyužívá porovnávání, ale frekvenční pole. Nejdříve určíme maximální hodnotu v poli. Tu použijeme pro inicializaci pomocného pole, které bude mít velikost max + 1. Po té na každý index pomocného pole uložíme počet výskytu jednotlivých hodnot (postupně procházímme původní pole a přičteme 1). Pak kumulativně přičteme ke každé hodnotě hodnotu zprava. Výsledek nám dává počáteční index, odkud začíná číslo. https://www.youtube.com/watch?v=OKd534EWcdk. Funguje pouze pro celočíselné hodnoty v omezeném rozsahu.
  
   * Stabilní, velmi rychlý: $O(n + k)$ (k … rozsah hodnot)   * Stabilní, velmi rychlý: $O(n + k)$ (k … rozsah hodnot)
Line 619: Line 732:
  
 <code python> <code python>
-def countingSort(arr): +# Counting Sort 
-  max_val = max(arr) +def counting_sort(arr): 
-  count = [0] * (max_val + 1) +    if not arr: 
- +        return [] 
-  while len(arr) > 0: +    max_val = max(arr) 
-    num = arr.pop(0) +    count = [0] * (max_val + 1) 
-    count[num] += 1 +    for num in arr: 
- +        count[num] += 1 
-  arr = [] +    output = [] 
-  for i in range(len(count)): +    for i in range(len(count)): 
-    arr += [i] * count[i] +        output.extend([i] * count[i]) 
- +    return output
-  return arr+
 </code>  </code> 
  
Line 654: Line 766:
 Je to všeobecná strategie pro řešení optimalizačních úloh. Významné vlastnosti: Je to všeobecná strategie pro řešení optimalizačních úloh. Významné vlastnosti:
   * Hledané optimální řešení lze sestavit z vhodně volených optimálních řešení téže úlohy nad redukovanými daty.   * Hledané optimální řešení lze sestavit z vhodně volených optimálních řešení téže úlohy nad redukovanými daty.
-  * V rekurzivně formulovaném postupu řešení se opakovaně objevují stejné menší podproblémy. DP umožňuje obejít opakovaný výpočet většinou jednoduchou tabelací výsledků menších podproblémů, tedy volně řečeno, přepočítáním menších výsledků+  * V rekurzivně formulovaném postupu řešení se opakovaně objevují stejné menší podproblémy. DP umožňuje obejít opakovaný výpočet většinou jednoduchou tabelací výsledků menších podproblémů, tedy volně řečeno, přepočítáním menších výsledků.
  
 ===== Dynamické programování pro Nejdelší Společnou Posloupnost (LCS) ===== ===== Dynamické programování pro Nejdelší Společnou Posloupnost (LCS) =====
-<markdown> +  * Mějme dvě posloupnosti písmen a chceme najít nejdelší společnou podposloupnost. 
-**Myšlenka algoritmu:** +  * Například u posloupností {BDCABA} a {ABCBDAB} je řešení {BCBA}. 
-  * Cíl: Najít nejdelší posloupnost znaků, která se vyskytuje ve stejném pořadí v obou vstupních řetězcích (ne nutně souvisle). +  * Časová složitost: $O(m \cdot n)$, kde $m$ a $n$ jsou délky řetězců.
-  * Dynamické programování (DP) využívá 2D tabulku pro ukládání dílčích výsledků. Buňka `dp[i][j]` udává délku LCS pro první `i` znaků řetězce `X` a první `j` znaků řetězce `Y`. +
-  * Pokud `X[i-1] == Y[j-1]`, přidáme tento znak k LCS a přičteme 1 k `dp[i-1][j-1]`. +
-  * Pokud se znaky liší, vezmeme maximum z `dp[i-1][j]` (horní buňka) a `dp[i][j-1]` (levá buňka).+
  
-**Pseudokód v Pythonu:** +  * **Myšlenka algoritmu:** 
-```python+    * Cíl: Najít nejdelší posloupnost znaků, která se vyskytuje ve stejném pořadí v obou vstupních řetězcích (ne nutně souvisle). 
 +    * Dynamické programování (DP) využívá 2D tabulku pro ukládání dílčích výsledků. 
 +    * Buňka `dp[i][j]` udává délku LCS pro první `i` znaků řetězce `X` a první `j` znaků řetězce `Y`. 
 +    * Pokud `X[i-1] == Y[j-1]`, přidáme tento znak k LCS a přičteme 1 k `dp[i-1][j-1]`. 
 +    * Pokud se znaky liší, vezmeme maximum z `dp[i-1][j]` (horní buňka) a `dp[i][j-1]` (levá buňka). 
 + 
 +  * **Pseudokód v Pythonu:** 
 +<code python>
 def lcs(X, Y): def lcs(X, Y):
     m = len(X)     m = len(X)
Line 671: Line 787:
     # Vytvoření DP tabulky s nulami (m+1 x n+1)     # Vytvoření DP tabulky s nulami (m+1 x n+1)
     dp = [[0]*(n+1) for _ in range(m+1)]     dp = [[0]*(n+1) for _ in range(m+1)]
-    +
     # Naplnění tabulky     # Naplnění tabulky
     for i in range(1, m+1):     for i in range(1, m+1):
Line 679: Line 795:
             else:             else:
                 dp[i][j] = max(dp[i-1][j], dp[i][j-1])                 dp[i][j] = max(dp[i-1][j], dp[i][j-1])
-    +
     # Rekonstrukce LCS z tabulky     # Rekonstrukce LCS z tabulky
     i, j = m, n     i, j = m, n
Line 693: Line 809:
             j -= 1             j -= 1
     return ''.join(reversed(result))     return ''.join(reversed(result))
-```+</code>
  
 **Příklad tabulky pro `X = "BDCABA"`, `Y = "ABCBDAB"`:** **Příklad tabulky pro `X = "BDCABA"`, `Y = "ABCBDAB"`:**
-  - Řešení: **"BCBA"** (délka 4). 
  
 +Řešení: **"BCBA"** (délka 4).
 +
 +**Tabulka:**
 |   |   | A | B | C | B | D | A | B | |   |   | A | B | C | B | D | A | B |
 |---|---|---|---|---|---|---|---|---| |---|---|---|---|---|---|---|---|---|
Line 708: Line 826:
 | A | 0 | 1 | 2 | 2 | 3 | 3 | 4 | 4 | | A | 0 | 1 | 2 | 2 | 3 | 3 | 4 | 4 |
  
-**Vysvětlení tabulky:** +  * **Vysvětlení tabulky:** 
-  * První řádek a sloupec jsou inicializovány na 0 (prázdné podřetězce). +    * První řádek a sloupec jsou inicializovány na 0 (prázdné podřetězce). 
-  * Buňka `dp[5][7]` (hodnota 4) ukazuje délku LCS. Cesta pro rekonstrukci je vyznačena šipkami: +    * Buňka `dp[5][7]` (hodnota 4) ukazuje délku LCS. 
-    - Začínáme od `dp[6][7]` (4), postupujeme diagonálně při shodě znaků.+    * Cesta pro rekonstrukci je postup diagonální (při shodě znaků) nebo výběr větší hodnoty z okolních buněk.
  
-**Časová složitost:**  +  * **Složitost:** 
-  * Naplnění tabulky: $O(m \cdot n)$, rekonstrukce: $O(m + n)$. +    * Naplnění tabulky: $O(m \cdot n)$ 
-  * Celkem: $O(m \cdot n)$. +    * Rekonstrukce: $O(m + n)$ 
-</markdown> +    * Celkem: $O(m \cdot n)$ 
-===== Rozptylovací tabulky (Hashing) =====+ 
 + 
 + 
 +===== 7. Rozptylovací tabulky (Hashing) =====
   * hashovací funkce, řešení kolizí, otevřené a zřetězené tabulky, double hashing, srůstající tabulky, univerzální hashování.   * hashovací funkce, řešení kolizí, otevřené a zřetězené tabulky, double hashing, srůstající tabulky, univerzální hashování.
  
-  * rozptylovací funkce = hashovací funkce +  * Rozptylovací tabulky – tabulka, určená k redukování dat na menší data, která budou jednoznačná. 
-  * Hashovací funkce přiřadí k potenciálně libovolnému množství dat hodnotu který má vždy kosntantní délku. +  * Základ datové struktury slovníku, kde operace search a insert mají konstantní složitost. 
-  * Hashovací funkce v kontextu algoritmizace by měla být hlavně rychlá (narozdíl od kryptografie, kde pomalost je část bezpečnosti za hashovací funkcí) s co nejméně kolizemi (kolize - 2 různé vstupy mají stejný výstup)+  * Hashovací funkce – funkce která datům přiřadí nějakou hodnotu konstantní délky, která se výrazně liší pro podobná data a není z ní možné rekonstruovat originální data – hash. 
 +  * Hashovací funkce přiřadí k potenciálně libovolnému množství dat hodnotu, která má vždy konstantní délku. 
 +  * V kontextu algoritmizace by měla být hlavně rychlá (na rozdíl od kryptografie, kde pomalost je část bezpečnosti). 
 +   
 +  * Cíl je generovat minimum kolizí. 
 +  * Kolize – situace, kdy dvěma různým datům přiřadíme stejný hash – řešíme pomocí zřetězeného rozptylování, nebo otevřeného rozptylování.
   * Umožňují vyhledávat v tabulkách s průměrnou časovou složitostí $O(1)$.   * Umožňují vyhledávat v tabulkách s průměrnou časovou složitostí $O(1)$.
 +
 ==== Algoritmické úlohy (soutěžní) ==== ==== Algoritmické úlohy (soutěžní) ====
-  * Two Sum – O(n) hledání dvojice se zadaným součtem pomocí `set`.+  * Two Sum – $O(n)$ hledání dvojice se zadaným součtem pomocí `set`.
   * Dynamické programování s memoizací – ukládání $T(n)$ do hashe (Fibonacci, LCS…).   * Dynamické programování s memoizací – ukládání $T(n)$ do hashe (Fibonacci, LCS…).
   * Rolling hash (Rabin–Karp) – rychlé vyhledávání vzoru v textu.   * Rolling hash (Rabin–Karp) – rychlé vyhledávání vzoru v textu.
-  * Longest Consecutive Sequence – O(n) řešení s `unordered_set`.+  * Longest Consecutive Sequence – $O(n)$ řešení s `unordered_set`.
   * Počty výskytů / anagramy – frekvenční slovník pro srovnání řetězců.   * Počty výskytů / anagramy – frekvenční slovník pro srovnání řetězců.
  
Line 735: Line 862:
   * Hash join v relačních databázích při spojování tabulek.   * Hash join v relačních databázích při spojování tabulek.
   * In-memory cache (DNS, LRU) pro konstantní přístup.   * In-memory cache (DNS, LRU) pro konstantní přístup.
-  * Deduplicace a kontrola integrity souborů (git objekty, zálohy).+  * Deduplikace a kontrola integrity souborů (git objekty, zálohy).
   * Bloom filter – pravděpodobnostní test příslušnosti s malou pamětí.   * Bloom filter – pravděpodobnostní test příslušnosti s malou pamětí.
  
 ==== Kolize v hashovacích tabulkách ==== ==== Kolize v hashovacích tabulkách ====
-Kolize  – situace, kdy dvěma různým vstupům hashovací funkce tabulky přiřadí stejný výstup.+  * Kolize nastávají, protože zobrazení z klíčů do adres hashovací funkce není prosté. 
 +  * Hashovací tabulky se používají k rychlému vyhledávání, ale protože hashovací funkce mohou mít kolize, tabulky musí umět tyto kolize řešit. 
 +  * Tabulka je nejčastěji reprezentovaná polem s indexy $0 … n-1$, kde $n$ je délka pole.
  
-Hashovací tabulky se používají k rychlému vyhledávání, ale protože hashovací funkce mohou mít kolize, tabulky musí umět tyto kolize řešit. +Existují tři běžné způsoby řešení kolizí:   
- +  * zřetězený hashing   
-Tabulka je nejčastěji reprezentovaná polem s indexy $0 … n-1$, kde $n$ je délka pole. +  * lineární sondování   
- +  * double hashing  
-Existují tři běžné způsoby řešení kolizí: zřetězený hashing, lineární sondování a double hashing.+
  
 === Zřetězený hashing === === Zřetězený hashing ===
-Jak to funguje  – z každého políčka vede spojený seznam (linked list).+  * Každá adresa si zachovává spojový seznam všech hodnot, které se namapují na danou adresu. 
 +  * Vkládání – vypočítáme index $h(k)$. Pokud políčko už obsahuje prvek, vložíme nový na konec jeho seznamu. 
 +  * Hledání – projdeme seznam, dokud klíč nenajdeme, nebo nedojdeme na jeho konec. 
 +  * Mazání – odstraníme uzel ze seznamu (klasická operace na linked-listu).
  
-  * **Vkládání** – vypočítáme index $h(k)$.   +Výhody:
-    Pokud políčko už obsahuje prvek, vložíme nový na *konec* jeho seznamu. +
-  * **Hledání** – projdeme seznam, dokud klíč nenajdeme, nebo nedojdeme na jeho konec. +
-  * **Mazání** – odstraníme uzel ze seznamu (klasická operace na linked-listu). +
- +
-Výhody+
   * Jednoduchá implementace, žádný problém s přeplněním pole.   * Jednoduchá implementace, žádný problém s přeplněním pole.
-  * Výkon se zhoršuje hladce – degraduje k $O(n)$ jen když se load-factor blíží ∞ a seznamy jsou dlouhé.+  * Výkon se zhoršuje hladce – degraduje k $O(n)$ jen když se load-factor blíží ∞.
  
-Nevýhody+Nevýhody:
   * Vícenásobné alokace a ukazatele → ztráta cache-locality.   * Vícenásobné alokace a ukazatele → ztráta cache-locality.
   * Potenciálně vyšší režie alokátorů při častém vkládání.   * Potenciálně vyšší režie alokátorů při častém vkládání.
  
-Složitost  +Složitost:
   * Average-case: $O(1)$   * Average-case: $O(1)$
   * Worst-case: $O(n)$   * Worst-case: $O(n)$
  
 === Otevřené rozptylování – Linear probing === === Otevřené rozptylování – Linear probing ===
-Jak to funguje  – pokud je políčko z hashu obsazeno, posouváme se lineárně dál.+Jak to funguje  – pokud je políčko z hashu obsazeno, posouváme se lineárně dál (modulo n).
  
-  * **Vkládání** – vypočítáme index $h(k)$.   +  * **Vkládání** – vypočítáme index $h(k)$. Kolize ⇒ zkusíme $(h(k)+1) \mod n$, pak $+1$… dokud nenajdeme prázdné místo.
-    Kolize ⇒ zkusíme $(h(k)+1) \mod n$, pak $+1$… dokud nenajdeme prázdné místo.+
   * **Hledání** – stejně sondujeme, dokud   * **Hledání** – stejně sondujeme, dokud
     * nenajdeme klíč  (nalezen) nebo nenarazíme na prázdné políčko  (klíč tam není).     * nenajdeme klíč  (nalezen) nebo nenarazíme na prázdné políčko  (klíč tam není).
Line 793: Line 918:
   * $h1(k)$ – primární index v rozsahu $0 … n-1$   * $h1(k)$ – primární index v rozsahu $0 … n-1$
   * $h2(k)$ – **krok (step)** v rozsahu $1 … n-1$;     * $h2(k)$ – **krok (step)** v rozsahu $1 … n-1$;  
-    musí být nesoudělný s $n$, aby prohlídka pokryla celé pole.+    * musí být nesoudělný s $n$, aby prohlídka pokryla celé pole.
  
 Algoritmus sondování   Algoritmus sondování  
Line 814: Line 939:
   * Average-case: $O(1)$   * Average-case: $O(1)$
   * Worst-case: $O(n)$   * Worst-case: $O(n)$
 +
 +
 === Srůstající (coalesced) hashing === === Srůstající (coalesced) hashing ===
 Kombinuje výhody otevřeného rozptylování a zřetězení: Kombinuje výhody otevřeného rozptylování a zřetězení:
  
   * 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. 
-    (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í, ale všechny uzly sedí přímo v poli, takže nedochází k fragmentaci paměti a cache-missům. 
-  * Vyhledávání prochází ukazatele stejně jako u zřetězení, ale všechny uzly sedí přímo v poli, + 
-    takže nedochází k fragmentaci paměti a cache-missům.+Různé varianty: 
 +  * LISCH (late insert standard coalesced hashing) – přidáváme na konec řetězce. 
 +  * EISCH (early insert…) – přidáváme na začátek řetězce. 
 +  * LICH, EICH – jako výše, ale se sklepem. 
 +  * VICH – kombinuje, kam přidat podle toho, kde řetězec končí.
  
 Složitost   Složitost  
Line 837: 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 848: 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í, vyhledávání i mazání běží v $O(1)$ očekávaném čase, bez ohledu na rozdělení klíčů. 
-    vyhledávání i mazání běží v $O(1)$ očekávaném čase, bez ohledu na rozdělení klíčů. +  * 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í +
-    (→ odolnost proti útokům na hash-tabulky např. v webových serverech).+
  
  
 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, že se to stane, je $\le 1/m$ a můžeme $h$ jednoduše přelosovat.
-    že se to stane, je $\le 1/m$ a můžeme $h$ jednoduše přelosovat.+
  
  
    

Trace:

Navigation

Playground

QR Code
QR Code statnice:bakalar:b4b33alg (generated for current page)