algorithm - 联合查找数据结构为 "linear in the real world?"是什么意思

Question

我正在承担 algorithms course on Coursera ，有一节作者提到了以下内容

the running time of weighted quick union with path compression is going be linear in the real world and actually could be improved to even a more interesting function called the Ackermann function, which is even more slowly growing than lg. And another point about this is it seems that this is so close to being linear that is time proportional to N instead of time proportional to N times the slowly growing function in N. Is there a simple algorithm that is linear? And people, looked for a long time for that, and actually it works out to be the case that we can prove that there is no such algorithm. (emphasis added)

(您可以找到整个 transcript here )

在所有其他来源中，包括 Wikipedia当时间与输入大小成比例增加时使用“线性”，而在具有路径压缩的加权快速联合中，情况肯定不是这种情况。

这里的“现实世界中的线性”到底是什么意思？

Answer 1

在具有路径压缩和按秩联合的联合查找数据结构上进行 m 次操作的运行时间为 O(mα(m))，其中 α(m) 是反阿克曼函数。此函数增长如此缓慢，以至于您无法用科学计数法表示输出为 6 的输入。换句话说，对于适合宇宙的任何可能的 m 值(甚至大小约为宇宙中 2^{num 个原子})，我们有 α(m) ≤ 5。因此，对于任何“合理”的输入 m 操作的成本将是 O(m · 6) = O(m)，这是线性的。

当然，运行时间不是线性的，因为 α(m) 确实会增长，只是非常非常缓慢。但是，将运行时间近似为 O(m) 通常没问题，因为您不可能注意到函数的运行时间偏离了简单的线性函数。

希望这对您有所帮助!