为什么Ackermann函数与用于不相交集的union-find算法的摊销复杂性有关？

Question

任何人都能直接解释为什么Ackermann函数http://en.wikipedia.org/wiki/Ackermann_function与用于不相交集的联合查找算法的摊销复杂性有关http://en.wikipedia.org/ wiki/Disjoint-set_data_structure？

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

我也在算法入门中查了一下,但它看起来也太严格且不直观.

谢谢你的帮助!

Answer 1

应用于不相交集森林

\n\n

来自维基百科

\n\n

\n

（关于查找和并集）这两种\n技术是相辅相成的；\n一起应用，每次操作的摊余时间\n仅为O(\xce\xb1(n))，其中\n \xce\xb1(n)是函数\nf(n) = A(n,n) 的反函数，A 是极其\n 快速增长的阿克曼函数。\n 因为 \xce\xb1(n) 是该函数的反函数\n ，对于 n 的所有远程实际值，\xce\xb1(n) 都小于 5。因此，每个操作的摊销运行时间实际上是一个很小的常数。

\n

\n\n

那么为什么是阿克曼呢？

\n\n

来自克鲁斯卡尔算法

\n\n

\n

函数 lg*n

\n\n

请注意，lg*n 是一个增长非常缓慢的函数，比 lg n 慢得多。实际上比 lg lg n 或 lg n 的任何有限组合慢。它是函数 f(n) = 2\n ^2^2^\xe2\x80\xa6^2 n 次的逆函数。对于 n >= 5，f(n)\n 大于宇宙中的原子数。因此，对于所有意图和目的，对于任何现实生活中的 n 值，f(n) 的倒数都是常数。\n 从工程师\xe2\x80\x99s 的角度来看，\n Kruskal\xe2\ x80\x99s 算法的运行时间为 O(e)。\n 当然请注意，从\n 理论家\xe2\x80\x99s 的角度来看，O(e) 的真实\n 结果仍然是一个\n 重大突破。 整个\n图片并不完整，因为\n实际的最佳结果表明lg*n可以\n替换为A(p,n)\n的逆\n，其中A是Ackermann\xe2\x80\x99s函数，a \n 爆炸式增长的功能。Ackermann\xe2\x80\x99s 函数的反函数与 lg*n 相关，并且是一个更好的结果，但证明更加困难。

\n

\n