3 ms·
In order to get the O(log(n)) runtime that you talk about, you need to take care that the Tree data structure doesn't devolve into a list, e.g. by keeping track
by sqrt17 16y ago
In order to get the O(log(n)) runtime that you talk about, you need to take care that the Tree data structure doesn't devolve into a list, e.g. by keeping track of a child count and always putting the smaller tree as a child of the larger tree (see http://en.wikipedia.org/wiki/Disjoint-set_data_structure http://en.wikipedia.org/wiki/Disjoint-set_data_structure)
Discussing asymptotic behaviour is only useful if you're able to understand how your code needs to look to actually achieve it.
- jamis 16y agoGood point. I've removed the bit about O(log n), since aside from being misleading, it really wasn't even relevant to the point of the article.
- baddox 16y agoThe disjoint set is one of my favorite data structures because the amortized running time of its basic operations is O(α(n)), α being the inverse of the Ackermann function. The Ackermann function grows extremely quickly (quicker than any primitive recursive function I believe), so its inverse grows extremely slowly. In fact, α(x) is less than 5 for "reasonable" values of x such as the number of atoms in the universe. Therefore, the amortized run time of the disjoint set operations can be thought of as essentially constant. Also of interest to me is that the inverse Ackermann function is proven to be the asymptotically optimal run time for the disjoint set operations. I'm not equipped to understand that particular proof of asymptotic optimality, but other such proofs (like the O(n lg n) running time for comparison sort) are elegant and awesome.
- adrianN 16y ago> The Ackermann function grows extremely quickly (quicker than any primitive recursive function I believe) This is correct. It was basically invented to show that primitive recursion is not capable of computing every computable function.