0

我发现一些在线union-find 教程描述了路径压缩技术，甚至比O(log(N))复杂性还要低find()，下面是这个博客中的路径压缩实现，

int root (int Arr[], int i) {
    while(Arr[i] != i) {
        Arr[i] = Arr[ Arr[i] ]; 
        i = Arr[i]; 
    }
   return i;
}

我看到这个实现只是将路径减少了一半，并且可以使用下面的递归技巧来进一步压缩，

int recurse_root (int Arr[], int i) {
    if ( i == Arr[i] ){
        return i;
    }
    Arr[i] = recurse_root( Arr, Arr[i] )
    return A[i];
}

我想知道我是否遗漏了什么，为什么大多数在线教程都没有讨论这种技术？

4

1 回答 1

2

我想知道我是否遗漏了什么，为什么大多数在线教程都没有讨论这种技术？

这样的在线教程没有使用正确的路径压缩启发式（如您所想）或没有提及它，因为很难证明它的运行时间是真实的，或者他们在没有证据的情况下提及它。

我不喜欢在线教程，所以我无法确定我暴露的 3 个原因中哪一个是最常见的。我可以告诉你的是，在《算法简介》（Cormen），第 3 版，第 569 和 570 页中，您可以找到包含图像的路径压缩启发式的出色解释。此外，如果您正在寻找实际运行时间的证明，请从第 573 页开始阅读（重读，值得一读）。

也许它在在线教程中并不流行，但在 CS 学位中必须知道它的存在。

于 2020-09-21T22:34:17.400 回答