Nájdi a spoj Union & Find (Disjoint-set)¶
Máme prvky rozdelené do množín. Každý prvok je v práve jednej množine. Chceme vedieť efektívne zistiť, v ktorej množine je prvok a vediet efektívne spojiť dve množiny do jednej.
MakeSet(x): z prvku vytvorí jednoprvkovú množinu
Find(x): zisti, v ktorej množine je x
Union(x, y): spojí množiny, ktoré obsahujú x,y| algoritmus | Union | Find |
|---|---|---|
| quick find | $O(n)$ | $O(1)$ |
| quick union | $O(h)$ | $O(h)$ |
| weighted | $$O(\log n)$$ | $$O(\log n)$$ |
| path compression | $$O\left(\log_{\left\lfloor{1+\frac{m}{n}}\right\rfloor} n\right)$$ | $$O\left(\log_{\left\lfloor{1+\frac{m}{n}}\right\rfloor} n\right)$$ |
| weighted+path compression | $O\left((m+n) \cdot \log^{*} n\right)$ | $O\left((m+n) \cdot \log^{*} n\right)$ |
| weighted+path compression | $O\left(m \cdot \alpha(m,n)\right)$ | $O\left(m \cdot \alpha(m,n)\right)$ |
kde $n$ je počet prvkov, $h$ je výška stromu, $m$ - počet operácií
Iterovaný dvojkový logaritmus¶
https://en.wikipedia.org/wiki/Iterated_logarithm
rastie veľmi pomaly
$2^{65536}$ má skoro 20000 miest, zaberá 8kiB, vo vesmíre je len $2^{240}$ atómov
In [7]:
len(str(2**65536)) #sys.set_int_max_str_digits(20000)
Out[7]:
19729
In [2]:
(2**65536).bit_length()/8/1024
Out[2]:
8.0001220703125
Inverzná Ackermannova funkcia¶
Ackermannova funkcia
$$ A(0, n) = n+1 $$ $$ A(m+1, n+1) = A\left(m, A(m+1, n)\right) $$
Inverzná Ackermannova funkcia
$$ \alpha(n, n) = \left[A(n, n)\right]^{-1}$$
$$ \alpha(m, n) = \min_{i \geq 1} A\left(i, \left\lfloor\frac{m}{n}\right\rfloor\right) \geq \log_2 n$$
In [ ]: