set - 为什么阿克曼函数与用于不相交集的并查找算法的摊余复杂度相关？

Question

谁能给我一个直观的解释为什么阿克曼函数 http://en.wikipedia.org/wiki/Ackermann_function与用于不相交集的并查找算法的摊销复杂度有关 http://en.wikipedia.org/wiki/Disjoint-set_data_structure ？

Tarjan 的数据结构书中的分析不是很直观。

我也在《算法导论》中查过，但似乎也太严格且不直观。

感谢您的帮助!

Answer 1

应用于不相交的森林

来自 Wikipedia

(about find and union) These two techniques complement each other; applied together, the amortized time per operation is only O(α(n)), where α(n) is the inverse of the function f(n) = A(n,n), and A is the extremely quickly-growing Ackermann function. Since α(n) is the inverse of this function, α(n) is less than 5 for all remotely practical values of n. Thus, the amortized running time per operation is effectively a small constant.

那为什么是阿克曼？

来自 Kruskal algoritm

The Function lg*n

Note that lg*n is a very slow growing function, much slower than lg n. In fact is slower than lg lg n, or any finite composition of lg n. It is the inverse of the function f(n) = 2 ^2^2^…^2, n times. For n >= 5, f(n) is greater than the number of atoms in the universe. Hence for all intents and purposes, the inverse of f(n) for any real life value of n, is constant. From an engineer’s point of view, Kruskal’s algorithm runs in O(e). Note of course that from a theoretician’s point of view, a true result of O(e) would still be a significant breakthrough. The whole picture is not complete because the actual best result shows that lg*n can be replaced by the inverse of A(p,n) where A is Ackermann’s function, a function that grows explosively. The inverse of Ackermann’s function is related to lg*n, and is a nicer result, but the proof is even harder.