5 ms·
Disjoint-Sets have a very cool implementation whose amortized time complexity is extremely slow growing. It is not quite constant, but even for a disjoint-set w
by kaymanb 4y ago
Disjoint-Sets have a very cool implementation whose amortized time complexity is extremely slow growing. It is not quite constant, but even for a disjoint-set with as many elements as there are particles in the universe, the amortized cost of an operation will be less than or equal to 4.
https://en.wikipedia.org/wiki/Disjoint-set_data_structure https://en.wikipedia.org/wiki/Disjoint-set_data_structure
- EnderShadow8 4y agoI've been told to consider it constant for all practical purposes
- pjscott 4y agoThe inverse Ackermann function is one of the slowest-growing functions that you’re ever likely to encounter in the wild. To say that it’s “constant for all practical purposes” is 100% true but doesn’t do justice to how amazingly slow this function is to grow. https://en.m.wikipedia.org/wiki/Ackermann_function https://en.m.wikipedia.org/wiki/Ackermann_function
- andreareina 4y agoUse the idea[1] at work to make large NP-complete problems more tractable by breaking the problem up into disjoint subsets. [1] doesn't implement the inverse-ackermann algorithm but still implemented as union/find.
- kragen 4y agoaka "union find" — some other comments in the thread call it that