Please enable JavaScript.

Coggle requires JavaScript to display documents.

Datové struktury - Coggle Diagram

- - - - Kolize
        
        Vytvoří se spojový seznam a přidáme prvek na konec
      - Faktor naplnění
        
        Očekávaná délka řetízků
        
        cn/m (Pro c univerzalni system)
  - - - Operace
        
        INsert
        
        Delete
        
        Find
        
        O(1)
        
        Časová složitost
        
        KOnstantní
        
        Prostorová složistost
        
        Lineární
      - Každému prvku universa přiřadí přihŕadku
      - Pro reprezentaci množiny
      - Přiklady
        
        Lineární kongurence
        
        ax mod m
        
        Vyšší bity součinu
        
        Použivámé SHIFT
        
        Potřebujeme a liché
        
        h(x) = Spodní část od ((ax mod 2^w)/2^(a-l)
        
        Skalární součin
        
        Polynom
    - - Přihrádky indexujeme od 0 do m-1
    - - UNiversum je vetší než počet přihrádek
        
        Dochází ke kolizím
      - Chceme uložit podmnožinu universa
      - Velikost (U)
    - - System H je c univerzální pokud pro A a B e Y [h(A) == h(B}] <= c/m pro A != B
    - - Střední hodnota kolizí je <= cn/m
        
        Důkaz
        
        Linearita střední hodnoty
  - - - Řešení
        
        Budeme volit funkci náhodně
  - - - Amortizovaně opět dostaneme konstantní složitost
  - - - Dukaz
        
        Bilinearita
      - Co když nechceme m jako prvočíslo
        
        Tak pouzijemene jine prvocislo p
    - - Dukaz