Ackermann函数为什么与用于不相交集合的并查集算法的平摊复杂度相关？

Question

Ackermann函数为什么与用于不相交集合的并查集算法的平摊复杂度相关？

16

请问有没有人能直观地解释一下阿克曼函数http://en.wikipedia.org/wiki/Ackermann_function与并查集算法http://en.wikipedia.org/wiki/Disjoint-set_data_structure的分摊复杂度有什么关系？

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

我也在《算法导论》中查找过，但那本书似乎也过于严谨和不够直观。

感谢您的帮助！

- Tianyang Li

@CrisStringfellow 我该怎么做？ - Tianyang Li

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- SDReyes · Accepted Answer

应用于不相交集合森林

来自维基百科

(关于查找和合并)这两个技术互补; 应用在一起，每个操作的平均时间为O(α(n))，其中α(n)是函数f(n)=A(n,n)的反函数，而A是增长极快的Ackermann函数。由于α(n)是这个函数的反函数，对于所有实际可行的n值，α(n)都小于5。因此，每个操作的平均运行时间实际上是一个小常数。

那么为什么是Ackerman函数？

来自Kruskal算法

函数lg*n

请注意，lg*n是一个非常缓慢的增长函数，比lg n慢得多。事实上比lg lg n或任何有限组合的lg n还要慢。它是函数f(n)=2^2^2^…^2，n次方的反函数。对于n>=5，f(n)大于宇宙中的原子数量。因此，对于任何实际生活中的n值， f(n)的反函数都是常数。从工程师的角度来看， Kruskal算法的运行时间为O(e)。当然，从理论学家的角度来看， O(e)的真正结果仍然是一个重大突破。整个局面尚未完全展现，因为实际上最佳结果表明， lg*n可以用A(p,n)的反函数代替，其中A是Ackermann函数，这是一个增长迅速的函数。 Ackermann函数的反函数与lg*n有关，是一个更好的结果，但证明更难。