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

Question

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

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

我也在Introduction to Algorithms中查到过，但也显得过于严谨和不直观。

谢谢你的帮助！

Answer 1

应用于不相交的森林

来自维基百科

（关于find和union）这两种技术相辅相成；一起应用，每次操作的摊销时间仅为 O(α(n))，其中 α(n) 是函数 f(n) = A(n,n) 的倒数，而 A 是增长极快的 Ackermann功能。由于 α(n) 是该函数的倒数，因此对于所有 n 的远程实际值，α(n) 都小于 5。因此，每次操作的摊销运行时间实际上是一个小常数。

那么为什么是阿克曼？

来自克鲁斯卡尔算法

函数 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) 的倒数都是常数。从工程师的角度来看，克鲁斯卡尔算法的运行时间为 O(e)。当然请注意，从理论家的角度来看，O(e) 的真实结果仍然是一个重大突破。 整幅图并不完整，因为实际最好的结果表明 lg*n 可以替换为 A(p,n) 的倒数，其中 A 是阿克曼函数，一个爆炸式增长的函数。Ackermann 函数的逆函数与 lg*n 相关，是一个更好的结果，但证明更加困难。