3 ms·
First time I've heard of the disjoint-set data structure. For a DSF implementation, Wikipedia [0] gives the wildest asymptotic complexity I've seen, using the i
by xelxebar 2y ago
First time I've heard of the disjoint-set data structure. For a DSF implementation, Wikipedia [0] gives the wildest asymptotic complexity I've seen, using the inverse Ackermann function! "Almost constant time" indeed.
[0]:https://en.wikipedia.org/wiki/Disjoint-set_data_structure https://en.wikipedia.org/wiki/Disjoint-set_data_structure
- kragen 2y agomore commonly it's called union-find; it came up on here last thursday: https://news.ycombinator.com/item?id=41450948 https://news.ycombinator.com/item?id=41450948
- shepherdjerred 2y agoDisjoint sets are awesome! You can use them with a _very_ simple algorithm to form a minimum spanning tree. https://en.wikipedia.org/wiki/Kruskal%27s_algorithm https://en.wikipedia.org/wiki/Kruskal%27s_algorithm
- kevinventullo 2y agoWhat’s especially surprising to me is that inverse Ackerman is provably optimal for this problem, regardless of implementation.
- LudwigNagasena 2y agoIt’s a standard part of Data Structures & Algorithms curricula. You can find it in CLRS.
- agumonkey 2y agoHa, I've been looking for an inverse ackermann instance for quite a while. Thanks