Content deleted Content added
→Disjoint-set linked lists: rv vandalism |
No edit summary |
||
Line 63:
'''return''' root
These two techniques complement each other; applied together, the [[amortized analysis|amortized]] 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'' {{ref|ackermann}}. Thus, the amortized 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.
Line 88:
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 Ackermann 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 Ackermann 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.
== Notes ==
# {{note|ackermann}} The first ''n'' such that α(''n'') >e; 5 has a base-2 logarithm whose own base-2 logarithm is greater than the number of particles in the universe raised to the power 200.
== References ==
| |||