java - 联合查找二次算法如何？

Question

在这个快速查找算法的实现中，构造函数执行 N 步，union() 也是如此。

老师说 union 太昂贵了，因为它需要 N^2 来处理 N union N 对象上的命令，当一次访问一个数组元素时，union 怎么可能是二次的？

public class QuickFind
{
    private int[] id;

    public QuickFind(int N) {
        id = new int[N];
        for (int i=0; i<N; i++) {
            id[i] = i;
        }
    }

    public boolean connected(int p, int q) {
        return id[p] == id[q];
    }

    public void union(int p, int q) {
        int pid = id[p];
        int qid = id[q];

        for (int i=0; i<id.length; i++)
            if (id[i] == pid)
                id[i] = qid;
    }
}

Answer 1

每次调用 union方法要求您遍历 id数组，需要 O(n)时间。如果调用 union方法 n次，则所需时间为n*O(n) = O(n^2) .

您可以提高 union 的时间复杂度O(1) 的方法，通过提高连接方法的时间复杂度，可能是O(log n) ，但这只是一次操作。我相信您的教科书对此有详细解释。