4

今天，由于这张幻灯片的第 13 页，我与某人讨论了 Kruskal 最小生成树算法。

该演示文稿的作者说，如果我们使用（双）链表实现不相交集，则性能为Make和Find的性能将分别为O(1)和O(1)。运算Union(u,v)的时间为min(nu,nv)，其中nu和nv是存储 u 和 v 的集合的大小。

我说过我们可以通过使每个成员的表示指针指向一个包含指向集合的真实表示的指针的定位器来将Union(u,v)的时间缩短为O(1) 。

在 Java 中，数据结构如下所示：

class DisjointSet {
    LinkedList<Vertex> list = new LinkedList<Vertex>(); // for holding the members, we might need it for print

    static Member makeSet(Vertex v) {
        Member m = new Member();

        DisjointSet set = new DisjointSet();
        m.set = set;
        set.list.add(m);

        m.vertex = v;

        Locator loc = new Locator();
        loc.representation = m;
        m.locator = loc;

        return m;
    }
}

class Member {
    DisjointSet set;
    Locator locator;
    Vertex vertex;

    Member find() {
        return locator.representation;
    }

    void union(Member u, Member v) { // assume nv is less than nu
        u.set.list.append(v.set.list); // hypothetical method, append a list in O(1)
        v.set = u.set;
        v.locator.representation = u.locator.representation;
    }

}

class Locator {
    Member representation;
}

对不起，简约的代码。如果可以这样制作，那么每个不相交集操作（Make,Find,Union）的运行时间将是O(1)。但与我讨论过的人看不到改进。我想知道你对此的看法。

Find/Union 在各种实现中的最快性能是什么？我不是数据结构方面的专家，但是通过在互联网上快速浏览，我发现没有恒定时间数据结构或算法可以做到这一点。

4

2 回答 2

4

我的直觉同意你的同事。你说：

u.set.list.append(v.set.list); // hypothetical method, append a list in O(1)

看起来您的意图是联合是通过附加完成的。但是，要实现联合，您必须删除重复项才能使结果成为一个集合。所以我可以看到一个固定集合大小的 O(1) 算法，例如......

Int32 set1;
Int32 set2;

Int32 unionSets1And2 = set1 | set2;

但这让我觉得作弊。如果您针对 N 的一般情况执行此操作，我看不出您如何避免某种形式的迭代（或哈希查找）。这将使它成为 O(n)（或最多 O(log n)）。

仅供参考：我很难遵循您的代码。在 makeSet 中，您构造了一个永远不会转义函数的本地定位器。看起来它什么也没做。目前尚不清楚您在附录中的意图是什么。可能想要编辑和详细说明您的方法。

于 2010-08-14T22:18:36.903 回答
3

使用Tarjan 版本的 Union-Find 结构（具有路径压缩和秩加权联合），m个Find 和(n-1) 个混合联合的序列将在 O(m.α(m,n)) 中，其中 α (m,n) 是Ackermann 函数的逆函数，对于m和n的所有实际值，其值为 4。所以这基本上意味着 Union-Find 具有最坏情况的摊销常数运算，但并不完全如此。

据我所知，不可能获得更好的理论复杂性，尽管改进带来了更好的实际效率。

对于诸如语言理论中使用的不相交集的特殊情况，已经表明线性（即 O(1) 中的所有内容）适应是可能的——主要是通过将节点分组在一起——但这些改进不能翻译成一般问题。另一方面，一个有点相似的核心思想已被成功地和独创性地用于最小生成树的 O(n) 算法（Chazelle 算法）。

所以你的代码不可能是正确的。错误是 Moron 指出的：当你合并两个集合时，你只更新每个列表的前导的“表示”，而不是所有其他元素的“表示”——同时在 find 函数中假设每个元素直接知道它的表示。

于 2010-08-14T22:40:07.407 回答