Content deleted Content added
→Disjoint-set forests: comments in Find code |
Lower bound and history |
||
Line 65:
These two techniques complement each other; applied together, the average time per operation is only O(α(n)), where α(n) is the inverse of the function ''f''(''n'') = ''A''(''n'',''n''), where ''A'' is the extremely quickly-growing [[Ackermann function]]. Since α(''n'') is its inverse, it's less than 5 for all remotely practical values of ''n''. Thus, the average running time per operation is effectively a small constant; we couldn't ask for much better than this.
In fact, we can't get better than this: Fredman and Saks showed in [[1989]] that Ω(α(n)) words must be accessed by ''any'' disjoint-set data structure per operation on average.
== Applications ==
Line 83 ⟶ 85:
As the water level continues to rise, it may touch a saddle point, or "pass." When we reach such a pass, we follow the steepest downhill route from it on each side until we arrive a local minimum. We use '''Find''' to determine which contours surround these two local minima, then use '''Union''' to combine them. Eventually, all contours will be combined into one, and we are done.
== History ==
While the ideas used in disjoint-set forests have long been familiar, [[Robert Tarjan]] was the first to prove the upper bound (and a restricted version of the lower bound) in terms of the inverse Ackmann function. Until this time the best bound on the time per operation, proven by Hopcroft and Ullman, was O(log<sup>*</sup> n), the [[iterated logarithm]] of n, another slowly-growing function (but not quite as slow as the inverse Ackmann function). Tarjan and van Leeuwen also developed one-pass ''Find'' algorithms that are more efficient in practice. The algorithm was made well-known by the popular textbook ''Introduction to Algorithms'', listed in the references.
== References ==
| |||