为什么Ackermann函数与用于不相交集的联合查找算法的摊余复杂性有关？ [英] Why is the Ackermann function related to the amortized complexity of union-find algorithm used for disjoint sets?

问题描述

有人可以给我直观的解释为什么Ackermann函数 http://en.wikipedia.org/ Wiki / Ackermann_function 与用于不相交集的联合查找算法的摊销复杂度有关 http ：//en.wikipedia.org/wiki/Disjoint-set_data_structure ？

Can anybody give me an intuitive explanation of why the Ackermann function http://en.wikipedia.org/wiki/Ackermann_function is related to the amortized complexity of union-find algorithm used for disjoint sets http://en.wikipedia.org/wiki/Disjoint-set_data_structure?

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

The analysis in Tarjan's data structure book isn't very intuitive.

我也在算法导论中进行了查找，但它似乎也过于严格和不直观。

I also looked it up in Introduction to Algorithms, but it also seems too rigorous and non-intuitive.

感谢您的帮助！

推荐答案

适用于不相交的森林

来自维基百科

（关于查找和并集）这两种
技术互相补充；
一起应用，每个操作的摊销时间
仅O（α（n）），其中
α（n）是函数
f（n）= A的反函数（n，n），而A是快速增长的极其快的Ackermann函数。
因为α（n）是此
函数的逆函数，所以对于所有
的远程实际值n，α（n）小于5。因此，
每
操作的摊销运行时间实际上是一个小的
常数。

(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.

为什么是阿克曼人？

来自

rel = nofollow>克鲁斯卡尔算法

函数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）
的倒数代替lg * n是Ackermann的函数，一个
函数，爆炸性地增长。 Ackermann函数的
逆是与lg * n相关的
，是更好的
结果，但证明甚至更难
。

这篇关于为什么Ackermann函数与用于不相交集的联合查找算法的摊余复杂性有关？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！