我正在Coursera上学习算法课程，其中有一节作者提到了以下内容
路径压缩加权快速联合的运行时间为在现实世界中是线性的，实际上可以改进为甚至还有一个更有趣的函数叫做Ackermann函数比lg的增长还要慢。还有一点是不是看起来非常接近线性以至于时间与N成正比而不是与N成正比在n中缓慢增长的函数，有没有一个简单的算法线性吗?人们为此寻找了很长一段时间，而事实上结果是我们可以证明没有这样的算法。(强调)
(你可以在这里找到全文)
在包括维基百科在内的所有其他来源中，当时间与输入大小成比例地增加时，使用"线性"，而在路径压缩的加权快速联合中，这肯定不是这种情况。
这里的"现实世界中的线性"究竟是什么意思?
对具有路径压缩和按秩并集的并查找数据结构进行m次操作的运行时间为O(mα(m))，其中α(m)为逆Ackermann函数。这个函数的增长非常缓慢，以至于您无法用科学记数法表示输出为6的输入。换句话说，对于宇宙中任何可能的m值(甚至是宇宙中大约有2个原子的大小)，我们有& α;(m) ≤5. 因此，对于任何"合理"的输入，m个操作的代价将是O(m ·6) = 0 (m)，线性
当然，运行时间不是线性的，因为α(m)确实在增长，只是非常非常慢。然而，将运行时间近似为O(m)通常是可以的，因为你不可能注意到函数的运行时间偏离了简单的线性函数。
希望这对你有帮助!
摘录如下:
证明了什么由霍普克罗夫特·乌尔曼和塔扬所写你有N个对象，M的任意序列工会和查找操作将触摸到数组最多只能有c (N + mlg * N)次。lg N是个有趣的函数....
还有一点大概是这样吧!/i>似乎这是非常接近线性，这是t时间与N成正比，而不是与时间成正比与生长缓慢的N倍成正比函数n
(")你指出单个操作的成本随着对象数量的增加而缓慢增长，但他们关注的是多个操作的总成本是如何随着涉及的对象数量的增加而增长的所以N乘以每次操作的成本随着N的增加而缓慢增长，在N上仍然是线性的