使用不相交集的每次操作的摊销时间
我碰巧在维基百科上读到，对不相交集合（合并两个元素，找到特定元素的父元素）的每次操作的摊销时间是 O(a(n))，其中 a(n) 是反阿克曼函数，它会增长非常快。
谁能解释为什么这是真的？
I happened to read on Wikipedia that the amortized time per operation on a disjoint set (union two elements, find parent of a specific element) is O(a(n)), where a(n) is the inverse Ackermann function, which grows very fast.
Can anyone explain why this is true?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
好吧，维基百科页面有一个引文。 如果您有兴趣，请检查一下。 如果您在大学，那应该很容易，如果不是，只需找到附近的一所大学并使用他们的图书馆（他们不在乎您是否不是学生）。
Well, the Wikipedia page has a citation. If you're that interested, check it out. If you're at college that should be easy, if not, just find a nearby college and use their library (they don't care if you're not a student).
嗯，这很难解释，因为这不是真的。 非逆阿克曼函数像火箭一样增长，而逆阿克曼函数则增长非常缓慢。
这为您提供了理论背景。
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.
算法简介中有事实证明。 这似乎是一本相当受欢迎的读物，你的城市或学校图书馆可能有一本。 我也在互联网上看到过一些副本，但这些副本的合法性可能值得怀疑。
编辑：大部分证明似乎可以在 Google 图书上阅读。
There is a proof of the fact in Introduction to Algorithms. It's a fairly popular read it seems, and your city or school library might have a copy. I've also seen copies floating about on the Internet but the legality of those is probably questionable.
EDIT: a chunk of the proof appears to be readable on Google Books.