big-o - 使用不相交集的每次操作的摊销时间

Question

我碰巧在维基百科上读到，在不相交集（联合两个元素，找到特定元素的父元素）上每次操作的摊销时间是 O(a(n))，其中 a(n) 是逆阿克曼函数，它会增长非常快。

谁能解释为什么这是真的？

Answer 1

Well, that would be rather hard to explain, because it isn't true. It's the non-inverse Ackermann function that grows like a rocket on steroids, the inverse Ackermann grows very slowly.

This gives you the theoretical background.

Answer 2

好吧，维基百科页面有引用。如果您有兴趣，请检查一下。如果你在大学那应该很容易，如果不是，那就找一所附近的大学并使用他们的图书馆（他们不在乎你是否不是学生）。

Answer 3

算法导论中有一个事实证明。这似乎是一本相当受欢迎的读物，您所在的城市或学校图书馆可能有一份副本。我还看到互联网上流传着副本，但这些副本的合法性可能值得怀疑。

编辑：一大块证据似乎在谷歌图书上是可读的。