我正在Coursera 上进行算法课程，作者在其中提到以下部分
带有路径压缩的加权快速联合的运行时间在现实世界中将是线性的，实际上可以改进为一个更有趣的函数，称为 Ackermann 函数，它比 lg 增长得更慢。关于这一点的另一点是，这似乎非常接近于线性，即时间与 N 成正比，而不是时间与 N 乘以 N 中缓慢增长的函数成正比。是否有一个简单的线性算法？人们为此寻找了很长时间，实际上我们可以证明没有这样的算法。（重点补充）
（你可以在这里找到完整的成绩单）
在包括维基百科在内的所有其他来源中，当时间与输入大小成比例增加时，使用“线性”，而在带有路径压缩的加权快速联合中，情况肯定不是这样。
这里的“现实世界中的线性”到底是什么意思？
在具有路径压缩和按秩并集的联合查找数据结构上执行 m 次操作的运行时间为 O(mα(m))，其中 α(m) 是反阿克曼函数。这个函数的增长非常缓慢，以至于你无法用科学计数法表示输出为 6 的输入。换句话说，对于适合宇宙的任何可能的 m 值（或者甚至在宇宙中具有大约 2 个num 个原子的大小），我们有 α(m) ≤ 5。因此，对于任何“合理的”输入，成本m 次操作将是 O(m · 6) = O(m)，这是线性的。
当然，运行时间不是线性的，因为 α(m) 确实增长了，只是非常非常缓慢。但是，将运行时间近似为 O(m) 通常很好，因为您不可能注意到函数的运行时间偏离简单的线性函数。
希望这可以帮助！
以下是成绩单中的一些片段：
Hopcroft Ulman 和 Tarjan 证明的是，如果您有 N 个对象，则任何 M 个 union 和 find 操作序列最多将接触数组 ac (N + M lg star N) 次。现在，lg N 是一个有趣的函数......
关于这一点的另一点是它似乎非常接近线性，即时间与 N 成正比，而不是时间与 N 乘以 N 中的缓慢增长函数。
（结束报价）
您指出单个操作的成本随着对象数量的增加而增长非常缓慢，但他们正在研究多个操作的总成本如何随着所涉及的对象数量而增长，因此 N 乘以每次操作成本增长非常缓慢，而 N 在 N 中仍然刚刚超过线性。